文献类型：期刊文献

中文题名：最小化时间表长的平行机调度近似算法研究

英文题名：APPROXIMATED ALGORITHM FOR IDENTICAL MACHINE SCHEDULING WITH MINIMIZED MAKESPANS

作者：程贞敏[1];李洪兴[2];谷敏强[3]

第一作者：程贞敏

机构：[1]北京联合大学商务学院;[2]大连理工大学电子与信息工程学院;[3]汕头大学理学院数学系

第一机构：北京联合大学商务学院

年份：2012

卷号：48

期号：1

起止页码：11-15

中文期刊名：北京师范大学学报：自然科学版

收录：CSTPCD;;北大核心:【北大核心2011】；CSCD:【CSCD2011_2012】；

基金：北京市教委科技面上资助项目(SQKM201211417015);北京联合大学科研基金资助项目(zk201005x)

语种：中文

中文关键词：平行机调度;周期维护;时间表长;近似算法;最坏误差界

外文关键词：identical machine scheduling,periodical maintenance makespans； approximative algorithm； worst-case bound；

摘要：讨论机器具有固定周期维护t,目标函数为最小化时间表长的m台平行机调度问题.这是一个NP-难的问题.关于该问题主要分析了当维护时间t≤T/3时,利用经典的装箱算法FFD我们可以得到关于该问题的一个近似算法FFPTD.该算法的最坏误差界为2,最后以实例说明2为该算法的紧界.
Identical machine scheduling with periodic maintenance was considered.The objective was to minimize make-spans.It was a NP-hard problem.An approximated algorithm was proposed to solve this problem with the bins packing algorithm FFD.For the case t≤T/3,the worst-case bound was 2.An example was given to illustrate that 2 was a tight bound.