一致機上最小化時間表長的在線排序問題.pdf

1、在離線排序問題中，機器的性質是多樣的，其中研宄比較多的主要為恒同機、一致機以及無關機。所謂恒同機是指機器的速度是一樣的，工件的加工時間只與工件自身的長度有關，而與機器無關；一致機是指機器的速度是不同的，一個工件的加工時間既與工件自身有關又與所排的機器速度有關;無關機是指機器的速度與所加工的工件也存在著聯(lián)系.
　　本文研究一致機上的在線排序問題，工件在到達之前的所有信息都是未知的。在線包括按時到達和按序列到達。按時到達即每個工件都有

2、各自的到達時間，按序列到達即工件是一個接著一個到的，下一個工件只有在前一個工件排序之后才能到達。每個工件一旦到達，工件的所有信息就變成已知。
　　在第二章中，研究了m臺一致機上批容量無界的工件長度為1在線排序問題Qm|online，p-batch,b=∞,pj=1|Cmax(m≥2),其中前m-1臺機器的速度為1,最后一臺機器的速度為v(0< v<1)。在線指的是工件按時間到達，在工件到達之前，該工件的所有信息是未知的。每個工件的

3、加工時間均為1。分批指的是一臺分批機器可以一批同時加工至多b個工件。批的加工時長由該批中的最長工件決定。按照批的容量，可以分為兩類平行分批排序：有界的情形和無界的情形。這里我們研究批容量無界的情形。我們給出競爭比為1+α1,0＜v≤1/2,1+α={1+α2,1/2＜v≤1.的最好可能的在線算法。其中α1滿足等式（1+α)m=2+α;α2滿足等式（1+α)(m+1)=(1/x-1)(1+α)(m-1)+2+α。
　　在第三章中，我

4、們考慮2臺一致機上的分層可中斷在線排序問題。Q2|online-list，g=2，pmtn|Cmax,工件是按序列到達，即后一個工件的信息只有在前一個工件排序之后才能知道。第一臺機器的速度為1,第二臺機器的速度為v。該問題所研宄的工件分為兩層，對于Jj工件來說，gj=1表示該工件只能在第一臺機器上加工，gj=2表示該工件可以在任意一臺機器上加工。進一步，排在速度為1的機器上的工件的實際加工時間為該工件自身的加工時間，而排在速度為v的機器

5、上的工件的加工時間等于該工件的標準加工時間與機器速度的比值。在任意時刻，每個機器最多只能加工一個工件，每個工件最多只能被一臺機器加工?？芍袛嗉垂ぜ梢苑殖扇舾蓚€片段在不重疊的時間內(nèi)在不同的機器上加工。這里所研宄的可中斷是不允許有空閑時間的，后到達的工件必須緊著前面排好的工件去排。在實際應用中的一些情況下，可能不允許有空閑時間是必須的，這也使得本文有研宄價值。本章對于當v≤1時給出競爭比的下界為1+ v/(v+1),當 v≤1且滿足v3+