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

1、博士學位論文工件具有學習與惡化效應的現(xiàn)代排序問題研究StudyOnModernSchedulingProblemswithDeteriorationandLearningEffectsConsiderations學10701052大連理工大學DalianUniversityofTechnology大連理工大學博士學位論文摘要燦哪㈣帥lIIIl眥尷IIII蛐Y2593063排序問題是一類重要的組合優(yōu)化問題，是運籌學的一個重要分支。經(jīng)典的排

2、序問題中，工件的加工時間一般被認為是常數(shù)。然而由于一些實際因素的影響，被加工的工件的實際加工時間是可變的。這樣的因素很多，如：工件的加工位置、開工時間等。由此，產(chǎn)生了具有學習效應與惡化效應的現(xiàn)代排序問題。由于諸多因素的影響，所以這些問題大多情況下比經(jīng)典排序問題更難于解決，很多都屬于NP難問題。處理NP難問題，本文給出了基于某些特殊情下該類問題算法的最壞情況界并提出它們的有效算法。某些帶有學習效應與惡化效應的現(xiàn)代排序問題是存在多項式算法的

3、，研究這類問題也是非常有價值的。若該類問題存在多項式算法不但可以解決該類問題，也為與其相似的NP難問題提供近似算法。對于工件具有學習效應與惡化效應的現(xiàn)代排序問題，本文做了如下的幾個的面的工作：1在學習效應的環(huán)境下的現(xiàn)代排序問題。(1)學習效應與工件在加工中所處的位置相關的排序問題，在單機情況下，討論了三個不同的目標函數(shù)分別為：加權(quán)完工時間和、最大延遲和誤工數(shù)。并且針對這三個問題的一些特殊情況，證明了它們是多項式時間可解的，也給出了三個最

4、壞情況界。(2)學習效應與工件位置相關并且?guī)в兴沙诠て诘膯螜C排序問題，研究了極小化提前成本、延遲成本和工期的松弛的加權(quán)和，將此問題轉(zhuǎn)化成為了指派問題，同時給出多項式時間最優(yōu)算法。(3)學習效應與工件的加工時間和相關的排序模型，解決了0口l(口為學習效應)時極小化完工時間問題是多項式時間可解的，最優(yōu)排序可以按照工件正常加工時間從大到小排列得到。對于該模型的完工時間和問題，給出了最優(yōu)解具有V型性質(zhì)。(4)學習效應與工件正常加工時間的對數(shù)和相