平行機半在線排序問題.pdf

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

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

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

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

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