| 基于总空闲时间增量的无等待流水调度混合遗传算法 |
| |
| 引用本文： | 朱夏,李小平,王茜. 基于总空闲时间增量的无等待流水调度混合遗传算法[J]. 计算机研究与发展, 2011, 48(3) |
| |
| 作者姓名： | 朱夏 李小平 王茜 |
| |
| 作者单位： | 1. 东南大学计算机科学与工程学院,南京,211189
2. 计算机网络和信息集成教育部重点实验室(东南大学),南京,211189 |
| |
| 基金项目： | 国家自然科学基金项目，国家"八六三"高技术研究发展计划基金项目 |
| |
| 摘 要： | 将NP-难的最小化最大完工时间无等待流水调度问题等价转化为最小化总空闲时间的问题,改变传统求解调度序列目标函数的模式,通过目标函数变化量判断新解的优劣,大大降低算法所需计算时间.分析启发式算法基本操作和进化算子的总空闲时间增量性质,设计基本总空闲时间增量法以快速评估新产生解的质量.提出混合遗传算法IHGA(increment based hybrid genetic algorithm)求解该问题,构造相应初始种群生成方法和进化算子,提出进化概率动态更新策略和种群收敛判断与再生机制;算法混合了迭代改进局部搜索以进一步提高解的质量,基于120个经典Benchmark实例,将IHGA与目前求解该问题的有效算法RAJ,GR,SA2,TSM和FCH进行比较,实验结果表明:IHGA在性能方面优于其他,计算效率方面优于SA2和TSM,略逊于GR,RAJ和FCH.
|
| 关 键 词： | 无等待 流水调度 总空闲时间增量 混合遗传算法 最大完工时间 |
Total-Idle-Time Increment Based Hybrid GA for No-Wait Flowshops with Makespan Minimization |
| |
| Zhu Xia,Li Xiaoping,Wang Qian. Total-Idle-Time Increment Based Hybrid GA for No-Wait Flowshops with Makespan Minimization[J]. Journal of Computer Research and Development, 2011, 48(3) |
| |
| Authors: | Zhu Xia Li Xiaoping Wang Qian |
| |
| Affiliation: | Zhu Xia,Li Xiaoping,and Wang Qian(School of Computer Science & Engineering,Southeast University,Nanjing 211189)(Key Laboratory of Computer Network and Information Integration(Southeast University),Ministry of Education,Nanjing 211189) |
| |
| Abstract: | No-wait flowshops with makespan minimization has been proved to be a kind of NP-hard combinatorial optimization problem.To solve this problem,it is equivalently transferred into the problem on total-idle-time minimization in this paper.Different from traditional methods in which objectives are completely computed for a new generated schedule,total-idle-time increment methods are presented in this paper.Whether a new schedule is better or worse than the original one is judged just by the total-idle-time incr... |
| |
| Keywords: | no-wait flowshops total-idle-time increment hybrid genetic algorithm makespan |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
