考慮維護時間的機器調(diào)度問題研究.pdf

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

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

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

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

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

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

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

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

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

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