算法設(shè)計(jì)與課程大作業(yè)

1、算法分析課程設(shè)計(jì) 題 目 作業(yè)調(diào)度問題及算法分析 學(xué)院名稱： 計(jì)算機(jī)與信息工程學(xué)院 專業(yè)名稱： 計(jì)算機(jī)科學(xué)與技術(shù) 目錄算法設(shè)計(jì)與分析課程大作業(yè)1一動(dòng)態(tài)規(guī)劃算法解決流水作業(yè)調(diào)度31、問題描述32、算法分析33. 算法的描述44、部分算法實(shí)現(xiàn)55. 運(yùn)行結(jié)果66、時(shí)空效率分析6二貪心算法解多機(jī)調(diào)度問題61、問題描述62、算法分析73.部分算法實(shí)現(xiàn)74.計(jì)算復(fù)雜性分析85. 運(yùn)行結(jié)果9三回溯法解決批作業(yè)調(diào)度問題91.問題描述92.算法思想103. 部分算法實(shí)現(xiàn)114.運(yùn)行結(jié)果125.時(shí)間復(fù)雜性分析12四作業(yè)調(diào)度算法比較12五課程學(xué)習(xí)總結(jié)13摘要： 在現(xiàn)代企業(yè)中，作業(yè)調(diào)度已成為提高資源利用率、從而提高

2、企業(yè)運(yùn)行效益的關(guān)鍵環(huán)節(jié)之一。把各個(gè)作業(yè)分配到車間現(xiàn)有的設(shè)備上，并確定它們的先后次序，這是一項(xiàng)復(fù)雜的工作 本文就作業(yè)調(diào)度排序問題進(jìn)行了研究，通過對(duì)幾個(gè)經(jīng)典作業(yè)調(diào)度算法的分析討論，總結(jié)了各個(gè)算法對(duì)作業(yè)調(diào)度的求解過程，并給出了每個(gè)算法的復(fù)雜度及性能分析。關(guān)鍵詞：作業(yè)調(diào)度；動(dòng)態(tài)規(guī)劃；貪心算法；回溯法；一動(dòng)態(tài)規(guī)劃算法解決流水作業(yè)調(diào)度1、問題描述 給定n個(gè)作業(yè)，每個(gè)作業(yè)有兩道工序，分別在兩臺(tái)機(jī)器上處理。一臺(tái)機(jī)器一次只能處理一道工序，并且一道工序一旦開始就必須進(jìn)行下去直到完成。一個(gè)作業(yè)只有在機(jī)器1上的處理完成以后才能由機(jī)器2處理。假設(shè)已知作業(yè)i在機(jī)器j上需要的處理時(shí)間為ti,j。流水作業(yè)調(diào)度問題就是要求確定

3、一個(gè)作業(yè)的處理順序使得盡快完成這n個(gè)作業(yè)。2、算法分析 直觀上，一個(gè)最優(yōu)調(diào)度應(yīng)使機(jī)器M1沒有空閑時(shí)間，且機(jī)器M2的空閑時(shí)間最少。在一般情況下，機(jī)器M2上會(huì)有機(jī)器空閑和作業(yè)積壓2種情況。 在一般情況下，機(jī)器M1開始加工S中作業(yè)時(shí)，機(jī)器M2還在加工其他作業(yè)，要等時(shí)間t后才可利用。將這種情況下完成S中作業(yè)所需的最短時(shí)間記為T(S,t)。流水作業(yè)調(diào)度問題的最優(yōu)值為T(N,0)。由流水作業(yè)調(diào)度問題的最優(yōu)子結(jié)構(gòu)性質(zhì)可知， （1）（2） 從公式（1）可以看出，該問題類似一個(gè)排列問題，求N個(gè)作業(yè)的最優(yōu)調(diào)度問題，利用其子結(jié)構(gòu)性質(zhì)，對(duì)集合中的每一個(gè)作業(yè)進(jìn)行試調(diào)度，在所有的試調(diào)度中，取其中加工時(shí)間最短的作業(yè)做為選擇

