1、目錄1.課程設(shè)計題目及實現(xiàn)功能12.設(shè)計內(nèi)容12.1問題描述12.2基本要求12.3設(shè)計思想13.概要設(shè)計23.1算法設(shè)計23.2最短時間流程圖33.3偽代碼34.詳細設(shè)計44.1需求分析44.2問題求解45.測試與調(diào)試56.程序清單57.體會與心得9參考文獻10課程設(shè)計報告 1.課程設(shè)計題目及實現(xiàn)功能課程設(shè)計題目：機器調(diào)度問題實現(xiàn)功能：怎樣安排機器上的具體作業(yè)數(shù)2.設(shè)計內(nèi)容2.1問題描述機器調(diào)度是指有m臺機器需要處理n個作業(yè)，設(shè)作業(yè)i的處理時間為ti，則對n個作業(yè)進行機器分配，使得：(1) 一臺機器在同一時間內(nèi)只能處理一個作業(yè)；(2) 一個作業(yè)不能同時在兩臺機器上處理；(3) 作業(yè)i一旦運行

2、，則需要ti個連續(xù)時間單位。設(shè)計算法進行合理調(diào)度，使得在m臺機器上處理n個作業(yè)所需要的處理時間最短。2.2基本要求(1) 建立問題模型，設(shè)計數(shù)據(jù)結(jié)構(gòu)；(2) 設(shè)計調(diào)度算法，為每個作業(yè)分配一臺可用機器；(3) 給出分配方案。2.3設(shè)計思想假設(shè)有七個作業(yè)，所需時間分別為2, 14, 4, 16, 6, 5, 3，有三臺機器，編號分別為m1、m2和m3。這七個作業(yè)在三臺機器上進行調(diào)度的情形如圖9所示，陰影區(qū)代表作業(yè)的運行區(qū)間。作業(yè)4在0到16時間被調(diào)度到機器1上運行，在這16個時間單位中，機器1完成了對作業(yè)4的處理；作業(yè)2在0到14時間被調(diào)度到機器2上處理，之后機器2在14到17時間處理作業(yè)7；在機

3、器3上，作業(yè)5在06時間完成，作業(yè)6在611時間完成，作業(yè)3在1115時間完成，作業(yè)1在1517時間完成。注意到作業(yè)i只能在一臺機器上從si時刻到si +ti時間完成且任何機器在同一時刻僅能處理一個作業(yè)，因此最短調(diào)度長度為17。m1m2m3時間分配 作業(yè)5作業(yè)6 作業(yè)3作業(yè)1作業(yè)2 作業(yè)7 作業(yè)41716圖9 三臺機器的調(diào)度示例6543.概要設(shè)計 3.1算法設(shè)計作業(yè)所需的時間數(shù)機器一機器二機器三將時間數(shù)從大到小排序16146541115317172163.2最短時間流程圖開始機器一機器二機器三機器一最??？機器二最小？機器三最小？算出最短調(diào)度時間3.3偽代碼為每個機器設(shè)計數(shù)據(jù)類型： struct

4、 MachineNode int ID; /機器號int avail; /機器可用時刻 ; · 為每個作業(yè)設(shè)計數(shù)據(jù)類型： struct JobNode int ID; /作業(yè)號int time; /處理時間 ;LPT算法用偽代碼描述如下：1. 如果作業(yè)數(shù)n機器數(shù)m，則 1.1 將作業(yè)i分配到機器i上； 1.2 最短調(diào)度長度等于n個作業(yè)中處理時間最大值；2. 否則，重復執(zhí)行以下操作，直到n個作業(yè)都被分配： 2.1 將n個作業(yè)按處理時間建成一個大根堆H1； 2.2 將m個機器按可用時刻建立一個小根堆H2； 2.3 將堆H1的堆頂作業(yè)分配給堆H2的堆頂機器； 2.4 將H2的堆頂機器加上H

