預(yù)知復(fù)合信息半在線排序問題算法研究.pdf

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

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

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

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

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

6、2k+1．同時針對兩臺機(jī)的情況設(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的算法．
　　 第六章研究了三臺機(jī)機(jī)器帶準(zhǔn)備時間的半在線Machine Covering問題P3，ri‖Cmin．對于預(yù)知所有工件加工時間總和和最大工