一致機(jī)上最小化時(shí)間表長的在線排序問題.pdf

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

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

3、加工時(shí)間均為1。分批指的是一臺(tái)分批機(jī)器可以一批同時(shí)加工至多b個(gè)工件。批的加工時(shí)長由該批中的最長工件決定。按照批的容量，可以分為兩類平行分批排序：有界的情形和無界的情形。這里我們研究批容量無界的情形。我們給出競爭比為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臺(tái)一致機(jī)上的分層可中斷在線排序問題。Q2|online-list，g=2，pmtn|Cmax,工件是按序列到達(dá)，即后一個(gè)工件的信息只有在前一個(gè)工件排序之后才能知道。第一臺(tái)機(jī)器的速度為1,第二臺(tái)機(jī)器的速度為v。該問題所研宄的工件分為兩層，對(duì)于Jj工件來說，gj=1表示該工件只能在第一臺(tái)機(jī)器上加工，gj=2表示該工件可以在任意一臺(tái)機(jī)器上加工。進(jìn)一步，排在速度為1的機(jī)器上的工件的實(shí)際加工時(shí)間為該工件自身的加工時(shí)間，而排在速度為v的機(jī)器

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