工件具有學習與惡化效應的現(xiàn)代排序問題研究

1、博士學位論文工件具有學習與惡化效應的現(xiàn)代排序問題研究S t u d yO n M o d e r nS c h e d u l i n gP r o b l e m s w i t hD e t e r i o r a t i o na n dL e a r n i n g E f f e c t s C o n s i d e r a t i o n s學 1 0 7 0 1 0 5 2大連理工大學D a l i a n U n i

2、v e r s i t yo f T e c h n o l o g y大連理工大學博士學位論文摘 要燦哪㈣帥l I I I l 眥尷I I I I 蛐 Y 2 5 9 3 0 6 3排序問題是一類重要的組合優(yōu)化問題，是運籌學的一個重要分支。經(jīng)典的排序問題中，工件的加工時間一般被認為是常數(shù)。然而由于一些實際因素的影響，被加工的工件的實際加工時間是可變的。這樣的因素很多，如：工件的加工位置、開工時間等。由此，產(chǎn)生了具有學習效應與惡化效應的

3、現(xiàn)代排序問題。由于諸多因素的影響，所以這些問題大多情況下比經(jīng)典排序問題更難于解決，很多都屬于N P ．難問題。處理N P ．難問題，本文給出了基于某些特殊情下該類問題算法的最壞情況界并提出它們的有效算法。某些帶有學習效應與惡化效應的現(xiàn)代排序問題是存在多項式算法的，研究這類問題也是非常有價值的。若該類問題存在多項式算法不但可以解決該類問題，也為與其相似的N P ．難問題提供近似算法。對于工件具有學習效應與惡化效應的現(xiàn)代排序問題，本文做了如

4、下的幾個的面的工作：1 ．在學習效應的環(huán)境下的現(xiàn)代排序問題。( 1 ) 學習效應與工件在加工中所處的位置相關(guān)的排序問題，在單機情況下，討論了三個不同的目標函數(shù)分別為：加權(quán)完工時間和、最大延遲和誤工數(shù)。并且針對這三個問題的一些特殊情況，證明了它們是多項式時間可解的，也給出了三個最壞情況界。( 2 ) 學習效應與工件位置相關(guān)并且?guī)в兴沙诠て诘膯螜C排序問題，研究了極小化提前成本、延遲成本和工期的松弛的加權(quán)和，將此問題轉(zhuǎn)化成為了指派問題，同時給

5、出多項式時間最優(yōu)算法。( 3 ) 學習效應與工件的加工時間和相關(guān)的排序模型，解決了0 < 口< l ( 口為學習效應) 時極小化完工時間問題是多項式時間可解的，最優(yōu)排序可以按照工件正常加工時間從大到小排列得到。對于該模型的完工時間和問題，給出了最優(yōu)解具有V ．型性質(zhì)。( 4 ) 學習效應與工件正常加工時間的對數(shù)和相關(guān)的單機成組排序問題，給出了當目標函數(shù)為極小化最大完工時間時的多項式時間算法。2 ．工件具有惡化效應的現(xiàn)代排序問