最小化最大延误无等待流水车间调度问题的禁忌搜索算法

• 作者: 李小平 王初阳 王茜
• 来源期刊: 东南大学学报（英文版）
• 学科: 工学
• 关键词: 禁忌搜索 无等待流水车间 调度 最大延误 邻域
• 年，卷（期）: 2010,（1）
• 页码范围: 26-30
• 分类号: TP278
• 字数: 2171字
• 语种: 英文
• DOI: 10.3969/j.issn.1003-7985.2010.01.006

摘要

为求解最小化最大延误无等待流水车间调度问题,提出了3个基于任务块交换的邻域,其中块交换邻域的规模为O(n4),块对换和简化块交换邻域的规模为D(n3).所提邻域的规模均大于现有邻域,因此可提高局部搜索算法的解质量.给出了3个邻域的加速性质,使一个相邻解的评估时间为常量,邻域的评估时间与其规模成正比.同基于支配规则的加速方法相比,所提出的加速性质适用于任何机器数.在禁忌搜索中比较了3个邻域,以及块对换和简化块交换邻域的并集.标准实例集上的计算结果表明:3个基于O(n3)邻域的禁忌搜索算法均好于现有算法;在所有的测试算法中,采用邻域并集的禁忌搜索算法的性能最好.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王茜	东南大学计算机科学与工程学院	60	1157	18.0	32.0
2	李小平	东南大学计算机科学与工程学院	31	465	11.0	21.0
3	王初阳	东南大学计算机科学与工程学院	1	2	1.0	1.0