5、1的堆頂作業(yè)的處理時間重新插入h2中； 2.5 將堆H1的堆頂元素刪除；3. 堆H2的堆頂元素就是最短調(diào)度時間；4.詳細設(shè)計4.1需求分析程序的功能：為給出的作業(yè)根據(jù)時間數(shù)分配機器。將作業(yè)按其所需時間的遞減順序排列。一臺機器在同一時刻只能處理一個作業(yè)，在分配一個作業(yè)時，將其分配給最先變?yōu)榭臻e的機器。直到所有作業(yè)分配完畢。算出最短調(diào)度時間。輸入輸出的要求：每個作業(yè)的所需的時間數(shù)和機器數(shù)為輸入。輸出為每個作業(yè)所分配的機器（每個機器所完成的作業(yè)），以及最短調(diào)度時間。4.2問題求解給出7個要完成的作業(yè)，作業(yè)所需的時間數(shù)分別為2, 14, 4, 16, 6, 5, 3，把這些作業(yè)在三臺機器中完成。首先將

6、7個作業(yè)由大到小排序，排序后為16, 14, 6, 5, 4, 3, 2，接著開始為機器分配作業(yè)。作業(yè)由大到小分配。每個機器同一時間只能分配一個作業(yè)。在分配一個作業(yè)時，將其分配給最先變?yōu)榭臻e的機器，把16分配給機器一，14分配給機器二, 6分配給機器三。比較三臺機器完成作業(yè)所需時間數(shù)，機器三最小。所以機器三先空閑下來。把5分配給機器三，比較三臺機器完成作業(yè)所需時間數(shù)，機器三最小。所以機器三先空閑下來。把4分配給機器三，比較三臺機器完成作業(yè)所需時間數(shù)，機器二最小。所以機器二先空閑下來。把3分配給機器二，比較三臺機器完成作業(yè)所需時間數(shù)，機器三最小。所以機器三先空閑下來。把2分配給機器三，到此作業(yè)分

7、配完畢。所需時間最長的機器上的所需時間就是最短調(diào)度時間。5.測試與調(diào)試直接運行此程序。去取一組測試數(shù)據(jù)在控制臺輸出此程序的結(jié)果。6.程序清單#include<stdio.h>#define N 10 /限定機器數(shù)和作業(yè)數(shù)不超過N個struct MachineNodeint ID; /機器號int avail; /機器可用時間;struct JobNodeint ID; /作業(yè)號int time; /處理時間;void Big(JobNode r,int k,int m)/建立大根堆int i,j;i=k;j=2*i;while(j<=m) if(j<m&&

8、;rj.time<rj+1.time) j+; if(ri.time>rj.time)break; else int temp1,temp2;temp1=ri.time;ri.time=rj.time;rj.time=temp1;temp2=ri.ID;ri.ID=rj.ID;rj.ID=temp2; void SortBig(JobNode r,int n) for(int i=n/2;i>=1;i-) Big(r,i,n);void Small(MachineNode r,int k,int m)/建立小根堆int i,j;i=k;j=2*i;while(j<=m)

9、if(j<m&&rj.avail>rj+1.avail)j+;if(ri.avail<rj.avail)break;elseint temp1,temp2;temp1=ri.avail;ri.avail=rj.avail;rj.avail=temp1;temp2=ri.ID;ri.ID=rj.ID;rj.ID=temp2;void SortSmall(MachineNode r,int n)for(int i=n/2;i>=1;i-)Small(r,i,n);void assign(MachineNode M,JobNode J,int m,int j)

