預知復合信息半在線排序問題算法研究.pdf

1、機器排序和機器覆蓋經(jīng)常在實際運用中出現(xiàn)，比如在網(wǎng)絡通信中通道分配均衡問題，大型的并行計算問題，柔性生產(chǎn)系統(tǒng)中任務排序問題，等等．這篇論文主要研究了m臺平行機的復合半在線排序問題．考慮了半在線機器覆蓋問題，這個問題最先由Deuermeyer等提出．應用于維持飛行器燃氣渦輪發(fā)動機的運轉(zhuǎn)和基于提高網(wǎng)絡服務質(zhì)量(quality of service，簡稱QoS)而產(chǎn)生的帶寬分配．同時還考慮了最先由Azar和Regev提出的在線Bin Stret

2、ching問題，以及機器帶準備時間的半在線排序問題．這些問題都具有著一定的現(xiàn)實背景，針對每個問題都分析了下界并設(shè)計了相應的半在線算法，有的算法是最優(yōu)算法．全文共分為七章．
　　 第一章是緒論部分，主要介紹一些組合優(yōu)化以及算法設(shè)計與分析方面相關(guān)的概念和預備知識．
　　 第二章簡要綜述了近年來與本文相關(guān)的在線與半在線平行機排序問題的若干成果，并簡單說明了一下本文的一些主要結(jié)果．
　　 第三章研究了兩臺同型平行機半在線

3、排序問題，也即事先預知復合信息：所有工件大小總和和最大工件大小的半在線排序問題(P2∣sum＆max∣Cmax)．盡管P2∣sum＆max∣Cmax具有競爭比為6/5的最優(yōu)算法，但這是針對最壞情況進行分析所得到的結(jié)果，并不理想，其實很多時候能夠得到競爭比更好的算法．因此這章主要分析了P2∣sum＆max∣Cmax當參數(shù)r＝2pmax/T取不同的值時間題的下界并設(shè)計了相應的算法，下界與算法的競爭比均是關(guān)于r的函數(shù)．當r=1/2時有競爭比為

4、7/6的最優(yōu)算法．當7/13≤r≤1時給出了最優(yōu)算法，算法的競爭比為
　　 第四章主要研究了預知工件大小按非增排列到達，目標為極小化stretchfactor的半在線Bin Stretching問題．也即預知工件大小按非增排列到達和離線狀態(tài)下最優(yōu)目標值C*，目標為Gmax(makespan)的平行機排序問題．對于m臺機器的情形，證明了問題的下界至少是10/9，并設(shè)計了競爭比至多為1+m—1/4m—2的半在線算法．對于P3∣opt

5、＆decr∣Cmax，則改進了算法，給出競爭比至多為7/6的算法．
　　 第五章主要研究了已知工件大小上界為C*/k的平行機排序問題，根據(jù)是否已知最優(yōu)目標值的不同模型，分別針對兩個目標Gmax和Cmin進行了分析．對于Pm∣k—bounded∣Cmax，證明了當m≤k+1時LS算法為最優(yōu)算法，競爭比為1+m—1/mk，當m＞k+1時下界至少為1+1/k+1．對于Pm∣opt＆k—bounded∣Cmax，證明了下界至少為1+1/

6、2k+1．同時針對兩臺機的情況設(shè)計了競爭比為1+1/2k+1的最優(yōu)算法OB2．對于Pm∣k—bounded∣Cmin，證明了LS算法為最優(yōu)算法，競爭比為mk/mk—m+1．對于Pm∣opt＆k—bounded∣Cmin，證明了下界至少為1+1/2k，并設(shè)計了競爭比為1+m—1/mk的算法．
　　 第六章研究了三臺機機器帶準備時間的半在線Machine Covering問題P3，ri‖Cmin．對于預知所有工件加工時間總和和最大工