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

• 作者: 唐立新 罗家祥
• 来源期刊: 自动化学报
• 学科: 地球科学
• 关键词: 并行机 变深度环交换 ILS算法 SS算法
• 年，卷（期）: 2005,（6）
• 所属期刊栏目: 论文与报告
• 页码范围: 917-924
• 页数: 8页
• 分类号: N49
• 字数: 4945字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	唐立新	东北大学信息科学与工程学院	106	2154	24.0	41.0
2	罗家祥	东北大学教育部暨辽宁省流程工业综合自动化重点实验室	3	26	2.0	3.0