4、方案。將問題規(guī)?？s小。 公式（2）說明一般情況下，對(duì)作業(yè)集S進(jìn)行調(diào)度，在M2機(jī)器上的等待時(shí)間，除了需要等該部件在M1機(jī)器上完成時(shí)間，還要沖抵一部分原來的等待時(shí)間，如果沖抵已成負(fù)值，自然仍需等待M1將作業(yè)做完，所以公式取maxt-ai,0。3. 算法的描述 從分析可知，流水作業(yè)調(diào)度問題一定存在滿足Johnson法則的最優(yōu)調(diào)度，且容易由下面的算法確定。流水作業(yè)調(diào)度問題的Johnson算法：（1）令；（2）將中作業(yè)依的非減序排列；將中作業(yè)依的非增序排列；作業(yè)接種作業(yè)構(gòu)成滿足Johnson法則的最優(yōu)調(diào)度。4、部分算法實(shí)現(xiàn)int FlowShop(int n,int a,int b,int c)int

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

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

7、的時(shí)間內(nèi)由m臺(tái)機(jī)器加工處理完成。約定，每個(gè)作業(yè)均可在任何一臺(tái)機(jī)器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。這個(gè)問題是NP完全問題，到目前為止還沒有有效的解法。對(duì)于這一類問題,用貪心選擇策略有時(shí)可以設(shè)計(jì)出較好的近似算法。 2、算法分析 貪心算法只需按順序以數(shù)組方式提供各作業(yè)的加工時(shí)間和機(jī)器的臺(tái)數(shù)；求出作業(yè)的個(gè)數(shù)，若小于機(jī)器臺(tái)數(shù)，就將作業(yè)逐個(gè)分配給就近的機(jī)器，所需要的加工時(shí)間，即為最長作業(yè)所需時(shí)間。 若作業(yè)數(shù)大于機(jī)器臺(tái)數(shù)，將作業(yè)按加工時(shí)間的多少降序排序，以機(jī)器數(shù)建立最小堆，先將前m個(gè)作業(yè)分配給m個(gè)機(jī)器，最小堆頂是最小的元素（即m個(gè)作業(yè)中加工時(shí)間最少的作業(yè)），將其移出并加上后

8、續(xù)作業(yè)的加工時(shí)間，再插入堆，這時(shí)會(huì)改變?cè)瓉淼臓顟B(tài)，升到堆頂?shù)臋C(jī)器加工總時(shí)間最少，它再移出加后續(xù)作業(yè)的加工時(shí)間，在插入堆，依此類推，直到全部作業(yè)結(jié)束。堆中的最大值就是完成所有作業(yè)所需的最短時(shí)間。 3.部分算法實(shí)現(xiàn) typedef struct Node int ID, avail;manode; /ID 機(jī)器編號(hào) avail 每次作業(yè)的初始時(shí)間 manode machineN; jobnode jobN; /* 找出下個(gè)作業(yè)執(zhí)行機(jī)器 */ manode* Find_min(manode a, int m) manode* temp = &a0; for (int i = 1; im; i+) i

9、f (ai.availavail) temp = &ai; return temp; /* 對(duì)作業(yè)時(shí)間由大到小進(jìn)行排序 */ 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(輸入機(jī)器數(shù)目(機(jī)器編號(hào)按輸入順序處理)n); cinm; for (i

10、= 0; im; i+)/給機(jī)器進(jìn)行編號(hào)并初始化 machinei.ID = i + 1; machinei.avail = 0; putchar(n); if (n = m) printf(為每個(gè)作業(yè)分配一臺(tái)機(jī)器,可完成任務(wù)!n); return; Sort(job, n); for (i = 0; i %d 的時(shí)間段分配給作業(yè): %dn, putchar(n); printf(該批作業(yè)處理完成所需加工時(shí)間為: %dn, temp); 4.計(jì)算復(fù)雜性分析當(dāng)nm 時(shí)，所有作業(yè)可以一次安排給各機(jī)器，算法greedy需要o(1) 時(shí)間。當(dāng)nm 時(shí)，排序耗時(shí)O(nlogn)。初始化堆需要O(m) 時(shí)

11、間。關(guān)于堆的removeMin和put運(yùn)算共耗時(shí)O(nlogm),因此算法greedy 所需的計(jì)算時(shí)間為O(nlogn+nlogm)=O(nlogn)。5. 運(yùn)行結(jié)果三回溯法解決批作業(yè)調(diào)度問題 1.問題描述 輸入：1. 任務(wù)數(shù)N2. 機(jī)器數(shù)M3. 隨機(jī)序列長度ti,其中ti=x表示第i個(gè)任務(wù)完成需要時(shí)間單位x，輸出：1. 開銷時(shí)間besttime，表示最佳調(diào)度需要時(shí)間單位2. 最佳調(diào)度序列bestx，其中bestxi=x，表示將第i個(gè)任務(wù)分配給第x個(gè)機(jī)器執(zhí)行。2.算法思想 解空間的表示：一個(gè)深度為N的M叉樹。ti:第i個(gè)任務(wù)的時(shí)間xi=j:當(dāng)前輸出結(jié)果Resi=j:表示第i個(gè)任務(wù)要運(yùn)行在第j臺(tái)

12、機(jī)器上time_machinei:第i個(gè)機(jī)器上的運(yùn)行時(shí)間基本思路： 1、搜索從開始結(jié)點(diǎn)（根結(jié)點(diǎn)）出發(fā)，以DFS搜索整個(gè)解空間。2、每搜索完一條路徑則記錄下time_min和Resi序列，開始結(jié)點(diǎn)就成為一個(gè)活結(jié)點(diǎn)， 同時(shí)也成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處向縱深方向移至一個(gè)新結(jié)點(diǎn)， 并成為一個(gè)新的活結(jié)點(diǎn)，也成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。 3、如果在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處不能再向縱深方向擴(kuò)展，則當(dāng)前擴(kuò)展結(jié)點(diǎn)就成為死結(jié)點(diǎn)。此時(shí)，應(yīng)往回移動(dòng)（回溯）至最近的一個(gè)活結(jié)點(diǎn)處，并使這個(gè)活結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)；直至找到一個(gè)解或全部解。3. 部分算法實(shí)現(xiàn)bool placetest(int k)int time_max_K

