通訊網(wǎng)絡(luò)中排序問題的若干在線和高性能算法.pdf

1、本文主要研究來源于通訊網(wǎng)絡(luò)的排序(scheduling)問題。我們首先研究的是并行工件(paralleljobs)的排序，每個(gè)并行工件可能需要一臺(tái)或多臺(tái)機(jī)器同時(shí)加工這個(gè)工件。我們考慮機(jī)器之間存在的各種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對(duì)排序結(jié)果的影響。具體的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可以是：完全圖結(jié)構(gòu)(PRAM)，線(Line)，網(wǎng)格(Mesh)，超立方體(Hypercube)等等。若干機(jī)器可以同時(shí)加工一個(gè)工件僅當(dāng)這些機(jī)器構(gòu)成的生成子網(wǎng)絡(luò)是連通的。也就是說，僅當(dāng)機(jī)器間存在

2、通訊路徑時(shí)才能夠共同工作，而且這些機(jī)器必須滿足工件所要求的數(shù)目和拓?fù)浣Y(jié)構(gòu)。除了機(jī)器之間具有網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)之外，我們對(duì)工件的各種不同的在線到達(dá)模式進(jìn)行分類和研究，如工件按先后序到達(dá)(ondependencies)，工件按釋放時(shí)間到達(dá)(overtime)，工件按列表逐個(gè)到達(dá)(overlist)。我們的目標(biāo)是對(duì)給定的工件集合進(jìn)行排序以滿足各種約束條件并使某種目標(biāo)值最優(yōu)化。常見的目標(biāo)函數(shù)有極小化最大完工時(shí)間(minimizethemakespan

3、)或者是最大化輸出量(maximizethethroughput)。 我們對(duì)這些排序問題提出了相應(yīng)的在線算法，并采用國(guó)際上通用的算法評(píng)價(jià)標(biāo)準(zhǔn)競(jìng)爭(zhēng)比(competitiveratio)來衡量、分析給出的算法。通過研究“壞的”實(shí)例，我們給出各種問題的下界(lowerbound)。從各種模型的分析來看，不同的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和工件的不同在線到達(dá)模式均對(duì)最后的排序結(jié)果產(chǎn)生重要的影響。本文對(duì)每個(gè)具體問題如何設(shè)計(jì)有效算法進(jìn)行了深入的研究，從而達(dá)

4、到對(duì)已有算法的重要改進(jìn)和對(duì)新問題提出高性能的算法。同時(shí)我們還研究，事先獲得工件的部分信息對(duì)算法的影響。對(duì)于并行工件的排序問題，我們還研究了幾個(gè)離線模型，即工件的所有信息都已知。我們或者證明該問題是多項(xiàng)式可解的或者是對(duì)NP難問題給出多項(xiàng)式時(shí)間近似方案。 我們還研究一些經(jīng)典排序問題，這里每個(gè)工件只需要一臺(tái)機(jī)器來加工。我們首先考慮的是機(jī)器總加工時(shí)間可擴(kuò)展的排序問題(schedulingwithextendableworkingtime

5、problem)。每臺(tái)機(jī)器有一個(gè)初始設(shè)定的正規(guī)加工時(shí)間，但機(jī)器的總加工時(shí)間可以根據(jù)需要決定是否延長(zhǎng)。每臺(tái)機(jī)器的工作時(shí)間定義為正規(guī)加工時(shí)間和總加工時(shí)間(真正加工時(shí)間)之間的較大值。我們的目標(biāo)是安排所有的工件，使得所有機(jī)器工作時(shí)間的總和最小。我們分別對(duì)所有的機(jī)器都有相同的正規(guī)加工時(shí)間，和每個(gè)機(jī)器的正規(guī)加工時(shí)間可以不相同的情況進(jìn)行深入的研究。 最后，我們討論經(jīng)典排序問題中，事先獲得工件的部分信息的半在線模型。我們已知最后加工的工件的加

6、工時(shí)間最長(zhǎng)，并且當(dāng)最后一個(gè)工件到達(dá)的時(shí)候，將被通知這就是最后一個(gè)工件。我們分別對(duì)小數(shù)目的平行機(jī)和同類機(jī)進(jìn)行了探討。 全文共分九章。第一章介紹本文研究的問題、模型及其應(yīng)用背景，以及問題之間的分類，并簡(jiǎn)要介紹本文的工作。一些基本概念，基礎(chǔ)知識(shí)和分析問題的工具也在本章中介紹。第九章總結(jié)本文詳細(xì)的成果以及對(duì)未來研究方向的展望。其余七章分成兩部分。第一部分由二到六章構(gòu)成，主要研究并行工件的排序問題。第二部分由第七、第八章組成，探討一些與經(jīng)

