A tabu search/path relinking algorithm to solve the job shop scheduling problem
A tabu search/path relinking algorithm to solve the job shop scheduling problem
复制标题
解决作业车间调度问题的禁忌搜索/路径重链接算法
DOI：
10.1016/j.cor.2014.08.006
复制
发表时间：
2014-02
影响因子：
4.6
通讯作者：
Cheng T. C. E.
中科院分区：
文献类型：
--
作者：
Peng Bo;Lu Zhipeng;Cheng T. C. E.
本文提出了一种将禁忌搜索过程整合到路径链接框架中的算法，以生成作业车间调度问题（JSP）的解。该禁忌搜索/路径重链接（TS/PR）算法具有几个显著特征，包括通过特定的重链接程序有效构建连接起始解和引导解的路径，以及基于两种改进方法的参考解确定机制。我们在文献中几乎所有可用的基准JSP实例上评估TS/PR的性能。测试结果表明，与文献中最先进的JSP算法相比，TS/PR获得了具有竞争力的结果，证明了其在解决方案质量和计算效率方面的有效性。特别是，TS/PR能够提高205个测试实例中的49个的上限，并解决了一个20多年来一直未解决的具有挑战性的实例。
We present an algorithm that incorporates a tabu search procedure into the framework of path relinking to generate solutions to the job shop scheduling problem (JSP). This tabu search/path relinking (TS/PR) algorithm comprises several distinguishing features, such as a specific relinking procedure to effectively construct a path linking the initiating solution and the guiding solution, and a reference solution determination mechanism based on two kinds of improvement methods. We evaluate the performance of TS/PR on almost all of the benchmark JSP instances available in the literature. The test results show that TS/PR obtains competitive results compared with state-of-the-art algorithms for JSP in the literature, demonstrating its efficacy in terms of both solution quality and computational efficiency. In particular, TS/PR is able to improve the upper bounds for 49 out of the 205 tested instances and it solves a challenging instance that has remained unsolved for over 20 years.
登录
查看更多内容
影响因子：
5.4
作者：
Balas, E;Vazacopoulos, A
通讯作者：
Vazacopoulos, A
影响因子：
2
作者：
Nowicki, E;Smutnicki, C
通讯作者：
Smutnicki, C
影响因子：
2.2
作者：
De Leone
通讯作者：
De Leone
DOI：
10.1016/j.ejor.2012.03.001
发表时间：
2012-08
期刊：
Eur. J. Oper. Res.
影响因子：
--
作者：
Liji Shen;U. Buscher
通讯作者：
Liji Shen;U. Buscher
DOI：
10.1287/ijoc.6.2.108
发表时间：
1994-05
期刊：
INFORMS J. Comput.
影响因子：
--
作者：
É. Taillard
通讯作者：
É. Taillard