若干批處理機(jī)排序與裝箱問題的算法研究.pdf

1、本文主要研究了批處理機(jī)排序和裝箱問題的一些新模型.排序問題和裝箱問題都是經(jīng)典的組合優(yōu)化問題，受到眾多學(xué)者的關(guān)注.隨著社會(huì)的發(fā)展，又不斷地產(chǎn)生一些新模型.批處理機(jī)排序問題就來源于現(xiàn)實(shí)生活中的半導(dǎo)體以及大規(guī)模集成電路生產(chǎn)中的產(chǎn)品檢驗(yàn)階段，一臺(tái)機(jī)器可以同時(shí)對(duì)多個(gè)工件進(jìn)行加工，只要工件的尺寸和不超出機(jī)器的容量.同時(shí)加工的工件稱為一批，其加工時(shí)間是批中最長的工件的加工時(shí)間.我們對(duì)兩種單臺(tái)批處理機(jī)排序的在線模型進(jìn)行了研究.變尺寸裝箱問題來源于運(yùn)輸公

2、司貨車的調(diào)度問題，不同貨車所需的費(fèi)用不同，如何安排才能使費(fèi)用盡可能少；而Open-end裝箱則來源于香港市民日常乘坐地鐵，市民的地鐵票在最后一次使用時(shí)允許金額不足而不需再追加繳費(fèi)，最少買幾張票就可以滿足市民的日常需求.我們研究了相應(yīng)的算法并對(duì)算法進(jìn)行了分析. 全文共分六章.第一章介紹組合優(yōu)化問題的一些基本概念、算法及其性能衡量，并簡要介紹本文的工作.其余五章可分為兩部分，第一部分由第二、三、四章組成，第二章對(duì)已有的批處理機(jī)排序問

3、題的歷史文獻(xiàn)以及相關(guān)的研究結(jié)果進(jìn)行詳細(xì)的綜述，三、四章則討論了兩種批處理機(jī)排序問題的模型；第二部分為第五、六章，分別討論了裝箱問題的兩個(gè)模型：變尺寸裝箱和Open-end裝箱. 單臺(tái)批處理機(jī)在線排序問題描述如下：給定一臺(tái)批處理機(jī)M，它的容量為B；又給定工件集L，每個(gè)工件有加工時(shí)間pj、到達(dá)時(shí)間rj和尺寸sj(0＜sj≤B，(A)i=1，2，…，n)，工件到達(dá)前信息未知.M能夠同時(shí)加工多個(gè)工件，只要這些工件的尺寸總和不超過B，這些

4、同時(shí)加工的工件稱為一批，它們同時(shí)開始加工，同時(shí)結(jié)束；加工過程中不允許中斷，也不允許放入或拿出工件；將批中最長工件的加工時(shí)間記為該批的加工時(shí)間.目標(biāo)是極小化最大完工時(shí)間(makespan).我們是最早對(duì)工件尺寸不同的在線模型進(jìn)行研究的.我們首先討論了工件加工時(shí)間相同的模型，給出了一個(gè)貪婪算法并證明其競(jìng)爭比為2；同時(shí)給出了一個(gè)改進(jìn)的算法，它的競(jìng)爭比為√3，大大縮小了與下界1+√5/2之間的差距.對(duì)工件尺寸不同的模型，我們對(duì)工件只有兩個(gè)到達(dá)時(shí)

5、間和有多個(gè)到達(dá)時(shí)間的情形給分別出了競(jìng)爭比119/44和7/2的在線算法，并證明當(dāng)工件滿足弱一致性條件時(shí)，它們的競(jìng)爭比分別改進(jìn)到2.4和3. 本研究最早提出了廣義的變尺寸裝箱模型.問題可以這樣描述：有M種箱子，每種箱子的尺寸和所需的費(fèi)用各不相同，數(shù)量無限，目標(biāo)是如何將所有物品都裝入箱子中，而使用到的箱子所花的總費(fèi)用盡可能小，如果箱子的尺寸與費(fèi)用是成正比的，那么就是原始的變尺寸裝箱問題，以前有學(xué)者對(duì)其進(jìn)行過研究.對(duì)原始的模型，我們分

6、析了幾個(gè)在線算法的絕對(duì)性能比，并給出了問題的下界；同時(shí)我們對(duì)允許自行設(shè)計(jì)箱子種類的情形，給出了最優(yōu)的箱子種類組合.對(duì)廣義的變尺寸裝箱問題，我們給出了絕對(duì)性能比不超過3的算法；當(dāng)滿足條件：最大的物品也能夠裝到最小的箱子里時(shí)，我們給出了絕對(duì)性能比不超過2的算法，這是目前變尺寸裝箱問題的最好結(jié)果. Open-end裝箱問題的模型是這樣描述的：只有一種箱子，數(shù)量無限，箱子中裝入最后一個(gè)物品時(shí)允許超出箱子的容量，目標(biāo)仍然是使用盡可能少的箱