1、博士學(xué)位論文工件具有學(xué)習(xí)與惡化效應(yīng)的現(xiàn)代排序問(wè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學(xué) 1 0 7 0 1 0 5 2大連理工大學(xué)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大連理工大學(xué)博士學(xué)位論文摘 要燦哪㈣帥l I I I l 眥尷I I I I 蛐 Y 2 5 9 3 0 6 3排序問(wèn)題是一類(lèi)重要的組合優(yōu)化問(wèn)題，是運(yùn)籌學(xué)的一個(gè)重要分支。經(jīng)典的排序問(wèn)題中，工件的加工時(shí)間一般被認(rèn)為是常數(shù)。然而由于一些實(shí)際因素的影響，被加工的工件的實(shí)際加工時(shí)間是可變的。這樣的因素很多，如：工件的加工位置、開(kāi)工時(shí)間等。由此，產(chǎn)生了具有學(xué)習(xí)效應(yīng)與惡化效應(yīng)的

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

4、下的幾個(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è)最壞情況界。( 2 ) 學(xué)習(xí)效應(yīng)與工件位置相關(guān)并且?guī)в兴沙诠て诘膯螜C(jī)排序問(wèn)題，研究了極小化提前成本、延遲成本和工期的松弛的加權(quán)和，將此問(wèn)題轉(zhuǎn)化成為了指派問(wèn)題，同時(shí)給

5、出多項(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ù)和相關(guān)的單機(jī)成組排序問(wèn)題，給出了當(dāng)目標(biāo)函數(shù)為極小化最大完工時(shí)間時(shí)的多項(xiàng)式時(shí)間算法。2 ．工件具有惡化效應(yīng)的現(xiàn)代排序問(wèn)