带不可用时间段和恶化加工时间的单机调度

• 作者: 左春荣 杨善林 马英
• 来源期刊: 系统工程学报
• 学科: 工学
• 关键词: 单机调度 不可用时间段 恶化加工时间 动态规划 启发式算法
• 年，卷（期）: 2010,（3）
• 页码范围: 371-378
• 分类号: O221|F406.2|TP301
• 字数: 5547字
• 语种: 中文

摘要

对机器带有一个不可用时间段并且加工时间恶化的不可续型单机最大完工时间调度问题进行了研究,简单说明了此问题的NP-困难性,提出了一种动态规算法以得到最优解,并给出了最短正常加工时间优先规则的最坏情况误差界限,最后提出了一种启发式算法采寻求近似解.实验结果表明该启发式算法无论从时间上还是解的质量上都是非常优异的,与动态规划给出的最优解相比,其平均相对误差仅为0.082%,最大误差也仅为3.448%,并且将近有一半的算例能得到最优解.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨善林	合肥工业大学管理学院	440	7797	38.0	67.0
3	左春荣	合肥工业大学管理学院	35	241	11.0	13.0
5	马英	合肥工业大学管理学院	16	161	8.0	12.0