13、= time_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

14、i=1;i=N;i+)Resi = xielsefor(int i=1;i=K;i+)xk = i;/將第k個(gè)任務(wù)放到第i個(gè)機(jī)器上面if( placetest(k) )time_machinei += tk;Backtrack(k+1,t,x);time_machinei -= tk;4.運(yùn)行結(jié)果5.時(shí)間復(fù)雜性分析由于沒有使用限界函數(shù)進(jìn)行優(yōu)化，算法時(shí)間和空間復(fù)雜度呈指數(shù)級(jí)增長。所以該算法不適合較大規(guī)模的計(jì)算。藍(lán)線表示機(jī)器數(shù)一定M=3時(shí)，n增大時(shí)求解最佳調(diào)度對(duì)所消耗的時(shí)間，該趨勢隨著指數(shù)增加。四作業(yè)調(diào)度算法比較 在流水作業(yè)調(diào)度中，Johnson算法這是在只有兩臺(tái)設(shè)備情況下的最優(yōu)排序算法，同時(shí)說明

15、工件的第一道工序和最后一道工序的加工時(shí)間對(duì)排序的影響是主要的。 貪心算法只需按順序以數(shù)組方式提供各作業(yè)的加工時(shí)間和機(jī)器的臺(tái)數(shù)；求出作業(yè)的個(gè)數(shù)，若小于機(jī)器臺(tái)數(shù)，就將作業(yè)逐個(gè)分配給就近的機(jī)器，所需要的加工時(shí)間，即為最長作業(yè)所需時(shí)間復(fù)雜度為O(nlogn)。 回溯算法解決批作業(yè)調(diào)度問題與前面兩個(gè)問題不同，前兩個(gè)是求所有作業(yè)在M2機(jī)器上加工完成的最后時(shí)間，而這里要求的是求所有作業(yè)在機(jī)器M2上完成處理時(shí)間的總和達(dá)到最小。這種調(diào)度算法可用于計(jì)算加工費(fèi)用。批處理作業(yè)調(diào)度問題屬于排列樹的解空間問題，因此時(shí)間復(fù)雜度為(n!) 五課程學(xué)習(xí)總結(jié) 算法分析與設(shè)計(jì)是一門非常重要的課程，很多問題的解決，程序的編寫都要依賴它，算法的學(xué)習(xí)對(duì)于培養(yǎng)一個(gè)人的邏輯思維能力是有極大幫助的，它可以培養(yǎng)我們養(yǎng)成思考分析問題，解決問題的能力。但是算法的學(xué)習(xí)同時(shí)也需要較強(qiáng)的理解能力，有些算法程序不易讀懂，這時(shí)需要在理解問題的本質(zhì)上對(duì)算法程序進(jìn)行解讀。在對(duì)一個(gè)問題進(jìn)行算法設(shè)計(jì)時(shí)，要了解問題