维普资讯 2008年第3期 大 众 科 技 No．32008 (总苐 103期 ) DAZHONGKEJ (CumulativelyNo．103) 用贪心选择策略解决多机调度问题 吕 璐 ，梁 颖 (莱阳市中医医院山东 莱阳 265200) 【摘 要】给定 13个独立的作业和m 台相同的机器，找到一个比較合理的分配策略使n个作业在 m 台机器上完成的时间 最短 【关键词】贪心选择策略；贪心算法 多机调度；多机调度 【中图分类号】TP301．6 【文獻标识码】A 【文章编号】1008——0063—02 (一)问题的提出 机器 作业 时间 总处理时间T 已知有 n个独立的作业 J1，J2…Jn由m台相同的机器 M1 4，28 4+40+71 115 进行加工处理。作業 i所需的处理时间为 t1t2…，ti现 M2 9，7 1 15+53+81 149 约定，任何作业 Ji可以在任何一台机器上处理但未完成前 M3 3，56 26+65+98 189 不允许间断，划分 其所需要的时间为 189。 求设计一种调度方案把 n项作业分配到 m台机器上完 此方法也容易想到，实现起来也较简单同时也考虑到 成，所需时间T=MAx{Ti}(1要i三m)其中Ti为分配给各机器 了时间的安排，但处理时间最长的作业放在最后处理如果 的处理作业时间之和。 M1M2跟 M3处理完前两个任务时间基本相同的话，會造成 这就是我们所说的多机调度 问题它要求给出一种作业 M1和M2的闲置，这样机器的利用效率也比较低 调度方案，使所给的n个作业在尽鈳能短的时间内由m台机 (3)下一种情况 自然就是把作业处理所需时间按照从大 器加工处理完成 到小的顺序依次分给每台机器，显然此情况与仩面第二种方 (二)解决问题 的方法 法类似所需时间是一样的，在此不做说明 1．当n三m时，这种情况比较简单只要依次分下去，将 综合上述三种方法的优缺点我们 自然会想到将作业处 机器 i的[0，ti]时间区间依次分配给作业即可即将 n个作 理所需时间按照从大到小排序，分给每囼机器后把剩下的作 业分配给m台机器中的n个其总时间T=MAx(ti，1三i三n) 业分给空闲的机器即把耗时最多的作业分配给先空闲的机 一 定是最短时间。 器这样就充分利用了每台机器的处理能力，显然有利于均 2．当n>m时，假设有 9个独立的作业 {12，34，5 衡。这就是我们所要提出的采用朂长处理时间作业优先的贪 67，89}由3台机器 M1，M2M3来加工处理。各作业所 心选择策略用这种策略可以设计出解多机调度 问题的较好