7、典排序相關(guān)的問題。具體說明如下： 第二章詳細(xì)綜述并行工件在線排序的歷史文獻(xiàn)以及相關(guān)問題的研究結(jié)果。 第三章研究的問題是：在線帶先后序約束(ondependencies)的并行工件在二維網(wǎng)格上的排序問題。所有工件的加工時(shí)間為單位時(shí)間，每個(gè)并行工件需要一組在二維子網(wǎng)格上的機(jī)器同時(shí)加工。工件之間存在先后序約束。一個(gè)并行工件到達(dá)并可以開始加工當(dāng)且僅當(dāng)這個(gè)工件的所有前序工件都已經(jīng)完工。但是，工件之間的這種序的關(guān)系事先不知道。這意味

8、著，不同策略的安排將可能導(dǎo)致不同的工件到達(dá)順序。我們研究的目標(biāo)是極小化最大完工時(shí)間。我們?cè)O(shè)計(jì)了一個(gè)有效的在線算法，其競(jìng)爭(zhēng)比不超過5.25。同時(shí)我們也證明了，任何在線算法的競(jìng)爭(zhēng)比都不可能小于3.859。這個(gè)結(jié)果改進(jìn)了原有的下界3.25和上界46/7。另外，當(dāng)并行工件可以旋轉(zhuǎn)90度的情況。我們證明了這個(gè)問題的上界最多為4.25，同時(shí)也證明了，不存在在線算法其競(jìng)爭(zhēng)比小于3.535。 第四章討論并行工件列表在線(overlist)的排序

9、問題。并行工件的到達(dá)順序已事先安排好在一個(gè)列表中。但是，安排者并不知道這個(gè)已經(jīng)安排好的順序，也不知道到底有多少個(gè)工件。當(dāng)且僅當(dāng)當(dāng)前工件已經(jīng)安排好下一個(gè)工件才到達(dá)(如果有的話)。工件一旦安排好之后，就不允許改動(dòng)。本章討論的問題基于機(jī)器的網(wǎng)絡(luò)結(jié)構(gòu)是完全圖結(jié)構(gòu)，也就是可以忽略網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，而只需要滿足相應(yīng)的機(jī)器數(shù)即可。這個(gè)問題的目標(biāo)仍然是極小化最大完工時(shí)間。我們給出了一個(gè)競(jìng)爭(zhēng)比為7的算法，極大的改進(jìn)了原先的競(jìng)爭(zhēng)比為12的算法。我們進(jìn)一步研究

10、三種特殊情況：工件按加工時(shí)間非升的順序到達(dá)；工件按工件的尺寸(所需的機(jī)器數(shù))非升的順序到達(dá)；工件的最大加工時(shí)間事先已知。對(duì)第一種情況，我們對(duì)貪婪算法進(jìn)行了分析并證明其上界最多為2。對(duì)第二種情況，我們也對(duì)貪婪算法進(jìn)行了分析并證明這個(gè)算法的競(jìng)爭(zhēng)比在2.75與2.5之間。對(duì)最后一種情況，貪婪算法就不再有效，我們給出了一個(gè)算法其緊界為4。最后，我們研究工件在加工當(dāng)中允許中斷，當(dāng)每個(gè)工件到達(dá)的時(shí)候，我們要決定何時(shí)開始加工該工件，是否對(duì)這個(gè)工件中斷

11、以及每次中斷的時(shí)刻，安排好之后也就不再允許修改。據(jù)我們所知，這是第一個(gè)研究可中斷并行工件列表在線排序問題的工作。我們給出了一個(gè)競(jìng)爭(zhēng)比為2-1/m的在線算法。 第五章研究可延展的并行工件(malleableparalleljob)排序問題。每個(gè)工件的加工時(shí)間是所使用機(jī)器數(shù)的函數(shù)。每個(gè)工件加工所需的機(jī)器數(shù)事先并不固定，但在安排的時(shí)候必須確定，而且一旦確定了，就不能再更改。機(jī)器之間的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)為二維網(wǎng)格。我們考慮并行工件在滿足單調(diào)性

