關(guān)于兩種現(xiàn)代排序模型的一些結(jié)果.pdf

1、授予單位代碼：!Q!i2研究生學(xué)號：Q2Q!!!密級：——鄭州大學(xué)碩士學(xué)位論文論文題目：關(guān)于兩種現(xiàn)代排序模型的一些結(jié)果作者姓名學(xué)科門類專業(yè)方向?qū)熜彰?、職稱錄嶺法理學(xué)運籌學(xué)與控制論原晉江教授二零零五年四月每個工件以有一個加工時間P3和一個尺寸島，在這里sJ代表工件以被裝到汽車中所要占的空間大小僅僅有一輛汽車去運送所有的工件，它有一個容量限制。目標(biāo)是尋找一個工件加工和運輸?shù)呐判颍沟盟泄ぜ患庸ね戤叢⑦\送給顧客的時間達(dá)到最小根據(jù)Lee和

2、Chertf20J的記號，這個問題被記為1一D，≈=1I”=l，c—zIC。。這里“1一D，k=1”表示工件首先在一臺機器上加工，然后被運送給一個顧客；“”=1，c=z”表示僅僅有一輛汽車去運送所有的工件，并且汽車的容量為z有關(guān)工件加工和運輸?shù)呐判騿栴}已經(jīng)成為在近十幾年里最重要的、被廣泛研究的課題之一Ahmadi113】等人研究了兩臺機器(一臺單機和一臺隨后的分批加工機器)的流水作業(yè)排序問題，目標(biāo)是最小化最大完工時間和完工時間和Herr

3、mann和Lee[19】，Yuan【24]，Chen[15】，Yang【231和Cheng[17]等人考慮了與工期相關(guān)的指標(biāo)的分批排序問題Lee和Chen[20]根據(jù)運輸時間和汽車容量，而不考慮運送的費用，提出了另一種工件加工和運輸?shù)淖钚』畲笸旯r間問題Chang和Lee[16】又發(fā)展了這個問題，他們考慮每個工件在汽車中占據(jù)不同的空間他們證明了這個問題1一D，k=lJ”=1，c=zlC。。是強NP一困難的，同時也提供了一個啟發(fā)式算法，

4、它的最差執(zhí)行比為：，并且這個界是緊的但是，他們所考慮的工件的加工時間和它們的尺寸是獨立的而在實際生產(chǎn)中，與小的尺寸的工件相比，具有大的尺寸的工件往往需要更多的加工時間因此，我們考慮了一種特殊的情形，即工件的加工時間和它們的尺寸戍正比在這種限制下，問題被記為1一D，k=lp=1，c=。，pj_“qf％。我們證明了當(dāng)工件的加工時間和它們的尺寸成正比時，這個問題仍然是強NP困難的并且Chang和Lee提出的啟發(fā)式算法對我們研究的問題有更好的執(zhí)