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

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

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

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

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

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

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