機器調度問題課設報告課程設計報告3.2最短時間流程圖開始開始機器一機器二機器三機器一最小？機器二最小？機器三最小？算出最短調度時間3.3偽代碼為每個機器設計數據類型：structMachineNode{intID;//機器號intavail;//機器可用時刻};·為每個作業設計數據類型：structJobNode{intID;//作業號inttime;//處理時間};LPT算法用偽代碼描述如下：1.如果作業數n≤機器數m，則1.1將作業i分配到機器i上；1.2最短調度長度等于n個作業中處理時間最大值；2.否則，重復執行以下操作，直到n個作業都被分配：2.1將n個作業按處理時間建成一個大根堆H1；2.2將m個機器按可用時刻建立一個小根堆H2；2.3將堆H1的堆頂作業分配給堆H2的堆頂機器；2.4將H2的堆頂機器加上H1的堆頂作業的處理時間重新插入h2中；2.5將堆H1的堆頂元素刪除；3.堆H2的堆頂元素就是最短調度時間；4.詳細設計4.1需求分析程序的功能：為給出的作業根據時間數分配機器。將作業按其所需時間的遞減順序排列。一臺機器在同一時刻只能處理一個作業，在分配一個作業時，將其分配給最先變為空閑的機器。直到所有作業分配完畢。算出最短調度時間。輸入輸出的要求：每個作業的所需的時間數和機器數為輸入。輸出為每個作業所分配的機器（每個機器所完成的作業），以及最短調度時間。4.2問題求解給出7個要完成的作業，作業所需的時間數分別為{2,14,4,16,6,5,3}，把這些作業在三臺機器中完成。首先將7個作業由大到小排序，排序后為{16,14,6,5,4,3,2}，接著開始為機器分配作業。作業由大到小分配。每個機器同一時間只能分配一個作業。在分配一個作業時，將其分配給最先變為空閑的機器，把16分配給機器一，14分配給機器二,6分配給機器三。比較三臺機器完成作業所需時間數，機器三最小。所以機器三先空閑下來。把5分配給機器三，比較三臺機器完成作業所需時間數，機器三最小。所以機器三先空閑下來。把4分配給機器三，比較三臺機器完成作業所需時間數，機器二最小。所以機器二先空閑下來。把3分配給機器二，比較三臺機器完成作業所需時間數，機器三最小。所以機器三先空閑下來。把2分配給機器三，到此作業分配完畢。所需時間最長的機器上的所需時間就是最短調度時間。5.測試與調試直接運行此程序。去取一組測試數據在控制臺輸出此程序的結果。6.程序清單#include<stdio.h>#defineN10//限定機器數和作業數不超過N個structMachineNode{ intID;//機器號 intavail;//機器可用時間};structJobNode{ intID;//作業號 inttime;//處理時間};voidBig(JobNoder[],intk,intm)//建立大根堆{ inti,j; i=k; j=2*i; while(j<=m) { if(j<m&&r[j].time<r[j+1].time) j++; if(r[i].time>r[j].time)break; else { inttemp1,temp2; temp1=r[i].time; r[i].time=r[j].time; r[j].time=temp1; temp2=r[i].ID; r[i].ID=r[j].ID; r[j].ID=temp2; } }}voidSortBig(JobNoder[],intn){for(inti=n/2;i>=1;i--)Big(r,i,n);}voidSmall(MachineNoder[],intk,intm)//建立小根堆{ inti,j; i=k; j=2*i; while(j<=m){ if(j<m&&r[j].avail>r[j+1].avail)j++; if(r[i].avail<r[j].avail)break; else { inttemp1,temp2; temp1=r[i].avail; r[i].avail=r[j].avail; r[j].avail=temp1; temp2=r[i].ID; r[i].ID=r[j].ID; r[j].ID=temp2; } }}voidSortSmall(MachineNoder[],intn){ for(inti=n/2;i>=1;i--) Small(r,i,n);}voidassign(MachineNodeM[],JobNodeJ[],intm,intj)//完成任務分配{ if(m>=j)//如果機器數m大于或等于作業數j { SortBig(J,j);//以各作業所需時間建立大根堆，堆頂元素即為最大耗時的作業所需時間 printf("一臺機器完成一個作業，最大工作時間為:%d\n",J[1].time); } else//如果機器數m小于作業數j { for(inti=1;i<=m;i++)//先為每臺機器分配一個作業，先把所需時間最大的m個作業分配給m臺機器 { SortBig(J,j);//建立大根堆求堆頂元素確定其中耗時最大的作業 M[i].avail=J[1].time;//機器i的處理時間即為作業所需時間 printf("機器%d完成作業%d\n",M[i].ID,J[1].ID); for(intk=1;k<j;k++)//減去已分配的作業 J[k]=J[k+1]; j=j-1; } for(intq=j;j>=1;q--)//把剩余的j-m個作業分配下去（j=j-m） { SortSmall(M,m);//將m個機器按可用時建立小根堆 SortBig(J,j);//將j個作業按處理時間建立大根堆 printf("機器%d完成作業%d\n",M[1].ID,J[1].ID);//將大根堆的堆頂作業分配給小根堆的堆頂機器 M[1].avail+=J[1].time;//將小根堆的堆頂機器加上大根堆的堆頂作業的處理時間，重新插入小根堆（循環執行SortSmall(M,m)時完成） for(intk=1;k<j;k++)//減去已分配的作業 J[k]=J[k+1]; j=j-1; } printf("最短調度時間為:%d\n",M[1].avail);//小根堆的堆頂元素就是最短調用時間 }}voidmain(){ intj=0;//作業個數 intm=0;//機器個數 inti; MachineNodeM[N];//機器的結構體數組 JobNodeJ[N];//作業的結構體數組 printf("請輸入作業個數\n"); scanf("%d",&j); printf("請輸入每個作業需要的處理時間:\n"); for(i=1;i<=j;i++) { J[i].ID=i;//為每個作業確定序號 printf("第%d個作業：\n",i); scanf("%d",&J[i].time);//輸入每個作業的用時 } printf("請輸入機器數:\n"); scanf("%d",&m); for(i=1;i<=m;i++) M[i].ID=i; //為每臺機器確定序號 assign(M,J,m,j);//調用完成分配任務的函數}7.體會與心得本次課程設計，使我對《數據結構》這門課程有了更深入的理解。《數據結構》是一門實踐性較強的課程，為了學好這門課程，必須在掌握理論知識的同時，加強上機實踐。

我們的課程設計題目是機器調度問題，剛開始做這個程序的時候，感到完全無從下手，甚至讓我覺得完成這次程序設計根本就是不可能的，于是開始查閱各種資料以及參考文獻，之后便開始著手寫程序，寫完運行時有很多問題，經常運行出現錯誤，但通過同學間的幫助最終基本解決問題。

在本課程設計中，我明白了理論與實際應用相結合的重要性，并提高了自己組織數據及編寫大型程序的能力。培養了基本的、良好的程序設計技能以及合作能力。這次課程設計同樣提高了我的綜合運用所學知識的能力。并對VC有了更深入的了解。《數據結構》是一門實踐性很強的課程，上機實習是對學生全面綜合素質進行訓練的一種最基本的方法，是與課堂聽講、自學和練習相輔相成的、必不可少的一個教學環節。上機實習一方面能使書本上的知識變“活”，起到深化理解和靈活掌握教學內容的目的;另一方面，上機實習是對學生軟件設計的綜合能力的訓練，包括問題分析，總體結構設計，程序設計基本技能和技巧的訓練。此外，還有更重要的一點是：機器是比任何教師更嚴厲的檢查者。因此，在“數據結構”的學習過程中，必須嚴格按照老師的要求，主動地、積極地、認真地做好每一個實驗，以不斷提高