机器调度问题课设报告.doc

目录1.课程设计题目及实现功能12.设计内容12.1问题描述12.2基本要求12.3设计思想13.概要设计23.1算法设计23.2最短时间流程图33.3伪代码34.详细设计44.1需求分析44.2问题求解45.测试与调试56.程序清单57.体会与心得9参考文献101课程设计报告 1.课程设计题目及实现功能课程设计题目：机器调度问题实现功能：怎样安排机器上的具体作业数2.设计内容2.1问题描述机器调度是指有m台机器需要处理n个作业，设作业i的处理时间为ti，则对n个作业进行机器分配，使得：(1) 一台机器在同一时间内只能处理一个作业；(2) 一个作业不能同时在两台机器上处理；(3) 作业i一旦运行，则需要ti个连续时间单位。设计算法进行合理调度，使得在m台机器上处理n个作业所需要的处理时间最短。2.2基本要求(1) 建立问题模型，设计数据结构；(2) 设计调度算法，为每个作业分配一台可用机器；(3) 给出分配方案。2.3设计思想假设有七个作业，所需时间分别为2, 14, 4, 16, 6, 5, 3，有三台机器，编号分别为m1、m2和m3。这七个作业在三台机器上进行调度的情形如图9所示，阴影区代表作业的运行区间。作业4在0到16时间被调度到机器1上运行，在这16个时间单位中，机器1完成了对作业4的处理；作业2在0到14时间被调度到机器2上处理，之后机器2在14到17时间处理作业7；在机器3上，作业5在06时间完成，作业6在611时间完成，作业3在1115时间完成，作业1在1517时间完成。注意到作业i只能在一台机器上从si时刻到si +ti时间完成且任何机器在同一时刻仅能处理一个作业，因此最短调度长度为17。m1m2m3时间分配 作业5作业6 作业3作业1作业2 作业7 作业41716图9 三台机器的调度示例6543.概要设计 3.1算法设计作业所需的时间数机器一机器二机器三将时间数从大到小排序16146541115317172163.2最短时间流程图开始机器一机器二机器三机器一最小？机器二最小？机器三最小？算出最短调度时间3.3伪代码为每个机器设计数据类型： struct MachineNode int ID; /机器号int avail; /机器可用时刻 ; 为每个作业设计数据类型： struct JobNode int 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.3 将堆H1的堆顶作业分配给堆H2的堆顶机器； 2.4 将H2的堆顶机器加上H1的堆顶作业的处理时间重新插入h2中； 2.5 将堆H1的堆顶元素删除；3. 堆H2的堆顶元素就是最短调度时间；4.详细设计4.1需求分析程序的功能：为给出的作业根据时间数分配机器。将作业按其所需时间的递减顺序排列。一台机器在同一时刻只能处理一个作业，在分配一个作业时，将其分配给最先变为空闲的机器。直到所有作业分配完毕。算出最短调度时间。输入输出的要求：每个作业的所需的时间数和机器数为输入。输出为每个作业所分配的机器（每个机器所完成的作业），以及最短调度时间。4.2问题求解给出7个要完成的作业，作业所需的时间数分别为2, 14, 4, 16, 6, 5, 3，把这些作业在三台机器中完成。首先将7个作业由大到小排序，排序后为16, 14, 6, 5, 4, 3, 2，接着开始为机器分配作业。作业由大到小分配。每个机器同一时间只能分配一个作业。在分配一个作业时，将其分配给最先变为空闲的机器，把16分配给机器一，14分配给机器二, 6分配给机器三。比较三台机器完成作业所需时间数，机器三最小。所以机器三先空闲下来。把5分配给机器三，比较三台机器完成作业所需时间数，机器三最小。所以机器三先空闲下来。把4分配给机器三，比较三台机器完成作业所需时间数，机器二最小。所以机器二先空闲下来。把3分配给机器二，比较三台机器完成作业所需时间数，机器三最小。所以机器三先空闲下来。把2分配给机器三，到此作业分配完毕。所需时间最长的机器上的所需时间就是最短调度时间。5.测试与调试直接运行此程序。去取一组测试数据在控制台输出此程序的结果。6.程序清单#include#define N 10 /限定机器数和作业数不超过N个struct MachineNodeint ID; /机器号int avail; /机器可用时间;struct JobNodeint ID; /作业号int time; /处理时间;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; else int 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 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大于或等于作业数jSortBig(J,j); /以各作业所需时间建立大根堆，堆顶元素即为最大耗时的作业所需时间printf(一台机器完成一个作业，最大工作时间为:%dn,J1.time);else /如果机器数m小于作业数jfor(int i=1;i=m;i+) /先为每台机器分配一个作业，先把所需时间最大的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); /将大根堆的堆顶作业分配给小根堆的堆顶机器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);scanf(%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.体会与心得本次课程设计，使我对数据结构这门课程有了更深入的理解。数据结构是一门实践性较强的课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。我们的课程设计题目是机器调度问题，刚开始做这个程序的时候，感到完全无从下手，甚至让我觉得完成这次程序设计根本就是不可能的，于是开始查阅各种资料以及参考文献，之后便开始着手写程序，写完运行时有很多问题，经常运行出现错误，但通过同学间的帮助最终基本解决问题。在本课程设计中，我明白了理论与实际应用相结合的重要性，并提高了自己组织数据及编写大型程序的能力。培养了基本的、良好的程序设计技能以及合作能力。这次课程设计同样提高了我的综合运用所学知识的能力。并对VC有了更深入的了解。数据结构是一门实践性很强的课程，上机实习是对学生全面综合素质进行训练的一种最基本的方法，是与课堂听讲、自学和练习相辅相成的、必不可少的一个教学环节。上机实习一方面能使书本上的知识变“活”，起到深化理解和灵活掌握教学内容的目的;另一方面，上机实习是对学生软件设计的综合能力的训练，包括问题分析，总体结构设计，程序设计基本技能和技巧的训练。此外，还有更重要的一点是：机器是比任何教师更严厉的检查者。因此，在“数据结构”的学习过程中，必须严格按照老师的要求，主动地、积极地、认真地