A hybrid Differential Evolution - Tabu Search algorithm for the solution of Job-Shop Scheduling Problems
A hybrid Differential Evolution - Tabu Search algorithm for the solution of Job-Shop Scheduling Problems
复制标题
DOI：
10.1016/j.asoc.2012.07.034
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Antonin Ponsich;C. Coello
中科院分区：
文献类型：
--
作者：
Antonin Ponsich;C. Coello
作业车间调度问题（Job-Shop Scheduling Problem， JSSP）在过去的几十年里引起了人们极大的兴趣，主要是因为它的组合特性使得它很难求解。局部搜索程序，特别是Nowicki和Smutnicki的i-TSAB算法所取得的良好性能，鼓励了研究者将这种局部搜索引擎与全局方法相结合。差分进化（DE）是一种进化算法，它被发现对连续优化特别有效，但在应用于排列问题时通常表现不佳。为了解决JSSP问题，本文引入了将DE与禁忌搜索（TS）相结合的思想。在TS中包含一个竞争性邻域，目的是确定DE是否能够取代构成i-TSAB主要优势的重新启动特征（即长期记忆和路径链接过程）。超过100个JSSP实例的计算实验报告表明，所提出的混合DE - TS算法相对于其他最先进的技术是有竞争力的，尽管，如果适当强调DE和TS中解决方案表示模式之间的充分性，仍然有改进的空间。
The Job-Shop Scheduling Problem (JSSP) has drawn considerable interest during the last decades, mainly because of its combinatorial characteristics, which make it very difficult to solve. The good performances attained by local search procedures, and especially Nowicki and Smutnicki's i-TSAB algorithm, encouraged researchers to combine such local search engines with global methods. Differential Evolution (DE) is an Evolutionary Algorithm that has been found to be particularly efficient for continuous optimization, but which does not usually perform well when applied to permutation problems. We introduce in this paper the idea of hybridizing DE with Tabu Search (TS) in order to solve the JSSP. A competitive neighborhood is included within the TS with the aim of determining if DE is able to replace the re-start features that constitute the main strengths of i-TSAB (i.e., a long-term memory and a path-relinking procedure). The computational experiments reported for more than 100 JSSP instances show that the proposed hybrid DE–TS algorithm is competitive with respect to other state-of-the-art techniques, although, there is still room for improvement if the adequacy between the solution representation modes within DE and TS is properly stressed.