1、精品文檔 題 目 作業調度問題及算法分析 學院名稱： 計算機與信息工程學院 專業名稱： 計算機科學與技術 17 / 17名目?算法設計與分析?課程大作業1一動態規劃算法解決流水作業調度31、問題描述32、算法分析33. 算法的描述44、局部算法實現55. 運行結果66、時空效率分析6二貪心算法解多機調度問題61、問題描述62、算法分析73.局部算法實現74.計算簡單性分析85. 運行結果9三回溯法解決批作業調度問題91.問題描述92.算法思想103. 局部算法實現114.運行結果125.時間簡單性分析12四作業調度算法比較12五課程學習總結13摘要： 在現代企業中，作業調度已成為提高資源利用率

2、、從而提高企業運行效益的關鍵環節之一。把各個作業安排到車間現有的設備上，并確定它們的先后次序，這是一項簡單的工作 本文就作業調度排序問題進行了爭辯，通過對幾個經典作業調度算法的分析爭辯，總結了各個算法對作業調度的求解過程，并給出了每個算法的簡單度及性能分析。關鍵詞：作業調度；動態規劃；貪心算法；回溯法；一動態規劃算法解決流水作業調度1、問題描述 給定n個作業，每個作業有兩道工序，分別在兩臺機器上處理。一臺機器一次只能處理一道工序，并且一道工序一旦開頭就必需進行下去直到完成。一個作業只有在機器1上的處理完成以后才能由機器2處理。假設作業i在機器j上需要的處理時間為ti,j。流水作業調度問題就是要

3、求確定一個作業的處理挨次使得盡快完成這n個作業。2、算法分析 直觀上，一個最優調度應使機器M1沒有空閑時間，且機器M2的空閑時間最少。在一般狀況下，機器M2上會有機器空閑和作業積壓2種狀況。 在一般狀況下，機器M1開頭加工S中作業時，機器M2還在加工其他作業，要等時間t后才可利用。將這種狀況下完成S中作業所需的最短時間記為T(S,t)。流水作業調度問題的最優值為T(N,0)。由流水作業調度問題的最優子結構性質可知， 12 從公式1可以看出，該問題類似一個排列問題，求N個作業的最優調度問題，利用其子結構性質，對集合中的每一個作業進行試調度，在全部的試調度中，取其中加工時間最短的作業做為選擇方案。

4、將問題規模縮小。 公式2說明一般狀況下，對作業集S進行調度，在M2機器上的等待時間，除了需要等該部件在M1機器上完成時間，還要沖抵一局部原來的等待時間，假設沖抵已成負值，自然仍需等待M1將作業做完，所以公式取maxt-ai,0。3. 算法的描述 從分析可知，流水作業調度問題肯定存在滿足Johnson法那么的最優調度，且簡潔由下面的算法確定。流水作業調度問題的Johnson算法：1令；2將中作業依的非減序排列；將中作業依的非增序排列；作業接種作業構成滿足Johnson法那么的最優調度。4、局部算法實現int FlowShop(int n,int a,int b,int c)int i;Jobty

