機(jī)器調(diào)度問(wèn)題課設(shè)報(bào)告

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

我們的課程設(shè)計(jì)題目是機(jī)器調(diào)度問(wèn)題，剛開(kāi)始做這個(gè)程序的時(shí)候，感到完全無(wú)從下手，甚至讓我覺(jué)得完成這次程序設(shè)計(jì)根本就是不可能的，于是開(kāi)始查閱各種資料以及參考文獻(xiàn)，之后便開(kāi)始著手寫程序，寫完運(yùn)行時(shí)有很多問(wèn)題，經(jīng)常運(yùn)行出現(xiàn)錯(cuò)誤，但通過(guò)同學(xué)間的幫助最終基本解決問(wèn)題。

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