機(jī)器調(diào)度問題數(shù)據(jù)結(jié)構(gòu)課設(shè)c++

1、WORD格式學(xué)號(hào)09770210數(shù)據(jù)構(gòu)造課程設(shè)計(jì)設(shè)計(jì)說明書題目機(jī)器調(diào)度問題起止日期：2021年 10月 20 日至2021年 12月14日學(xué)生姓名X 艷 羽班級(jí)軟件二班成績(jī)指導(dǎo)教師(簽字)電子與信息工程系年月日專業(yè)資料整理WORD格式附錄四課程設(shè)計(jì)任務(wù)書*城市建立學(xué)院課程設(shè)計(jì)任務(wù)書專業(yè)資料整理WORD格式20212021學(xué)年第1 學(xué)期專業(yè)資料整理WORD格式電子與信息工程系軟件工程專業(yè)2班級(jí)專業(yè)資料整理WORD格式課程設(shè)計(jì)名稱：數(shù)據(jù)構(gòu)造課程設(shè)計(jì)設(shè)計(jì)題目：機(jī)器調(diào)度問題專業(yè)資料整理WORD格式完成期限：自2021年 10 月 20 日至2021年12月14日共周專業(yè)資料整理WORD格式設(shè)計(jì)依據(jù)、要

2、求及主要內(nèi)容可另加附頁：一、設(shè)計(jì)目的熟悉各種數(shù)據(jù)構(gòu)造和運(yùn)算，會(huì)使用數(shù)據(jù)構(gòu)造的根本操作解決一些實(shí)際問題。二、設(shè)計(jì)要求（ 1重視課程設(shè)計(jì)環(huán)節(jié)， 用嚴(yán)謹(jǐn)、 科學(xué)和踏實(shí)的工作態(tài)度對(duì)待課程設(shè)計(jì)的每一項(xiàng)任務(wù)；（ 2按照課程設(shè)計(jì)的題目要求，獨(dú)立地完成各項(xiàng)任務(wù)，嚴(yán)禁抄襲；凡發(fā)現(xiàn)抄襲，抄襲者與被抄襲者皆以零分計(jì)入本課程設(shè)計(jì)成績(jī)。 凡發(fā)現(xiàn)實(shí)驗(yàn)報(bào)告或源程序雷同， 涉及的全部人員皆以零分計(jì)入本課程設(shè)計(jì)成績(jī)；（ 3學(xué)生在承受設(shè)計(jì)任務(wù)后，首先要按設(shè)計(jì)任務(wù)書的要求編寫設(shè)計(jì)進(jìn)程表；（ 4認(rèn)真編寫課程設(shè)計(jì)報(bào)告。三、設(shè)計(jì)內(nèi)容機(jī)器調(diào)度問題1)問題描述機(jī)器調(diào)度是指有m 臺(tái)機(jī)器需要處理n 個(gè)作業(yè)，設(shè)作業(yè)i 的處理時(shí)間為ti，那么對(duì) n

3、 個(gè)作業(yè)進(jìn)展機(jī)器分配，使得：(1) 一臺(tái)機(jī)器在同一時(shí)間內(nèi)只能處理一個(gè)作業(yè)；(2) 一個(gè)作業(yè)不能同時(shí)在兩臺(tái)機(jī)器上處理；(3) 作業(yè) i 一旦運(yùn)行，那么需要 ti個(gè)連續(xù)時(shí)間單位。設(shè)計(jì)算法進(jìn)展合理調(diào)度，使得在m 臺(tái)機(jī)器上處理n 個(gè)作業(yè)所需要的處理時(shí)間最短。2) 根本要求(1) 建立問題模型，設(shè)計(jì)數(shù)據(jù)構(gòu)造；專業(yè)資料整理WORD格式(2) 設(shè)計(jì)調(diào)度算法，為每個(gè)作業(yè)分配一臺(tái)可用機(jī)器；(3) 給出分配方案。3) 設(shè)計(jì)思想假設(shè)有七個(gè)作業(yè)，所需時(shí)間分別為2, 14, 4, 16, 6, 5, 3，有三臺(tái)機(jī)器，編號(hào)分別為m1、m2和 m3。這七個(gè)作業(yè)在三臺(tái)機(jī)器上進(jìn)展調(diào)度的情形如圖9 所示，陰影區(qū)代表作業(yè)的運(yùn)行區(qū)間

