湖南涉外经济学院 计算机科学与技术专业 《算法设计与分析》课程 多机调度问题 实 验 报 告 班级： 计 科 1 0 0 2 学号： *************** 姓名： 教师： 成绩： 2 0 1 2 年 5 月 【实验目的】 1 掌握贪心算法 2 利用贪心算法解决多机调度问题 3 分析实验结果，是否能将机器处理时间最短化 【系统环境】 Windows 7 平台 【实验工具】 VC++6.0 英文企业版 【问题描述】 描述： 设有n 个独立的作业{ 1,2，…，n} ，由 m 台相同的机器进行加工处理。作业i 所需的处理时间为 t。现约定，任何作业可以在任何一台机器上加工处理，但未完工前不允许中断处理。任何作业不能拆分成更小的子作业。 多机调度问题要求给出一种作业调度方案，使所给的n 个作业在尽可能短的时间内由 m 台机器加工处理完成。 例： 设7 个独立作业{ 1,2,3,4,5,6,7}有3 台机器m1，m2，m3 来加工处理。各作业所需的处理时间分别为{ 2,14,4,16,6,5,3} 。现要求用贪心算法给出最优解。 【实验原理】 贪心算法的应用，该算法总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义 上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。 贪心法基本策略： 1、分析问题性质，确定适当的贪心选择标准 ； 2、按 贪心选择标准 对n 个输 入 进行排 序 ，初 始 化部分解； 3、按 序 每 次 输 入 一个量 ，如 果这 个输 入 和 当前已 构 成在这 种选择标准 下 的部分 解加在一起 不能产生一个可行解，则 此 输 入 不能加入 到部分解中，否则 形 成新 的部分解； 4、继 续 处理下 一输 入 ，直 至 n 个输 入 处理完毕 ，最终 的部分解即 为此 问题的最优解。 【源程序代码】 #include #define N 10 typedef struct node { int ID,time;//作业所需时间 }jobnode; typedef struct Node { int ID,avail;//ID 机器编号 avail 每次作业的初始时间 }manode; manode machine[N]; jobnode job[N]; /* 找出下个作业执行机器 */ manode* Find_min(manode a[],int m) { manode* temp=&a[0]; for(int i=1;iavail) temp=&a[i]; } return temp; } /* 对作业时间由大...
VIP
