| 带释放时间的并行机调度问题的ILS & SS算法 |
| |
| 引用本文： | 罗家祥,唐立新. 带释放时间的并行机调度问题的ILS & SS算法[J]. 自动化学报, 2005, 31(6) |
| |
| 作者姓名： | 罗家祥 唐立新 |
| |
| 基金项目： | 国家重点基础研究发展计划(973计划)，中国科学院资助项目，高等学校优秀青年教师教学科研奖励计划 |
| |
| 摘 要： | 研究工件带释放时间的两类并行机最小化总完成时间的调度问题.针对问题提出了一种新的基于变深度环交换邻域结构的Iterated local search(ILS)算法.1)提出了变深度环交换邻域结构.2)基于变深度环交换和传统Swap的混合邻域,提出了带有两种kick策略的ILS算法.3)为了加强ILS逃出局部最优的能力,将Scatter search(SS)搜索方法引入了ILS算法中;算法将当前最好解和次好解进行分散处理,再从处理后的解开始继续迭代.为了验证算法的有效性,对两类并行机问题分别随机产生100组数据进行试验.实验结果表明:对于同构并行机问题,引入SS的ILS算法的计算结果与下界的平均偏差为0.99%,而没有引入SS的ILS算法的为1.06%;对于无关并行机问题,引入SS搜索方法后,ILS算法的计算结果改进了6.06%,并明显优于多点下降算法.
|
| 关 键 词： | 并行机 变深度环交换 ILS算法 SS算法 |
A New ILS & SS Algorithm for Parallel-machine Scheduling Problem |
| |
| LUO Jia-Xiang,TANG Li-Xin. A New ILS & SS Algorithm for Parallel-machine Scheduling Problem[J]. Acta Automatica Sinica, 2005, 31(6) |
| |
| Authors: | LUO Jia-Xiang TANG Li-Xin |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 万方数据 等数据库收录！ |
|
