平行批在線排序問題.pdf

1、在線排序是現(xiàn)代排序的一個重要組成部分.在經(jīng)典的離線排序問題中，我們總是假設(shè)決策者在做決策之前已經(jīng)獲知所有工件的信息.事實(shí)上，在實(shí)際生產(chǎn)過程中很多時候決策者在沒有獲得所有工件信息之前就必須做出決策.于是出現(xiàn)了在線排序.人們通常把在線排序問題分為三類：
　　 列表在線（online-list）：工件是排成一個序列到達(dá)的.前面的工件必須被安排到機(jī)器上后面的工件才會被釋放出來.工件一旦被釋放，工件的信息即被獲知.工件的安排方式一旦確定就

2、不可以再改變.
　　 時間在線（online-time）：工件是隨著時間到達(dá)的.前面到達(dá)的工件即使沒有被安排也不會影響后面工件的到來.工件的信息在工件的到達(dá)時刻才能獲知，工件在到達(dá)之前不可以被安排.工件被安排之后不能再改變.
　　 不可預(yù)測的時間在線（online-time-nclv）：工件是隨著時間到達(dá)的.工件的加工時間只有在工件完工之后才可獲知，而在工件的到達(dá)時刻無法得知或預(yù)測（nonclairvoyance）.工件

3、在到達(dá)之前不可以被安排，一旦安排就不可以改變.
　　 在本學(xué)位論文中，我們主要研究的是時間在線排序問題.我們考慮一臺或兩臺平行批處理機(jī)的排序模型.平行批處理問題起源于半導(dǎo)體制作工業(yè)、制平行批鞋業(yè)、金屬鑄造工業(yè)等方面.在后文中我們將會詳細(xì)敘述.一臺平行批處理機(jī)在不超過批容量的情形下，可以同時加工多個工件.批的加工時間是由該批中最長的工件確定的.同一批的工件具有相同的開工時間和相同的完工時間.在本文所研究的排序模型中，我們均假設(shè)批容

4、量是無界的，即機(jī)器可以同時加工任意多個工件.同時，我們還假設(shè)存在多個不可相容的工件組或者假設(shè)批是允許有限次重啟的.
　　 不可相容的工件組是指，每個工件可能屬于不同的組，組與組之間是不可相容的（比如，不同的組具有不同的化學(xué)性質(zhì)）.因此，不同組的工件不可以被安排在同一批加工.
　　 考慮到重啟是一種有限的資源或者重啟會帶來一定的負(fù)面影響，因此我們提出了有限次重啟的概念.批允許有限次重啟是指，如果一批中不包含有已經(jīng)被重啟過的

5、工件，就可以被重啟.批重啟之后，批中的工件被釋放出來，成為各自獨(dú)立的未加工工件.再次加工被重啟過的工件時必須重新開始加工，并且加工過程不可以被打斷直到其完工.
　　 重啟與中斷是兩個不同的概念.中斷的工件再次被加工時是接著已經(jīng)被加工的部分繼續(xù)加工的；而重啟的工件再次被加工時是從頭開始加工的，前面已經(jīng)加工的部分全部作廢.重啟只有在在線排序問題中才有意義.因?yàn)樵陔x線排序中，我們完全可以等到適當(dāng)?shù)臅r候再加工工件，而不用做無用功.而在在

6、線排序中，因?yàn)槿狈ξ磥砉ぜ男畔ⅲ岳弥貑⒖梢詭椭鷽Q策者得到更優(yōu)良的在線算法.
　　 我們用競爭比來衡量一個在線算法的優(yōu)良程度.對于一個最小化目標(biāo)函數(shù)的在線排序問題，我們說在線算法A是ρ-競爭的（ρ>1），如果對于任意的實(shí)例Ⅰ，都有A（Ⅰ）≤ρ.opt（Ⅰ），其中A（Ⅰ）是在線算法A生成的目標(biāo)函數(shù)值，opt（Ⅰ）是最優(yōu)的離線算法生成的目標(biāo)函數(shù)值.（對最大化目標(biāo)函數(shù)的在線排序問題，如果A是ρ-競爭的（ρ<1），則有A（Ⅰ）≥ρ

7、.opt（Ⅰ）.）由此可見，ρ的值越趨于1，則在線算法得到的目標(biāo)函數(shù)值就越趨于離線情形下最優(yōu)的目標(biāo)函數(shù)值，在線算法也更優(yōu)良.對某個在線排序問題來說，如果它的一個在線算法的競爭比與該問題的競爭比的下界相吻合，那么我們就說該算法是最好可能的在線算法，這也就意味著該在線排序問題徹底被解決.
　　 本學(xué)位論文中我們主要考慮了六個問題.第二章和第三章研究的是單臺平行批處理機(jī)帶有不可相容的工件組的在線排序問題；第四章和第五章研究的是兩臺平行

8、批處理機(jī)的問題；后面兩章我們主要探討了允許有限次重啟的平行批排序問題，包括單機(jī)和平行機(jī).具體地，主要結(jié)果如下：
　　 1.在第二章中，我們研究了帶有兩個不可相容的工件組的單臺平行批處理機(jī)在線排序問題.目標(biāo)函數(shù)是最小化最大完工時間.我們首先證明了該問題任意在線算法的競爭比的下界是√17+3/4≈1.7808，然后我們給出了一個競爭比是√17+3/4的最好可能的在線算法.
　　 2.在第三章中，在第二章研究的基礎(chǔ)上我們擴(kuò)展了

9、已有的結(jié)果.我們假設(shè)不可相容的工件組的個數(shù)f是一個輸入的數(shù).我們找到了最好可能的在線算法的競爭比是f的一個表達(dá)式，即1+√4f+1-1/2f.當(dāng)f≤2時，得到的結(jié)果與已知結(jié)果相同.需要說明的是，本章我們給出的算法是一個有別于已知的新的在線算法.
　　 3.在第四章中，對于兩臺平行批處理機(jī)，目標(biāo)函數(shù)是最小化最大完工時間的在線排序問題，我們首先證明了問題的競爭比的下界是√2，然后我們給出了一個最好可能的新的在線算法，證明了算法的競爭

10、比與下界吻合.
　　 4.在第五章中，我們探討了帶有兩個工件組的兩臺平行批處理機(jī)在線排序問題.目標(biāo)函數(shù)足最小化最大完工時間.我們用對手策略證明了該問題任意在線算法的競爭比的下界是√5+1/2≈1.618.繼而，我們給出了一個最好可能的在線算法，證明的算法的競爭比就是√5+1/2.
　　 5.在第六章中，我們主要研究的是單臺平行批處理機(jī)，批允許有限次重啟的最小化最大完工時間的在線排序問題.我們首先證明該問題競爭比的下界是3

11、/2，然后給出了個競爭比是3/2的最好可能的在線算法.在不允許重啟的情形下，最好可能的在線算法是√5+1/2-競爭的.因此批允許重啟使得我們得到了史好可能的在線算法.
　　 6.在第七章中，我們研究的是允許有限次重啟的兩臺半行批處理機(jī)在線排序問題.目標(biāo)函數(shù)是最小化最大完工時間.在不允許重啟的情形下，最好可能的在線算法是√2-競爭的.我們證明當(dāng)批允許有限次重啟時，任意在線算法競爭比的下界約為1.298，在second-restar