10、 /完成任務(wù)分配if(m>=j) /如果機器數(shù)m大于或等于作業(yè)數(shù)jSortBig(J,j); /以各作業(yè)所需時間建立大根堆，堆頂元素即為最大耗時的作業(yè)所需時間printf("一臺機器完成一個作業(yè)，最大工作時間為:%dn",J1.time);else /如果機器數(shù)m小于作業(yè)數(shù)jfor(int i=1;i<=m;i+) /先為每臺機器分配一個作業(yè)，先把所需時間最大的m個作業(yè)分配給m臺機器SortBig(J,j); /建立大根堆求堆頂元素確定其中耗時最大的作業(yè)Mi.avail=J1.time; /機器i的處理時間即為作業(yè)所需時間printf("機器 %d 完

11、成作業(yè)%dn",Mi.ID,J1.ID);for(int k=1;k<j;k+) /減去已分配的作業(yè)Jk=Jk+1;j=j-1;for(int q=j;j>=1;q-) /把剩余的j-m個作業(yè)分配下去（j=j-m）SortSmall(M,m); /將m個機器按可用時建立小根堆SortBig(J,j); /將j個作業(yè)按處理時間建立大根堆printf("機器 %d 完成作業(yè)%dn",M1.ID,J1.ID); /將大根堆的堆頂作業(yè)分配給小根堆的堆頂機器M1.avail+=J1.time; /將小根堆的堆頂機器加上大根堆的堆頂作業(yè)的處理時間，重新插入小根堆（

12、循環(huán)執(zhí)行SortSmall(M,m)時完成）for(int k=1;k<j;k+) /減去已分配的作業(yè)Jk=Jk+1;j=j-1;printf("最短調(diào)度時間為:%dn",M1.avail); /小根堆的堆頂元素就是最短調(diào)用時間void main()int j=0; /作業(yè)個數(shù)int m=0; /機器個數(shù)int i;MachineNode MN; /機器的結(jié)構(gòu)體數(shù)組JobNode JN; /作業(yè)的結(jié)構(gòu)體數(shù)組printf("請輸入作業(yè)個數(shù)n");scanf("%d",&j);printf("請輸入每個作業(yè)需要的處

13、理時間:n");for(i=1;i<=j;i+) Ji.ID=i; /為每個作業(yè)確定序號printf("第%d個作業(yè)：n",i);scanf("%d",&Ji.time); /輸入每個作業(yè)的用時printf("請輸入機器數(shù):n");scanf("%d",&m);for(i=1;i<=m;i+)Mi.ID=i; /為每臺機器確定序號assign(M,J,m,j); /調(diào)用完成分配任務(wù)的函數(shù)7.體會與心得本次課程設(shè)計，使我對數(shù)據(jù)結(jié)構(gòu)這門課程有了更深入的理解。數(shù)據(jù)結(jié)構(gòu)是一門實踐性較強

14、的課程，為了學好這門課程，必須在掌握理論知識的同時，加強上機實踐。我們的課程設(shè)計題目是機器調(diào)度問題，剛開始做這個程序的時候，感到完全無從下手，甚至讓我覺得完成這次程序設(shè)計根本就是不可能的，于是開始查閱各種資料以及參考文獻，之后便開始著手寫程序，寫完運行時有很多問題，經(jīng)常運行出現(xiàn)錯誤，但通過同學間的幫助最終基本解決問題。在本課程設(shè)計中，我明白了理論與實際應(yīng)用相結(jié)合的重要性，并提高了自己組織數(shù)據(jù)及編寫大型程序的能力。培養(yǎng)了基本的、良好的程序設(shè)計技能以及合作能力。這次課程設(shè)計同樣提高了我的綜合運用所學知識的能力。并對VC有了更深入的了解。數(shù)據(jù)結(jié)構(gòu)是一門實踐性很強的課程，上機實習是對學生全面綜合素質(zhì)進行訓練的一種最基本的方法，是與課堂聽講、自學和練習相輔相成的、必不可少的一個教學環(huán)節(jié)。上機實習一方面能使書本上的知識變“活”，起到深化理解和靈活掌握教學內(nèi)容的目的;另一方面，上機實習是對學生軟件設(shè)計的綜合能力的訓練，包括問題分析，總體結(jié)構(gòu)設(shè)計，程序設(shè)計基本技能和技巧的訓練。此外，還有更重要的一點是：機器是比任何教師更嚴厲的檢查者。因此，在“數(shù)據(jù)結(jié)構(gòu)”的學習過