4、。作業(yè) 4 在 0 到 16 時(shí)間被調(diào)度到機(jī)器1 上運(yùn)行， 在這 16個(gè)時(shí)間單位中， 機(jī)器 1 完成了對(duì)作業(yè) 4 的處理；作業(yè)2 在 0 到 14 時(shí)間被調(diào)度到機(jī)器2 上處理，之后機(jī)器2在14到 17時(shí)間處理作業(yè) 7；在機(jī)器3 上，作業(yè) 5 在 06 時(shí)間完成，作業(yè)6 在 6 11 時(shí)間完成，作業(yè)3 在11 15 時(shí)間完成，作業(yè) 1 在 1517 時(shí)間完成。注意到作業(yè)i 只能在一臺(tái)機(jī)器上從 si時(shí)刻到si +ti時(shí)間完成且任何機(jī)器在同一時(shí)刻僅能處理一個(gè)作業(yè)，因此最短調(diào)度長(zhǎng)度為17。m1作業(yè) 4m2作業(yè) 2作業(yè) 7m3作業(yè) 5作業(yè) 6作業(yè) 3作業(yè) 1時(shí)間654分配1617圖 9三臺(tái)機(jī)器的調(diào)度例如

5、在上述處理中，采用了最長(zhǎng)時(shí)間優(yōu)先LPT 的簡(jiǎn)單調(diào)度策略。在LPT算法中，作業(yè)按其所需時(shí)間的遞減順序排列，在分配一個(gè)作業(yè)時(shí)，將其分配給最先變?yōu)榭臻e的機(jī)器。四、參考文獻(xiàn)1王紅梅數(shù)據(jù)構(gòu)造清華大學(xué)2王紅梅數(shù)據(jù)構(gòu)造學(xué)習(xí)輔導(dǎo)與實(shí)驗(yàn)指導(dǎo)清華大學(xué)3嚴(yán)蔚敏，吳偉民數(shù)據(jù)構(gòu)造C 語言版清華大學(xué)專業(yè)資料整理WORD格式一、需求分析一程序的功能為給出的作業(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ī)器所

6、完成的作業(yè) ，以及最短調(diào)度時(shí)間。二、問題求解給出 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 ，接著開場(chǎng)為機(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ī)器三先空閑下來。把 5 分配給機(jī)器三，比較三臺(tái)機(jī)器完成作業(yè)所需時(shí)間數(shù)，機(jī)器三最小。所以機(jī)器三先空閑下來。把

7、 4 分配給機(jī)器三，比較三臺(tái)機(jī)器完成作業(yè)所需時(shí)間數(shù)，機(jī)器二最小。所以機(jī)器二先空閑下來。把 3 分配給機(jī)器二，比較三臺(tái)機(jī)器完成作業(yè)所需時(shí)間數(shù)，機(jī)器三最小。所以機(jī)器三先空閑下來。把 2 分配給機(jī)器三，到此作業(yè)分配完畢。所需時(shí)間最長(zhǎng)的機(jī)器上的所需時(shí)間就是最短調(diào)度時(shí)間。三、總體設(shè)計(jì)專業(yè)資料整理WORD格式程序設(shè)計(jì)組成框圖：專業(yè)資料整理WORD格式開場(chǎng)機(jī)器二機(jī)器三機(jī)器一最小？最??？最?。繖C(jī)器一機(jī)器二機(jī)器三算出最短調(diào)度時(shí)間流程圖：作業(yè)所需的時(shí)間數(shù)將時(shí)間數(shù)從大到小排序16機(jī)器一16143機(jī)器二176542機(jī)器三111517專業(yè)資料整理WORD格式四、詳細(xì)設(shè)計(jì)1、運(yùn)用下面的代碼計(jì)算哪臺(tái)機(jī)器空閑int min=

8、machines0;for(int i=0;i<machines.length;i+)if(machinesi<min)min=machinesi;if(machines0=min)System.out.println(" 第 "+1+" 個(gè)機(jī)器空閑，可以開場(chǎng)下一個(gè)作業(yè)！ ");if(machines1=min)System.out.println(" 第 "+2+" 個(gè)機(jī)器空閑，可以開場(chǎng)下一個(gè)作業(yè)！ ");if(machines2=min) System.out.println("第 &qu

9、ot;+3+" 個(gè)機(jī)器空閑，可以開場(chǎng)下一個(gè)作業(yè)！ ");2、運(yùn)用下面源代碼計(jì)算最短調(diào)度時(shí)間int max=machines0;for(int i=0;i<machines.length;i+)if(machinesi>max)max=machinesi;五、調(diào)試與測(cè)試直接運(yùn)行此程序。在控制臺(tái)輸出此程序的結(jié)果。每當(dāng)出現(xiàn)機(jī)器空閑后，輸入空閑的機(jī)器，繼續(xù)下一步操作。直到作業(yè)分配完畢。專業(yè)資料整理WORD格式六、關(guān)鍵源程序清單和執(zhí)行結(jié)果專業(yè)資料整理WORD格式源代碼：import java.util.Arrays;import java.util.Scanner;pub

10、lic class MyData public MyData()public static void main(String args) int works=2,14,4,16,6,5,3;/ 準(zhǔn)備調(diào)度的作業(yè)int N=works.length;System.out.print(" 準(zhǔn)備調(diào)度的作業(yè)的時(shí)間數(shù)分別為：");for(int i=0;i<N;i+)System.out.print(worksi+"");System.out.println();int temp=0;Scanner input=new Scanner(System.in);f

