贪心算法多机调度问题

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

2、int time;Job;Job J10;typedef struct JobNodeint ID;int time;JobNode *next;JobNode,*pJobNode;typedef struct Headerint s;pJobNode next;Header,*pHeader;int l=1;int main()Header M10;int m,n;cout请输入数据的作业的个数与机器的个数nm;cout请输入所有的任务的相关数据endl;for(int i=1;i=m;i+)Mi.s=0;for(int l=1;lJl.IDJl.time;int SelectMin(Hea

3、der *M,int m);for(l=1;l=n;l+)cout第l个任务在第MSelectMin(M,m)台机器上完 成endl;return 0;int SelectMin(Header *M,int m)int k=1;for(int i=1;i=m;i+)if(Mi.s=Ml.s) k=i;Mk.s+=Jl.time; return k;五、实验结果1、实验图形I G:2016M?glADebug2.exe 成成成成sss兀I G:2016M?glADebug2.exe 成成成成sss兀ue上上上上in 7oo7no7oo7o n矶矶机叽co -4HSH口 o7第第第第ey 6在在在

4、在k s务务务务叫a 3ATTTTss 2 12 3 4 e1第第第第pp请输入数据的作业的个数与机器的个数5 1请输入所有的任务的相关数据成成成成成 成成成成成 SS3兀元ue 上上上上上in 7 n 3fflffl叽ffl巩co 4-4sfiafi口 D 1 i 1 1 1 t yMMMMMMMMey 1在在在在在k 8务务务务务ny EEEErr aTTTTTss12 3 4 5 eTi pAn Fgpa-ZTIF.r2、结果分析如上面第一个图所示当输入数据作业的个数与机器的个数为4和3的时候, 输入的所有任务相关的数据为1 2 3 4 5 6 7 8,第一个任务在第M3台机器上完成,

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