| 带不可用时间段的部分可续型单机最大完工时间调度 |
| |
| 引用本文： | 马英,杨善林,储诚斌.带不可用时间段的部分可续型单机最大完工时间调度[J].系统工程理论与实践,2009,29(4):128-134. |
| |
| 作者姓名： | 马英 杨善林 储诚斌 |
| |
| 作者单位： | 1. 合肥工业大学管理学院,合肥230009;过程优化与智能决策教育部重点实验室,合肥230009
2. 合肥工业大学管理学院,合肥230009;特鲁瓦工业大学工业系统优化实验室,特鲁瓦10010 |
| |
| 基金项目： | 国家自然科学基金，国家高技术研究发展计划(863计划) |
| |
| 摘 要： | 研究了机器带有一个不可用时间段的单机最小化最大完工时间调度问题,并假定被中断工件是部分可续的,即其已加工部分在机器重新可用之后需部分进行重新加工.文中简单说明了此问题为NP-难问题,并证明了最大加工时间优先LPT规则的误差上限是α/2（其中α为重加工系数），且举例说明该界限是紧的。在此基础上，简单地说明了该算法对不可续型问题的误差上限是1/2，而不是有关文献所证明的1/3，同时上例也是1/3误差上限的反例。还提出了一个启发式算法，实验结果证明了此算法的高效性，对不同参数对此算法性能的影响也进行了分析。
|
| 关 键 词： | 单机调度 部分可续型 最长加工时间优先 |
Minimizing makespan in semiresumable case of single-machine scheduling with an availability constraint |
| |
| MA Ying,YANG Shan-lin,CHU Cheng-bin.Minimizing makespan in semiresumable case of single-machine scheduling with an availability constraint[J].Systems Engineering —Theory & Practice,2009,29(4):128-134. |
| |
| Authors: | MA Ying YANG Shan-lin CHU Cheng-bin |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《系统工程理论与实践》浏览原始摘要信息 |
| 点击此处可从《系统工程理论与实践》下载免费的PDF全文 |
