机器调度问题数据结构课设c++

1、WORD格式学号09770210数据构造课程设计设计说明书题目机器调度问题起止日期：2021年 10月 20 日至2021年 12月14日学生姓名X 艳 羽班级软件二班成绩指导教师(签字)电子与信息工程系年月日专业资料整理WORD格式附录四课程设计任务书*城市建立学院课程设计任务书专业资料整理WORD格式20212021学年第1 学期专业资料整理WORD格式电子与信息工程系软件工程专业2班级专业资料整理WORD格式课程设计名称：数据构造课程设计设计题目：机器调度问题专业资料整理WORD格式完成期限：自2021年 10 月 20 日至2021年12月14日共周专业资料整理WORD格式设计依据、要

2、求及主要内容可另加附页：一、设计目的熟悉各种数据构造和运算，会使用数据构造的根本操作解决一些实际问题。二、设计要求（ 1重视课程设计环节， 用严谨、 科学和踏实的工作态度对待课程设计的每一项任务；（ 2按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。 凡发现实验报告或源程序雷同， 涉及的全部人员皆以零分计入本课程设计成绩；（ 3学生在承受设计任务后，首先要按设计任务书的要求编写设计进程表；（ 4认真编写课程设计报告。三、设计内容机器调度问题1)问题描述机器调度是指有m 台机器需要处理n 个作业，设作业i 的处理时间为ti，那么对 n

3、 个作业进展机器分配，使得：(1) 一台机器在同一时间内只能处理一个作业；(2) 一个作业不能同时在两台机器上处理；(3) 作业 i 一旦运行，那么需要 ti个连续时间单位。设计算法进展合理调度，使得在m 台机器上处理n 个作业所需要的处理时间最短。2) 根本要求(1) 建立问题模型，设计数据构造；专业资料整理WORD格式(2) 设计调度算法，为每个作业分配一台可用机器；(3) 给出分配方案。3) 设计思想假设有七个作业，所需时间分别为2, 14, 4, 16, 6, 5, 3，有三台机器，编号分别为m1、m2和 m3。这七个作业在三台机器上进展调度的情形如图9 所示，阴影区代表作业的运行区间

4、。作业 4 在 0 到 16 时间被调度到机器1 上运行， 在这 16个时间单位中， 机器 1 完成了对作业 4 的处理；作业2 在 0 到 14 时间被调度到机器2 上处理，之后机器2在14到 17时间处理作业 7；在机器3 上，作业 5 在 06 时间完成，作业6 在 6 11 时间完成，作业3 在11 15 时间完成，作业 1 在 1517 时间完成。注意到作业i 只能在一台机器上从 si时刻到si +ti时间完成且任何机器在同一时刻仅能处理一个作业，因此最短调度长度为17。m1作业 4m2作业 2作业 7m3作业 5作业 6作业 3作业 1时间654分配1617图 9三台机器的调度例如

5、在上述处理中，采用了最长时间优先LPT 的简单调度策略。在LPT算法中，作业按其所需时间的递减顺序排列，在分配一个作业时，将其分配给最先变为空闲的机器。四、参考文献1王红梅数据构造清华大学2王红梅数据构造学习辅导与实验指导清华大学3严蔚敏，吴伟民数据构造C 语言版清华大学专业资料整理WORD格式一、需求分析一程序的功能为给出的作业根据时间数分配机器。将作业按其所需时间的递减顺序排列。一台机器在同一时刻只能处理一个作业，在分配一个作业时，将其分配给最先变为空闲的机器。直到所有作业分配完毕。算出最短调度时间。二输入输出的要求每个作业的所需的时间数和机器数为输入。输出为每个作业所分配的机器每个机器所

6、完成的作业 ，以及最短调度时间。二、问题求解给出 7 个要完成的作业，作业所需的时间数分别为2, 14, 4, 16, 6, 5, 3 ，把这些作业在三台机器中完成。首先将7 个作业由大到小排序，排序后为16, 14, 6, 5, 4, 3, 2 ，接着开场为机器分配作业。作业由大到小分配。每个机器同一时间只能分配一个作业。在分配一个作业时，将其分配给最先变为空闲的机器，把 16 分配给机器一， 14 分配给机器二 , 6 分配给机器三。 比较三台机器完成作业所需时间数，机器三最小。所以机器三先空闲下来。把 5 分配给机器三，比较三台机器完成作业所需时间数，机器三最小。所以机器三先空闲下来。把

