《机器调度问题课设报告》由会员分享，可在线阅读，更多相关《机器调度问题课设报告（12页珍藏版）》请在金锄头文库上搜索。
1、目录1. 课程设计题目及实现功能 12. 设计内容 12.1 问题描述 12.2 基本要求 12.3 设计思想 13. 概要设计 23.1 算法设计 23.2 最短时间流程图 33.3 伪代码 34. 详细设计 44.1 需求分析 44.2 问题求解 45. 测试与调试 56. 程序清单 57. 体会与心得 9参考文献 10课程设计报告1. 课程设计题目及实现功能课程设计题目：机器调度问题实现功能：怎样安排机器上的具体作业数2. 设计内容2.1 问题描述机器调度是指有m台机器需要处理n个作业，设作业i的处理时间为ti,则 对 n 个作业进行机器分配，使得：(1) 一台机器在同一时间内只能处理一
2、个作业；(2) 一个作业不能同时在两台机器上处理；(3) 作业 i 一旦运行，则需要 t i 个连续时间单位。设计算法进行合理调度，使得在m台机器上处理n个作业所需要的处理时间 最短 。2.2 基本要求(1) 建立问题模型，设计数据结构；(2) 设计调度算法，为每个作业分配一台可用机器；(3) 给出分配方案。2.3 设计思想假设有七个作业，所需时间分别为 2, 14, 4, 16, 6, 5, 3 ，有三台机器， 编号分别为m、m和m。这七个作业在三台机器上进行调度的情形如图 9所示， 阴影区代表作业的运行区间。作业 4 在 0 到 16时间被调度到机器 1 上运行，在 这 16 个时间单位中
3、， 机器 1 完成了对作业 4 的处理；作业 2在 0到 14时间被调 度到机器 2 上处理，之后机器 2 在 14 到 17 时间处理作业 7；在机器 3 上，作业 5在06时间完成，作业6在611时间完成，作业3在1115时间完成，作 业1在1517时间完成。注意到作业i只能在一台机器上从Si时刻到Si +ti时 间完成且任何机器在同一时刻仅能处理一个作业，因此最短调度长度为 17。m2作业2作业7m3作业5作业6作业3作业1作业4mi时间6 -5-4 _分 己 一一-一一一-一 -一一 16 一一一-一一一-一、j17图9三台机器的调度示例3. 概要设计3.1算法设计3.2最短时间流程图
4、111F机器一机器二机器三算出最短调 度时间3.3伪代码为每个机器设计数据类型：struct Mach in eNodeint ID; 机器号int avail; /机器可用时刻；为每个作业设计数据类型：struct JobNodeint ID;/作业号int time;/处理时间;LPT 算法用伪代码描述如下：1. 如果作业数n电器数m，则1.1 将作业 i 分配到机器 i 上；1.2 最短调度长度等于 n 个作业中处理时间最大值；2. 否则，重复执行以下操作，直到 n 个作业都被分配：2.1将n个作业按处理时间建成一个大根堆 H1;2.2 将 m 个机器按可用时刻建立一个小根堆 H2；2.
5、3 将堆 H1 的堆顶作业分配给堆 H2 的堆顶机器；2.4 将 H2 的堆顶机器加上 H1 的堆顶作业的处理时间重新插入 h2 中；2.5 将堆 H1 的堆顶元素删除；3. 堆 H2 的堆顶元素就是最短调度时间；4. 详细设计4.1 需求分析程序的功能： 为给出的作业根据时间数分配机器。将作业按其所需时间的递减顺序排列。一台机器在同一时刻只能处理一个作业， 在分配一个作业时， 将其分配给最先变 为空闲的机器。直到所有作业分配完毕。算出最短调度时间。输入输出的要求：每个作业的所需的时间数和机器数为输入。输出为每个作业所分配的机器 （每个机器所完成的作业） ，以及最短调度时间。4.2 问题求解给
6、出 7个要完成的作业，作业所需的时间数分别为 2, 14, 4, 16, 6, 5, 3， 把这些作业在三台机器中完成。 首先将 7个作业由大到小排序， 排序后为 16, 14, 6, 5, 4, 3, 2，接着开始为机器分配作业。作业由大到小分配。每个机器同一时间只能分配一个作业。在分配一个作业时，将其分配给最先变为空闲的机器，把 1 6分配给机器一， 1 4分配给机器二 , 6 分配给机器三。比较三台机器完 成作业所需时间数，机器三最小。所以机器三先空闲下来。把 5 分配给机器三，比较三台机器完成作业所需时间数，机器三最小。所以机器二先空闲下来。把4分配给机器三，比较三台机器完成作业所需时
7、间数，机器二最小。所以 机器二先空闲下来。把3分配给机器二，比较三台机器完成作业所需时间数，机器三最小。所以 机器三先空闲下来。把2分配给机器三，到此作业分配完毕。所需时间最长的机器上的所需时间 就是最短调度时间。5. 测试与调试直接运行此程序。去取一组测试数据在控制台输出此程序的结果C:User,lenovoesktopDebLigM exe6. 程序清单#in clude#define N 10限定机器数和作业数不超过N个struct Mach in eNodeint ID; /机器号int avail; / 机器可用时间;struct JobNodeint ID; /作业号int tim
8、e; / 处理时间;void Big(JobNode r,int k,int m)/ 建立大根堆int i,j;i=k;j=2*i;while(j=m)if(jm&rj.timerj.time)break;elseint temp1,temp2; temp1=ri.time;ri.time=rj.time; rj.time=temp1;temp2=ri.ID;ri.ID=rj.ID;rj.ID=temp2;void SortBig(JobNode r,int n)for(int i=n/2;i=1;i-)Big(r,i,n);void Small(MachineNode r,int k,int
9、 m)/ 建立小根堆int i,j;i=k;j=2*i;while(j=m)if(jrj+1.avail)j+; if(ri.avail=1;i-)Small(r,i,n);/完成任务分配void assign(MachineNode M,JobNode J,int m,int j)if(m=j)/如果机器数 m 大于或等于作业数SortBig(J,j);/以各作业所需时间建立大根堆， 堆顶元素即为最大耗时的作业所需时间printf( 一台机器完成一个作业，最大工作时间为 :%dn,J1.time);else /如果机器数 m 小于作业数 jfor(int i=1;i=m;i+) / 先为每台
10、机器分配一个作业， 先把所需时间最大的 m 个 作业分配给 m 台机器SortBig(J,j); /建立大根堆求堆顶元素确定其中耗时最大的作业Mi.avail=J1.time; / 机器 i 的处理时间即为作业所需时间 printf( 机器 %d 完成作业 %dn,Mi.ID,J1.ID);for(int k=1;k=1;q-) / 把剩余的 j-m 个作业分配下去( j=j-m )SortSmall(M,m); / 将 m 个机器按可用时建立小根堆SortBig(J,j); /将 j 个作业按处理时间建立大根堆printf( 机器 %d 完成作业 %dn,M1.ID,J1.ID);/将大根堆
11、的堆顶作业分配给小根堆的堆顶机器M1.avail+=J1.time; / 将小根堆的堆顶机器加上大根堆的堆顶作业的处 理时间，重新插入小根堆(循环执行 SortSmall(M,m) 时完成)for(int k=1;kj;k+)/ 减去已分配的作业Jk=Jk+1;j=j-1;printf( 最短调度时间为 :%dn,M1.avail); /小根堆的堆顶元素就是最短调用时间void main()int j=0; /作业个数int m=0; / 机器个数int i;MachineNode MN;/ 机器的结构体数组JobNode JN;/作业的结构体数组printf（ 请输入作业个数 n）;scan
12、f（%d,&j）;printf（ 请输入每个作业需要的处理时间 :n）;for(i=1;i=j;i+)/为每个作业确定序号/输入每个作业的用时/为每台机器确定序号 /调用完成分配任务的函数Ji.ID=i;printf( 第 %d 个作业： n,i); scanf(%d,&Ji.time);printf( 请输入机器数 :n); scanf(%d,&m);for(i=1;i=m;i+)Mi.ID=i;assign(M,J,m,j);7. 体会与心得本次课程设计，使我对数据结构这门课程有了更深入的理解。数据结 构是一门实践性较强的课程， 为了学好这门课程， 必须在掌握理论知识的同时， 加强上机实践
13、。我们的课程设计题目是机器调度问题， 刚开始做这个程序的时候， 感到完全 无从下手， 甚至让我觉得完成这次程序设计根本就是不可能的， 于是开始查阅各 种资料以及参考文献， 之后便开始着手写程序， 写完运行时有很多问题， 经常运 行出现错误，但通过同学间的帮助最终基本解决问题。在本课程设计中， 我明白了理论与实际应用相结合的重要性， 并提高了自己 组织数据及编写大型程序的能力。 培养了基本的、 良好的程序设计技能以及合作 能力。这次课程设计同样提高了我的综合运用所学知识的能力。并对VC有了更 深入的了解。 数据结构是一门实践性很强的课程，上机实习是对学生全面综 合素质进行训练的一种最基本的方法，是与课堂听讲、自学和练习相辅相成的、 必不可少的一个教学环节。上机实习一方面能使书本上的知识变“活”，起到深
