考慮維護(hù)時(shí)間的機(jī)器調(diào)度問題研究.pdf

1、傳統(tǒng)的機(jī)器調(diào)度問題通常假定在整個(gè)調(diào)度期內(nèi)機(jī)器一直可用。然而，在實(shí)際生產(chǎn)過程中，為了減少因機(jī)器失效或機(jī)器故障而導(dǎo)致的產(chǎn)品質(zhì)量下降、維護(hù)成本增加和生產(chǎn)效率降低等問題，企業(yè)一般都會(huì)在調(diào)度期之前預(yù)先安排機(jī)器維護(hù)，因此在調(diào)度問題中考慮這種預(yù)防維護(hù)時(shí)間更具現(xiàn)實(shí)意義。
　　 本文首先較為詳盡的研究了考慮維護(hù)時(shí)間的單機(jī)調(diào)度問題，包括維護(hù)時(shí)段固定且加工時(shí)間恒定、維護(hù)時(shí)段固定且加工時(shí)間可變、維護(hù)時(shí)段可調(diào)且加工時(shí)間恒定以及維護(hù)時(shí)段可調(diào)且加工時(shí)間可變等

2、四類問題。對(duì)于多機(jī)調(diào)度問題，重點(diǎn)研究了維護(hù)時(shí)段固定且加工時(shí)間恒定的問題，以此說明了把單機(jī)調(diào)度問題的求解方法拓展到相應(yīng)多機(jī)調(diào)度問題的思路，其他三類問題均可按照這種思路進(jìn)行求解。受維護(hù)時(shí)段的影響，工件在加工過程中可能會(huì)被中斷，基于實(shí)際生產(chǎn)過程中的不同情況，本文分別考慮了被中斷工件可續(xù)、不可續(xù)和部分可續(xù)三種情形。
　　 上述問題的目標(biāo)函數(shù)假定為與生產(chǎn)效率有關(guān)的最大完工時(shí)間及（加權(quán)）完工時(shí)間和。根據(jù)問題的復(fù)雜性不同，本文給出了不同的求解

3、方法：對(duì)于NP-難問題，本文一方面致力于設(shè)計(jì)能求解盡可能大規(guī)模問題的精確算法，另一方面，鑒于精確算法在時(shí)間和空間性能上的不足，本文也致力于構(gòu)造高效的啟發(fā)式算法，從而能夠在合理的時(shí)間內(nèi)求得大規(guī)模問題高質(zhì)量的滿意解；另外，在某些特殊情形下，有些問題是多項(xiàng)式可解的，對(duì)于這些問題，本文通過證明某種多項(xiàng)式時(shí)間算法能夠?yàn)槠涮峁┳顑?yōu)解來說明其多項(xiàng)式可解性。
　　 具體而言，本文的主要研究內(nèi)容和創(chuàng)新點(diǎn)如下：
　　 （1）對(duì)于維護(hù)時(shí)段固定

4、且加工時(shí)間恒定的單機(jī)調(diào)度問題，研究了部分可續(xù)情形下的兩種目標(biāo)函數(shù)。對(duì)于最大完工時(shí)間最小化問題，簡單說明了此問題的NP-難性，給出了最大加工時(shí)間優(yōu)先（Longest processing time first，LPT）規(guī)則的最壞情況相對(duì)誤差界，進(jìn)而提出了兩個(gè)基于LPT 規(guī)則的啟發(fā)式算法：LPT-PI和MLPT，其中LPT-PI以LPT 規(guī)則作為初始解，并結(jié)合基于成對(duì)交換技術(shù)的鄰域搜索對(duì)解進(jìn)行改進(jìn)，而MLPT 通過改進(jìn)LPT 算法執(zhí)行過程中

5、的某一類特殊情況來得到更優(yōu)的啟發(fā)式解。另外，還證明了MLPT的最壞情況相對(duì)誤差界，并通過大規(guī)模實(shí)驗(yàn)對(duì)算法性能進(jìn)行了對(duì)比分析。對(duì)于加權(quán)完工時(shí)間和最小化問題，簡單說明了問題的NP-難性，提出了最優(yōu)解的性質(zhì)，并在此基礎(chǔ)上構(gòu)造了動(dòng)態(tài)規(guī)劃和分枝定界兩種精確算法。
　　 大量隨機(jī)數(shù)據(jù)的實(shí)驗(yàn)結(jié)果表明這兩種算法都是有效的，且不論從能解問題規(guī)模，還是從尋得最優(yōu)解所需時(shí)間方面，分枝定界算法都要優(yōu)于動(dòng)態(tài)規(guī)劃算法。
　　 （2）對(duì)于維護(hù)時(shí)段固定