12、(monotonic)的情況下的排序。這里單調(diào)性指的是一個(gè)工件的加工時(shí)間在機(jī)器數(shù)目減少的情況下，其加工時(shí)間不會(huì)變短，而它的功(指的是機(jī)器數(shù)乘加工時(shí)間)不會(huì)增加。我們的目標(biāo)是極小化最大完工時(shí)間。對(duì)這個(gè)問題，當(dāng)機(jī)器數(shù)目為充分大的時(shí)候我們給出一個(gè)漸近完全多項(xiàng)式方案(AFPTAS)。也就是，對(duì)于任意給定的一個(gè)小量ε，我們給出的算法都能在多項(xiàng)式時(shí)間內(nèi)保證算法所得的解不超過最優(yōu)解的1+ε倍(加上一個(gè)常數(shù))。 第六章我們研究問題的目標(biāo)是極大化

13、輸出量(throughput)，即極大化完工工件的個(gè)數(shù)。首先我們討論的是在超立方體上的排序問題，每個(gè)并行工件均需一個(gè)子超立方體來同時(shí)加工。并行工件釋放時(shí)間(releasetime)相同，但是有各自的交工期(duedate)。容易證明這個(gè)問題是NP難的。因此，我們討論了單位加工時(shí)間的情況。證明該問題是P問題。我們進(jìn)一步討論一個(gè)公開問題，即并行工件在兩臺(tái)機(jī)上的排序問題，工件有各自的釋放時(shí)間，同時(shí)每個(gè)工件的加工時(shí)間為單位時(shí)間，其目標(biāo)仍是極大化

14、輸出量。我們證明了該問題也是P問題。 第七章討論機(jī)器加工時(shí)間可擴(kuò)展的排序問題。給定m臺(tái)機(jī)器以及每臺(tái)機(jī)器的正規(guī)加工時(shí)間b1，b2，…，bm。機(jī)器的總加工時(shí)間可以根據(jù)需要決定是否延長(zhǎng)。每臺(tái)機(jī)器的工作時(shí)間定義為正規(guī)加工時(shí)間和總加工時(shí)間(即安排在該機(jī)器上的所有工件的加工時(shí)間之和)之間的較大值。工件是按列表在線到達(dá)的。目標(biāo)是安排所有的工件在給定的機(jī)器上，使得所有機(jī)器工作時(shí)間的總和最小。對(duì)于所有機(jī)器的正規(guī)加工時(shí)間相同情況，我們研究了機(jī)器數(shù)目

15、較少的的情況，詳細(xì)深入的分析已有算法并證明其算法具體的競(jìng)爭(zhēng)比。對(duì)于兩臺(tái)機(jī)器，我們給出了競(jìng)爭(zhēng)比為7/6的最優(yōu)在線算法。對(duì)于三臺(tái)機(jī)器，我們給出了問題的下界(17+√577)/36和上界7/6。對(duì)于四臺(tái)機(jī)器，我們給出了下界9/8，并證明其上界不超過19/16。接著，我們對(duì)機(jī)器的正規(guī)加工時(shí)間不同的情況進(jìn)行了研究。假設(shè)最小的正規(guī)加工時(shí)間不小于最大的工件加工時(shí)間。對(duì)任意的m臺(tái)機(jī)器，我們對(duì)貪婪算法進(jìn)行詳細(xì)的分析，并完全刻劃了其緊界與機(jī)器數(shù)m之間的關(guān)系

16、。然后，我們對(duì)兩和三臺(tái)機(jī)器的情況，給出了改進(jìn)的算法以及問題的下界。在沒有上述假設(shè)的情況下，我們對(duì)兩臺(tái)機(jī)器進(jìn)行了研究。最后，我們對(duì)加工工件是并行工件而且是離線的情況進(jìn)行了研究，提出了一個(gè)算法并證明其緊界是2。 第八章我們研究經(jīng)典排序問題中的半在線模型。工件是按列表在線。同時(shí)我們已知最后加工的工件的加工時(shí)間最長(zhǎng)，并且當(dāng)最后一個(gè)工件到達(dá)的時(shí)候，將被通知這就是最后一個(gè)工件。我們分別對(duì)小數(shù)目的同型機(jī)和同類機(jī)進(jìn)行了探討。目標(biāo)是極小化最大完工