机器调度问题课设报告

机器调度问题课设报告课程设计报告3.2最短时间流程图开始开始机器一机器二机器三机器一最小？机器二最小？机器三最小？算出最短调度时间3.3伪代码为每个机器设计数据类型：structMachineNode{intID;//机器号intavail;//机器可用时刻};·为每个作业设计数据类型：structJobNode{intID;//作业号inttime;//处理时间};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<stdio.h>#defineN10//限定机器数和作业数不超过N个structMachineNode{ intID;//机器号 intavail;//机器可用时间};structJobNode{ intID;//作业号 inttime;//处理时间};voidBig(JobNoder[],intk,intm)//建立大根堆{ inti,j; i=k; j=2*i; while(j<=m) { if(j<m&&r[j].time<r[j+1].time) j++; if(r[i].time>r[j].time)break; else { inttemp1,temp2; temp1=r[i].time; r[i].time=r[j].time; r[j].time=temp1; temp2=r[i].ID; r[i].ID=r[j].ID; r[j].ID=temp2; } }}voidSortBig(JobNoder[],intn){for(inti=n/2;i>=1;i--)Big(r,i,n);}voidSmall(MachineNoder[],intk,intm)//建立小根堆{ inti,j; i=k; j=2*i; while(j<=m){ if(j<m&&r[j].avail>r[j+1].avail)j++; if(r[i].avail<r[j].avail)break; else { inttemp1,temp2; temp1=r[i].avail; r[i].avail=r[j].avail; r[j].avail=temp1; temp2=r[i].ID; r[i].ID=r[j].ID; r[j].ID=temp2; } }}voidSortSmall(MachineNoder[],intn){ for(inti=n/2;i>=1;i--) Small(r,i,n);}voidassign(MachineNodeM[],JobNodeJ[],intm,intj)//完成任务分配{ if(m>=j)//如果机器数m大于或等于作业数j { SortBig(J,j);//以各作业所需时间建立大根堆，堆顶元素即为最大耗时的作业所需时间 printf("一台机器完成一个作业，最大工作时间为:%d\n",J[1].time); } else//如果机器数m小于作业数j { for(inti=1;i<=m;i++)//先为每台机器分配一个作业，先把所需时间最大的m个作业分配给m台机器 { SortBig(J,j);//建立大根堆求堆顶元素确定其中耗时最大的作业 M[i].avail=J[1].time;//机器i的处理时间即为作业所需时间 printf("机器%d完成作业%d\n",M[i].ID,J[1].ID); for(intk=1;k<j;k++)//减去已分配的作业 J[k]=J[k+1]; j=j-1; } for(intq=j;j>=1;q--)//把剩余的j-m个作业分配下去（j=j-m） { SortSmall(M,m);//将m个机器按可用时建立小根堆 SortBig(J,j);//将j个作业按处理时间建立大根堆 printf("机器%d完成作业%d\n",M[1].ID,J[1].ID);//将大根堆的堆顶作业分配给小根堆的堆顶机器 M[1].avail+=J[1].time;//将小根堆的堆顶机器加上大根堆的堆顶作业的处理时间，重新插入小根堆（循环执行SortSmall(M,m)时完成） for(intk=1;k<j;k++)//减去已分配的作业 J[k]=J[k+1]; j=j-1; } printf("最短调度时间为:%d\n",M[1].avail);//小根堆的堆顶元素就是最短调用时间 }}voidmain(){ intj=0;//作业个数 intm=0;//机器个数 inti; MachineNodeM[N];//机器的结构体数组 JobNodeJ[N];//作业的结构体数组 printf("请输入作业个数\n"); scanf("%d",&j); printf("请输入每个作业需要的处理时间:\n"); for(i=1;i<=j;i++) { J[i].ID=i;//为每个作业确定序号 printf("第%d个作业：\n",i); scanf("%d",&J[i].time);//输入每个作业的用时 } printf("请输入机器数:\n"); scanf("%d",&m); for(i=1;i<=m;i++) M[i].ID=i; //为每台机器确定序号 assign(M,J,m,j);//调用完成分配任务的函数}7.体会与心得本次课程设计，使我对《数据结构》这门课程有了更深入的理解。《数据结构》是一门实践性较强的课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。

我们的课程设计题目是机器调度问题，刚开始做这个程序的时候，感到完全无从下手，甚至让我觉得完成这次程序设计根本就是不可能的，于是开始查阅各种资料以及参考文献，之后便开始着手写程序，写完运行时有很多问题，经常运行出现错误，但通过同学间的帮助最终基本解决问题。

在本课程设计中，我明白了理论与实际应用相结合的重要性，并提高了自己组织数据及编写大型程序的能力。培养了基本的、良好的程序设计技能以及合作能力。这次课程设计同样提高了我的综合运用所学知识的能力。并对VC有了更深入的了解。《数据结构》是一门实践性很强的课程，上机实习是对学生全面综合素质进行训练的一种最基本的方法，是与课堂听讲、自学和练习相辅相成的、必不可少的一个教学环节。上机实习一方面能使书本上的知识变“活”，起到深化理解和灵活掌握教学内容的目的;另一方面，上机实习是对学生软件设计的综合能力的训练，包括问题分析，总体结构设计，程序设计基本技能和技巧的训练。此外，还有更重要的一点是：机器是比任何教师更严厉的检查者。因此，在“数据结构”的学习过程中，必须严格按照老师的要求，主动地、积极地、认真地做好每一个实验，以不断提高