6、且加工時(shí)間可變的單機(jī)調(diào)度問題，研究了最大完工時(shí)間及完工時(shí)間和兩種目標(biāo)函數(shù)。證明了這兩種目標(biāo)函數(shù)下加工時(shí)間線性增加和線性減少時(shí)的幾種可續(xù)情形是多項(xiàng)式可解的。對(duì)于不可續(xù)情形，重點(diǎn)研究了加工時(shí)間線性增加時(shí)的完工時(shí)間和問題。
　　 對(duì)于該問題，簡單說明了其NP-難性，證明了最優(yōu)解的性質(zhì)，在此基礎(chǔ)上構(gòu)造了一種動(dòng)態(tài)規(guī)劃算法，鑒于此算法應(yīng)用上的局限性，給出了SNPT(Shortest normal processing time）規(guī)則的最壞情

7、況相對(duì)誤差界，進(jìn)而提出了一種基于SNPT 規(guī)則和交換技術(shù)的啟發(fā)式算法。大量算例的實(shí)驗(yàn)結(jié)果顯示不僅算法的運(yùn)行時(shí)間很少，相對(duì)誤差也很?。ㄆ骄鄬?duì)誤差和最大相對(duì)誤差分別為0.082％和3.448％），并且將近有一半的算例能得到最優(yōu)解，因此該啟發(fā)式算法能夠很高效的解決此類問題。而對(duì)于其他目標(biāo)函數(shù)和加工時(shí)間函數(shù)下的不可續(xù)情形，通過分析與上述問題求解方法上的相似性，給出了其求解思路。
　　 （3）對(duì)于維護(hù)時(shí)段可調(diào)的單機(jī)調(diào)度問題，重點(diǎn)研究了加

8、工時(shí)間恒定的問題，考慮了完工時(shí)間和這個(gè)目標(biāo)函數(shù)。對(duì)于可續(xù)情形，給出了最優(yōu)解的幾個(gè)性質(zhì)，提出了一種SPT 算法，并證明了其最優(yōu)性；對(duì)于不可續(xù)情形，簡單說明了其NP-難性，提出了幾個(gè)與可續(xù)情形類似的最優(yōu)解的性質(zhì)和SPT 算法，給出了該算法最優(yōu)的條件，并證明了其最壞情況相對(duì)誤差界。在最優(yōu)解性質(zhì)的基礎(chǔ)上，構(gòu)造了一種動(dòng)態(tài)規(guī)劃算法和一種分枝定界算法，其中分枝定界算法的初始解是在SPT 算法的基礎(chǔ)上利用兩條性質(zhì)對(duì)維護(hù)時(shí)段之前的末工件和維護(hù)時(shí)段之后的工

9、件進(jìn)行交換所得，而提出的幾個(gè)下界是基于維護(hù)時(shí)段固定的相應(yīng)問題。實(shí)驗(yàn)證明了動(dòng)態(tài)規(guī)劃和分枝定界這兩種算法的有效性及互補(bǔ)性。對(duì)于加工時(shí)間可變的調(diào)度問題，首先證明了其可續(xù)情形是多項(xiàng)式可解的，并對(duì)此問題與相應(yīng)加工時(shí)間恒定問題在求解方法上的相似性進(jìn)行了總結(jié)，進(jìn)而給出了不可續(xù)情形的求解思路。
　　 （4）對(duì)于多機(jī)調(diào)度問題，重點(diǎn)研究了維護(hù)時(shí)段固定且加工時(shí)間恒定的問題，考慮了部分可續(xù)情形下的兩種目標(biāo)函數(shù)。對(duì)于最大完工時(shí)間最小化問題，說明了問題的N

10、P-難性，建立了整數(shù)規(guī)劃模型，并提出了兩臺(tái)機(jī)器上工件互換的四條性質(zhì)，進(jìn)而提出了一種啟發(fā)式算法，該算法首先把所有工件按LPT 算法進(jìn)行分配，得到一個(gè)可行解，然后再重復(fù)把最大完工時(shí)間最大和最小兩臺(tái)機(jī)器上的工件進(jìn)行互換以提高解的質(zhì)量。該啟發(fā)式算法和LPT 算法的對(duì)比實(shí)驗(yàn)結(jié)果驗(yàn)證了此算法的有效性；對(duì)于加權(quán)完工時(shí)間和最小化問題，說明了問題的NP-難性，給出了最優(yōu)解的性質(zhì)，進(jìn)而提出了一種動(dòng)態(tài)規(guī)劃算法來求得中小規(guī)模問題的最優(yōu)解，另外還提出了一種基于W