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

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

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

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

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

6、線排序中，因?yàn)槿狈ξ磥?lái)工件的信息，所以利用重啟可以幫助決策者得到更優(yōu)良的在線算法.
　　 我們用競(jìng)爭(zhēng)比來(lái)衡量一個(gè)在線算法的優(yōu)良程度.對(duì)于一個(gè)最小化目標(biāo)函數(shù)的在線排序問(wèn)題，我們說(shuō)在線算法A是ρ-競(jìng)爭(zhēng)的（ρ>1），如果對(duì)于任意的實(shí)例Ⅰ，都有A（Ⅰ）≤ρ.opt（Ⅰ），其中A（Ⅰ）是在線算法A生成的目標(biāo)函數(shù)值，opt（Ⅰ）是最優(yōu)的離線算法生成的目標(biāo)函數(shù)值.（對(duì)最大化目標(biāo)函數(shù)的在線排序問(wèn)題，如果A是ρ-競(jìng)爭(zhēng)的（ρ<1），則有A（Ⅰ）≥ρ

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

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

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

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

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