機器調度問題數據結構課設c++

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

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

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

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

5、在上述處理中，采用了最長時間優(yōu)先LPT 的簡單調度策略。在LPT算法中，作業(yè)按其所需時間的遞減順序排列，在分配一個作業(yè)時，將其分配給最先變?yōu)榭臻e的機器。四、參考文獻1王紅梅數據構造清華大學2王紅梅數據構造學習輔導與實驗指導清華大學3嚴蔚敏，吳偉民數據構造C 語言版清華大學專業(yè)資料整理WORD格式一、需求分析一程序的功能為給出的作業(yè)根據時間數分配機器。將作業(yè)按其所需時間的遞減順序排列。一臺機器在同一時刻只能處理一個作業(yè)，在分配一個作業(yè)時，將其分配給最先變?yōu)榭臻e的機器。直到所有作業(yè)分配完畢。算出最短調度時間。二輸入輸出的要求每個作業(yè)的所需的時間數和機器數為輸入。輸出為每個作業(yè)所分配的機器每個機器所

6、完成的作業(yè) ，以及最短調度時間。二、問題求解給出 7 個要完成的作業(yè)，作業(yè)所需的時間數分別為2, 14, 4, 16, 6, 5, 3 ，把這些作業(yè)在三臺機器中完成。首先將7 個作業(yè)由大到小排序，排序后為16, 14, 6, 5, 4, 3, 2 ，接著開場為機器分配作業(yè)。作業(yè)由大到小分配。每個機器同一時間只能分配一個作業(yè)。在分配一個作業(yè)時，將其分配給最先變?yōu)榭臻e的機器，把 16 分配給機器一， 14 分配給機器二 , 6 分配給機器三。 比較三臺機器完成作業(yè)所需時間數，機器三最小。所以機器三先空閑下來。把 5 分配給機器三，比較三臺機器完成作業(yè)所需時間數，機器三最小。所以機器三先空閑下來。把

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

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

9、ot;+3+" 個機器空閑，可以開場下一個作業(yè)！ ");2、運用下面源代碼計算最短調度時間int max=machines0;for(int i=0;i<machines.length;i+)if(machinesi>max)max=machinesi;五、調試與測試直接運行此程序。在控制臺輸出此程序的結果。每當出現機器空閑后，輸入空閑的機器，繼續(xù)下一步操作。直到作業(yè)分配完畢。專業(yè)資料整理WORD格式六、關鍵源程序清單和執(zhí)行結果專業(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;/ 準備調度的作業(yè)int N=works.length;System.out.print(" 準備調度的作業(yè)的時間數分別為：");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+)/ 對給出的作業(yè)時間數從大到小冒泡排序 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(" 開場作業(yè)！ ");System.out.println(" 機器 1 完成時間數為"+works0+" 的作業(yè) ");machines1=works1;S

12、ystem.out.println(" 機器 2 完成時間數為 "+works1+" 的作業(yè) "); machines2=works2;System.out.println(" 機器 3 完成時間數為"+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+"個機器空閑，可以開場下一個作專業(yè)資料整理WORD格式業(yè)！ ");專業(yè)資料整理WORD格式if(machines1=min)System.out.println("第 "+2+"個機器空閑，可以開場下一個作專業(yè)資料整理WORD格式業(yè)！ ");專業(yè)資料整理WORD格式if(machines2=min)System.out.println("第 "+3+"個機器空閑，可以開場下一個作專業(yè)資料整理WORD格式業(yè)！ ");/專業(yè)資料整理WORD格式System.out.printl

14、n(" 開場下一個作業(yè)的機器是：");int shuru1=input.nextInt();專業(yè)資料整理WORD格式System.out.println(" 機器 "+shuru1+" 完成時間數為 "+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+"個機器空閑，可以開場下一個作專業(yè)資料整理WORD格式業(yè)！ ");專業(yè)資料整理WORD格式if(machines1=min)System.out.println("第 "+2+"個機器空閑，可以開場下一個作專業(yè)資料整理WORD格式業(yè)！ ");專業(yè)資料整理WORD格式if(machines2=min)System.out.println("第 "+3+"個機器空閑，可以開場下一個作專業(yè)資料整理

16、WORD格式業(yè)！ ");/專業(yè)資料整理WORD格式System.out.println(" 開場下一個作業(yè)的機器是：");int shuru2=input.nextInt();System.out.println(" 機器 "+shuru2+" 完成時間數為 "+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+"個機器空閑，可以開場下一個作專業(yè)資料整理WORD格式業(yè)！ ");專業(yè)資料整理WORD格式if(machines1=min)System.out.println("第 "+2+"個機器空閑，可以開場下一個作專業(yè)資料整理WORD格式業(yè)！ ");專業(yè)資料整理WORD格式if(machines2=min)System.out.println("第

18、"+3+"個機器空閑，可以開場下一個作專業(yè)資料整理WORD格式業(yè)！ ");/專業(yè)資料整理WORD格式System.out.println("開場下一個作業(yè)的機器是：");專業(yè)資料整理WORD格式int shuru3=input.nextInt();System.out.println(" 機器 "+shuru3+" 完成時間數為 "+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+"個機器空閑，可以開場下一個作專業(yè)資料整理WORD格式業(yè)！ ");專業(yè)資料整理WORD格式if(machines1=min)System.out