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

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

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

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

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