A hybrid Differential Evolution—Tabu Search algorithm for the solution of Job-Shop Scheduling Problems

[Display omitted] ► An algorithm combining Differential Evolution and Tabu Search is proposed. ► It is applied to the classical Job-Shop Scheduling Problem (makespan minimization). ► Computational experiments were performed over more than 100 classical instances. ► The hybrid algorithm provides very...

Full description

Saved in:
Bibliographic Details
Published in:Applied soft computing 2013-01, Vol.13 (1), p.462-474
Main Authors: Ponsich, Antonin, Coello Coello, Carlos A.
Format: Article
Language:English
Subjects:
Differential Evolution
Job-Shop Scheduling
Tabu Search
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:[Display omitted] ► An algorithm combining Differential Evolution and Tabu Search is proposed. ► It is applied to the classical Job-Shop Scheduling Problem (makespan minimization). ► Computational experiments were performed over more than 100 classical instances. ► The hybrid algorithm provides very good results for low size and medium instances. ► For complex instances, the algorithm finds acceptable solutions. 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.
ISSN:1568-4946
1872-9681
DOI:10.1016/j.asoc.2012.07.034