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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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