7、 4 分配给机器三，比较三台机器完成作业所需时间数，机器二最小。所以机器二先空闲下来。把 3 分配给机器二，比较三台机器完成作业所需时间数，机器三最小。所以机器三先空闲下来。把 2 分配给机器三，到此作业分配完毕。所需时间最长的机器上的所需时间就是最短调度时间。三、总体设计专业资料整理WORD格式程序设计组成框图：专业资料整理WORD格式开场机器二机器三机器一最小？最小？最小？机器一机器二机器三算出最短调度时间流程图：作业所需的时间数将时间数从大到小排序16机器一16143机器二176542机器三111517专业资料整理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+" 个机器空闲，可以开场下一个作业！ ");if(machines1=min)System.out.println(" 第 "+2+" 个机器空闲，可以开场下一个作业！ ");if(machines2=min) System.out.println("第 &qu

9、ot;+3+" 个机器空闲，可以开场下一个作业！ ");2、运用下面源代码计算最短调度时间int max=machines0;for(int i=0;i<machines.length;i+)if(machinesi>max)max=machinesi;五、调试与测试直接运行此程序。在控制台输出此程序的结果。每当出现机器空闲后，输入空闲的机器，继续下一步操作。直到作业分配完毕。专业资料整理WORD格式六、关键源程序清单和执行结果专业资料整理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;/ 准备调度的作业int N=works.length;System.out.print(" 准备调度的作业的时间数分别为：");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+)/ 对给出的作业时间数从大到小冒泡排序 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(" 开场作业！ ");System.out.println(" 机器 1 完成时间数为"+works0+" 的作业 ");machines1=works1;S

12、ystem.out.println(" 机器 2 完成时间数为 "+works1+" 的作业 "); machines2=works2;System.out.println(" 机器 3 完成时间数为"+works2+" 的作业 ");int min=machines0;for(int i=0;i<machines.length;i+)if(machinesi<min)min=machinesi;专业资料整理WORD格式if(machines0=min)System.out.println("

13、第 "+1+"个机器空闲，可以开场下一个作专业资料整理WORD格式业！ ");专业资料整理WORD格式if(machines1=min)System.out.println("第 "+2+"个机器空闲，可以开场下一个作专业资料整理WORD格式业！ ");专业资料整理WORD格式if(machines2=min)System.out.println("第 "+3+"个机器空闲，可以开场下一个作专业资料整理WORD格式业！ ");/专业资料整理WORD格式System.out.printl

14、n(" 开场下一个作业的机器是：");int shuru1=input.nextInt();专业资料整理WORD格式System.out.println(" 机器 "+shuru1+" 完成时间数为 "+works3+"machinesshuru1-1=machinesshuru1-1+works3;的作业");专业资料整理WORD格式min=machines0;for(int i=0;i<machines.length;i+)if(machinesi<min)min=machinesi;专业资料整理W

15、ORD格式if(machines0=min)System.out.println("第 "+1+"个机器空闲，可以开场下一个作专业资料整理WORD格式业！ ");专业资料整理WORD格式if(machines1=min)System.out.println("第 "+2+"个机器空闲，可以开场下一个作专业资料整理WORD格式业！ ");专业资料整理WORD格式if(machines2=min)System.out.println("第 "+3+"个机器空闲，可以开场下一个作专业资料整理

16、WORD格式业！ ");/专业资料整理WORD格式System.out.println(" 开场下一个作业的机器是：");int shuru2=input.nextInt();System.out.println(" 机器 "+shuru2+" 完成时间数为 "+works4+"machinesshuru2-1=machinesshuru2-1+works4;的作业");专业资料整理WORD格式min=machines0;for(int i=0;i<machines.length;i+)if(mac

17、hinesi<min)min=machinesi;专业资料整理WORD格式if(machines0=min)System.out.println("第 "+1+"个机器空闲，可以开场下一个作专业资料整理WORD格式业！ ");专业资料整理WORD格式if(machines1=min)System.out.println("第 "+2+"个机器空闲，可以开场下一个作专业资料整理WORD格式业！ ");专业资料整理WORD格式if(machines2=min)System.out.println("第

18、"+3+"个机器空闲，可以开场下一个作专业资料整理WORD格式业！ ");/专业资料整理WORD格式System.out.println("开场下一个作业的机器是：");专业资料整理WORD格式int shuru3=input.nextInt();System.out.println(" 机器 "+shuru3+" 完成时间数为 "+works5+" 的作业 "); machinesshuru3-1=machinesshuru3-1+works5;min=machines0;for(int i=0;i<machines.length;i+)if(machinesi<min)min=machinesi;专业资料整理WORD格式if(machines0=min)System.out.println("第 "+1+"个机器空闲，可以开场下一个作专业资料整理WORD格式业！ ");专业资料整理WORD格式if(machines1=min)System.out