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

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

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

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

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

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

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