带释放时间的并行机调度问题的ILS & SS算法

摘要：

研究工件带释放时间的两类并行机最小化总完成时间的调度问题.针对问题提出了一种新的基于变深度环交换邻域结构的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算法

所属期刊栏目：31

分类号：N49(普及读物)

资助基金：国家重点基础研究发展计划973计划70425003;中国科学院资助项目70171030,60274049;高等学校优秀青年教师教学科研奖励计划教育司[2002]383

在线出版日期：2005-12-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：917-924