平行機(jī)半在線排序問(wèn)題.pdf

1、本文主要考慮平行機(jī)半在線排序問(wèn)題.本文首先簡(jiǎn)要介紹了排序問(wèn)題、競(jìng)爭(zhēng)比分析和近似算法等基本概念，總結(jié)了近年來(lái)出現(xiàn)的各個(gè)半在線模型及其有關(guān)結(jié)果. 第二章考慮已知工件最大加工時(shí)間的半在線模型，目標(biāo)為極大化最小機(jī)器負(fù)載.主要討論兩個(gè)問(wèn)題：1三臺(tái)同類機(jī)的情形，我們給出min3算法并且證明此算法的競(jìng)爭(zhēng)比為max{r+1，3s+r+11+r+s}.min3算法是緊的且當(dāng)1≤s≤2、r=1時(shí)是最優(yōu)的.2m臺(tái)特殊同類機(jī)問(wèn)題，我們給出Cmin算法及

2、其競(jìng)爭(zhēng)比max{m-1，ms+m-1}，并證明Cmin算法是緊的且當(dāng)1≤s≤(m-1)(m-2)(m≥3)時(shí)是最優(yōu)的. 第三章考慮已知工件最大加工時(shí)間的半在線問(wèn)題，目標(biāo)為極小化機(jī)器最大負(fù)載.主要討論四個(gè)問(wèn)題：1對(duì)于兩臺(tái)同類機(jī)的問(wèn)題，我們給出競(jìng)爭(zhēng)比分別為2(s+1)s+2(1≤s≤2)和s+1(s＞2)的Qmax2算法，并且證明此算法是緊的且相應(yīng)某些s的特殊值是最優(yōu)的.2對(duì)于三臺(tái)同類機(jī)半在線問(wèn)題，我們給出Qmax3算法并證明此算法

3、的競(jìng)爭(zhēng)比不大于2(r+s+1)2r+s(1＜s≤2)和r+2s+1(s＞2)且嚴(yán)格小于2.3對(duì)于三臺(tái)特殊同類機(jī)問(wèn)題，給出Qmax3t算法并證明其競(jìng)爭(zhēng)比不大于s+2(1≤s≤2)和s+2s(s＞2)且恒小于2.4最后我們考慮m臺(tái)同型機(jī)問(wèn)題，給出一個(gè)競(jìng)爭(zhēng)比為2m-3的Cmax算法并證明此算法對(duì)任何m≥3是緊的. 第四章中，我們考慮已知工件總加工時(shí)間的兩臺(tái)同類機(jī)半在線問(wèn)題，目標(biāo)為極大化最小機(jī)器負(fù)載.我們給出Q2min算法并證明此算法的

4、競(jìng)爭(zhēng)比小于2+√22，而此問(wèn)題競(jìng)爭(zhēng)比的下界為1+√52.同時(shí)證明當(dāng)s=1+√52時(shí)Q2min算法最優(yōu)的. 在第五章中，我們考慮帶機(jī)器準(zhǔn)備時(shí)間的已知工件總加工時(shí)間的半在線問(wèn)題.第一節(jié)考慮P2，ri｜sum｜Cmin問(wèn)題，給出Prsum算法并證明此算法的競(jìng)爭(zhēng)比為32且是最優(yōu)算法.在第二節(jié)則考慮Q2，ri｜sum｜Cmax問(wèn)題，給出Qrmax算法并證明此算法的競(jìng)爭(zhēng)比為√2；同時(shí)給出此問(wèn)題的一個(gè)下界. 第六章我們首先引進(jìn)一個(gè)新的

5、半在線術(shù)語(yǔ)：半在線模型的松弛，然后我們介紹一個(gè)新的半在線模型：已知工件最大加工時(shí)間在某一區(qū)域內(nèi)，即knownlargestjobinterval模型.第一節(jié)考慮P2｜knownlargestjobinterval｜Cmax問(wèn)題，我們給出Pinterval算法及其競(jìng)爭(zhēng)比，并證明此競(jìng)爭(zhēng)比是緊的且與最優(yōu)競(jìng)爭(zhēng)比的誤差不超過(guò)433.第二節(jié)考慮P2｜knownlargestjobinterval｜Cmin問(wèn)題，我們給出Pinterval算法的競(jìng)爭(zhēng)比