11、or(int i=0;i<N-1;i+)/ 對(duì)給出的作業(yè)時(shí)間數(shù)從大到小冒泡排序 for(int j=0;j<N-i-1;j+)if(worksj<worksj+1)temp=worksj;worksj=worksj+1;worksj+1=temp;int machines=new int3;machines0=works0;System.out.println(" 開場(chǎng)作業(yè)！ ");System.out.println(" 機(jī)器 1 完成時(shí)間數(shù)為"+works0+" 的作業(yè) ");machines1=works1;S

12、ystem.out.println(" 機(jī)器 2 完成時(shí)間數(shù)為 "+works1+" 的作業(yè) "); machines2=works2;System.out.println(" 機(jī)器 3 完成時(shí)間數(shù)為"+works2+" 的作業(yè) ");int min=machines0;for(int i=0;i<machines.length;i+)if(machinesi<min)min=machinesi;專業(yè)資料整理WORD格式if(machines0=min)System.out.println("

13、第 "+1+"個(gè)機(jī)器空閑，可以開場(chǎng)下一個(gè)作專業(yè)資料整理WORD格式業(yè)！ ");專業(yè)資料整理WORD格式if(machines1=min)System.out.println("第 "+2+"個(gè)機(jī)器空閑，可以開場(chǎng)下一個(gè)作專業(yè)資料整理WORD格式業(yè)！ ");專業(yè)資料整理WORD格式if(machines2=min)System.out.println("第 "+3+"個(gè)機(jī)器空閑，可以開場(chǎng)下一個(gè)作專業(yè)資料整理WORD格式業(yè)！ ");/專業(yè)資料整理WORD格式System.out.printl

14、n(" 開場(chǎng)下一個(gè)作業(yè)的機(jī)器是：");int shuru1=input.nextInt();專業(yè)資料整理WORD格式System.out.println(" 機(jī)器 "+shuru1+" 完成時(shí)間數(shù)為 "+works3+"machinesshuru1-1=machinesshuru1-1+works3;的作業(yè)");專業(yè)資料整理WORD格式min=machines0;for(int i=0;i<machines.length;i+)if(machinesi<min)min=machinesi;專業(yè)資料整理W

15、ORD格式if(machines0=min)System.out.println("第 "+1+"個(gè)機(jī)器空閑，可以開場(chǎng)下一個(gè)作專業(yè)資料整理WORD格式業(yè)！ ");專業(yè)資料整理WORD格式if(machines1=min)System.out.println("第 "+2+"個(gè)機(jī)器空閑，可以開場(chǎng)下一個(gè)作專業(yè)資料整理WORD格式業(yè)！ ");專業(yè)資料整理WORD格式if(machines2=min)System.out.println("第 "+3+"個(gè)機(jī)器空閑，可以開場(chǎng)下一個(gè)作專業(yè)資料整理

16、WORD格式業(yè)！ ");/專業(yè)資料整理WORD格式System.out.println(" 開場(chǎng)下一個(gè)作業(yè)的機(jī)器是：");int shuru2=input.nextInt();System.out.println(" 機(jī)器 "+shuru2+" 完成時(shí)間數(shù)為 "+works4+"machinesshuru2-1=machinesshuru2-1+works4;的作業(yè)");專業(yè)資料整理WORD格式min=machines0;for(int i=0;i<machines.length;i+)if(mac

17、hinesi<min)min=machinesi;專業(yè)資料整理WORD格式if(machines0=min)System.out.println("第 "+1+"個(gè)機(jī)器空閑，可以開場(chǎng)下一個(gè)作專業(yè)資料整理WORD格式業(yè)！ ");專業(yè)資料整理WORD格式if(machines1=min)System.out.println("第 "+2+"個(gè)機(jī)器空閑，可以開場(chǎng)下一個(gè)作專業(yè)資料整理WORD格式業(yè)！ ");專業(yè)資料整理WORD格式if(machines2=min)System.out.println("第

18、"+3+"個(gè)機(jī)器空閑，可以開場(chǎng)下一個(gè)作專業(yè)資料整理WORD格式業(yè)！ ");/專業(yè)資料整理WORD格式System.out.println("開場(chǎng)下一個(gè)作業(yè)的機(jī)器是：");專業(yè)資料整理WORD格式int shuru3=input.nextInt();System.out.println(" 機(jī)器 "+shuru3+" 完成時(shí)間數(shù)為 "+works5+" 的作業(yè) "); machinesshuru3-1=machinesshuru3-1+works5;min=machines0;for(int i=0;i<machines.length;i+)if(machinesi<min)min=machinesi;專業(yè)資料整理WORD格式if(machines0=min)System.out.println("第 "+1+"個(gè)機(jī)器空閑，可以開場(chǎng)下一個(gè)作專業(yè)資料整理WORD格式業(yè)！ ");專業(yè)資料整理WORD格式if(machines1=min)System.out