贪心算法多机调度问题

《贪心算法多机调度问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《算法设计与分析》实验报告2015-2016年第2学期实验班级：学生姓名：学号：指导老师：信息工程学院实验项目名称：贪心算法多机调度问题实验日期：2016年4月6日一、实验类型：验证性□设计性二、实验目的1、熟悉多机调度问题的算法；2、初步掌握贪心算法；三、实验内容与要求要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。四、实验步骤源程序：#include#include<

2、iostream>usingnamespacestd;typedefstructJob{intID;inttime;}Job;JobJ[10];typedefstructJobNode{intID;inttime;JobNode*next;}JobNode,*pJobNode;typedefstructHeader{ints;pJobNodenext;}Header,*pHeader;intl=1;intmain(){HeaderM[10];intm,n;cout<<"请输入数据的作业的个数与机器的个数"<

3、in>>n>>m;cout<<"请输入所有的任务的相关数据"<>J[l].ID>>J[l].time;intSelectMin(Header*M,intm);for(l=1;l<=n;l++)cout<<"第"<

4、nti=1;i<=m;i++){if(M[i].s<=M[l].s)k=i;}M[k].s+=J[l].time;returnk;}五、实验结果1、实验图形图1图22、结果分析如上面第一个图所示当输入数据作业的个数与机器的个数为4和3的时候,输入的所有任务相关的数据为12345678,第一个任务在第M3台机器上完成,第二个任务在第M2台机器上完成,第三个任务在第M1台机器上完成,第四个任务在第M3台机器上完成,如上面第二个图所示当输入数据作业的个数与机器的个数为5和1的时候,输入的所有任务相关的数据为1262819543

5、7,第一个任务在第M1台机器上完成,第二个任务在第M1台机器上完成,第三个任务在第M1台机器上完成,第四个任务在第M1台机器上完成,第四个任务在第M1台机器上完成。六、实验总结本次的实验主要是为了让我们熟悉多机调度问题的算法并且能够初步的掌握贪心算法。一开始的时候没弄明白什么是多机调度，后来通过老师的讲解也是一知半解，最后还是通过网上查阅相关资料，并且看了一下视频才弄清楚。本次的实验首先我们需要把作业按加工所用的时间从大到小排序；然后如果作业数目比机器的数目少或相等，则直接把作业分配下去；最后如果作业数目比机器的数目多，

6、则每台机器上先分配一个作业，如下的作业分配时，是选那个表头上最小的链表加入新作业。总之此次的实验不仅让我们在一定程度上了解了多机度问题，并且初步了解掌握了贪心算法，还提高了我们分析和解决问题的能力。