5、pe *d = new Jobtypen;for( i=0; ibi?bi:ai;/按Johnson法那么分別取對應的bi或ai值作為關鍵字di.job = ai=bi;/給符合條件aibi的放入到N1子集標記為truedi.index = i; BubbleSort(d,n);/對數組d按關鍵字升序進行排序 int j = 0,k = n-1; for( i=0; in; i+)if(di.job)cj+ = di.index;/將排過序的數組d，取其中作業序號屬于N1的從前面進入elseck- = di.index;/屬于N2的從后面進入，從而實現N1的非減序排序，N2的非增序排序 j =

6、 ac0;k = j+bc0;for( i=1; in; i+)j += aci;/M1在執行ci作業的同時，M2在執行ci-1號作業，最短執行時間取決于M1與M2誰后執行完k = jk?k+bci:j+bci;/計算最優加工時間delete d;return k;5. 運行結果 6、時空效率分析 算法Flowshop的主要計算時間花在對作業集的排序上。在這里，我們使用冒泡排序法(BubbleSort)，因此，在最壞狀況下算法FlowJob所需要的計算時間為。所需要的空閑明顯是。二貪心算法解多機調度問題 1、問題描述 多機調度問題要求給出一種作業調度方案，使所給的n個作業在盡可能短的時間內由m

7、臺機器加工處理完成。商定，每個作業均可在任何一臺機器上加工處理，但未完工前不允許中斷處理。作業不能拆分成更小的子作業。這個問題是NP完全問題，到目前為止還沒有有效的解法。對于這一類問題,用貪心選擇策略有時可以設計出較好的近似算法。 2、算法分析 貪心算法只需按挨次以數組方式供給各作業的加工時間和機器的臺數；求出作業的個數，假設小于機器臺數，就將作業逐個安排給就近的機器，所需要的加工時間，即為最長作業所需時間。 假設作業數大于機器臺數，將作業按加工時間的多少降序排序，以機器數建立最小堆，先將前m個作業安排給m個機器，最小堆頂是最小的元素即m個作業中加工時間最少的作業，將其移出并加上后續作業的加工

8、時間，再插入堆，這時會轉變原來的狀態，升到堆頂的機器加工總時間最少，它再移出加后續作業的加工時間，在插入堆，依此類推，直到全部作業結束。堆中的最大值就是完成全部作業所需的最短時間。 3.局部算法實現 typedef struct Node int ID, avail;manode; /ID 機器編號 avail 每次作業的初始時間 manode machineN; jobnode jobN; /* 找出下個作業執行機器 */ manode* Find_min(manode a, int m) manode* temp = &a0; for (int i = 1; im; i+) if (ai.

9、availavail) temp = &ai; return temp; /* 對作業時間由大到小進行排序 */ void Sort(jobnode t, int n) jobnode temp; for (int i = 0; ii; j-) if (jobj.timejobj - 1.time) temp = jobj; jobj = jobj - 1; jobj - 1 = temp; void main() for (i = 0; ijobi.time; jobi.ID = i + 1; printf(輸入機器數目(機器編號按輸入挨次處理)n); cinm; for (i = 0; i

10、m; i+)/給機器進行編號并初始化 machinei.ID = i + 1; machinei.avail = 0; putchar(n); if (n = m) printf(為每個作業安排一臺機器,可完成任務!n); return; Sort(job, n); for (i = 0; i %d 的時間段安排給作業: %dn, putchar(n); printf(該批作業處理完成所需加工時間為: %dn, temp); 4.計算簡單性分析當nm 時，全部作業可以一次支配給各機器，算法greedy需要o(1) 時間。當nm 時，排序耗時O(nlogn)。初始化堆需要O(m) 時間。關于堆的

11、removeMin和put運算共耗時O(nlogm),因此算法greedy 所需的計算時間為O(nlogn+nlogm)=O(nlogn)。5. 運行結果三回溯法解決批作業調度問題 1.問題描述 輸入：1. 任務數N2. 機器數M3. 隨機序列長度ti,其中ti=x表示第i個任務完成需要時間單位x，輸出：1. 開銷時間besttime，表示最正確調度需要時間單位2. 最正確調度序列bestx，其中bestxi=x，表示將第i個任務安排給第x個機器執行。2.算法思想 解空間的表示：一個深度為N的M叉樹。ti:第i個任務的時間xi=j:當前輸出結果Resi=j:表示第i個任務要運行在第j臺機器上t

12、ime_machinei:第i個機器上的運行時間根本思路： 1、搜尋從開頭結點根結點動身，以DFS搜尋整個解空間。2、每搜尋完一條路徑那么記錄下time_min和Resi序列，開頭結點就成為一個活結點， 同時也成為當前的擴展結點。在當前的擴展結點處向縱深方向移至一個新結點， 并成為一個新的活結點，也成為當前擴展結點。 3、假設在當前的擴展結點處不能再向縱深方向擴展，那么當前擴展結點就成為死結點。此時，應往回移動回溯至最近的一個活結點處，并使這個活結點成為當前的擴展結點；直至找到一個解或全部解。3. 局部算法實現bool placetest(int k)int time_max_K = time

13、_machine1;for(int i=2;i time_max_K )time_max_K = time_machinei;if(time_max_K time_min)return false;elsereturn true; void Backtrack(int k,int t,int x) if(k N )int time_max_K = time_machine1;for(int i=2;i time_max_K )time_max_K = time_machinei;if(time_max_Ktime_min)time_min = time_max_K;for(int i=1;i=

14、N;i+)Resi = xielsefor(int i=1;i=K;i+)xk = i;/將第k個任務放到第i個機器上面if( placetest(k) )time_machinei += tk;Backtrack(k+1,t,x);time_machinei -= tk;4.運行結果5.時間簡單性分析由于沒有使用限界函數進行優化，算法時間和空間簡單度呈指數級增長。所以該算法不適合較大規模的計算。藍線表示機器數肯定M=3時，n增大時求解最正確調度對所消耗的時間，該趨勢隨著指數增加。四作業調度算法比較 在流水作業調度中，Johnson算法這是在只有兩臺設備狀況下的最優排序算法，同時說明工件的第一

15、道工序和最終一道工序的加工時間對排序的影響是主要的。 貪心算法只需按挨次以數組方式供給各作業的加工時間和機器的臺數；求出作業的個數，假設小于機器臺數，就將作業逐個安排給就近的機器，所需要的加工時間，即為最長作業所需時間簡單度為O(nlogn)。 回溯算法解決批作業調度問題與前面兩個問題不同，前兩個是求全部作業在M2機器上加工完成的最終時間，而這里要求的是求全部作業在機器M2上完成處理時間的總和到達最小。這種調度算法可用于計算加工費用。批處理作業調度問題屬于排列樹的解空間問題，因此時間簡單度為(n!) 五課程學習總結 算法分析與設計是一門格外重要的課程，很多問題的解決，程序的編寫都要依靠它，算法的學習對于培育一個人的規律思維力量是有極大掛念的，它可以培育我們養成思考分析問題，解決問題的力量。但是算法的學習同時也需要較強的理解力量，有些算法程序不易讀懂，這時需要在理解問題的本質上對算法程序進行解讀。在對一個問題進行算法設計時，要了解問題