23053.工件具有學(xué)習(xí)與惡化效應(yīng)的現(xiàn)代排序問(wèn)題研究

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

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

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

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