Journal
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volume 206, Issue 1, Pages 64-72Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.ejor.2010.02.014
Keywords
Scheduling; No-wait flowshop; Maximum lateness; Tabu search; Neighborhood
Funding
- National Science Foundation of China [60672092, 60504029, 60873236]
- National High-Tech Research and Development Plan of China [2008AA04Z103]
Ask authors/readers for more resources
For the no-wait flowshop scheduling problem with maximum lateness criterion, properties are developed to speed up three kinds of basic operations generating candidate solutions, i.e., the insertion of a new job into a partial sequence, and the insertion and exchange neighborhood moves. The properties reduce the time to evaluate a candidate from O(nm) to O(1) and simplify the implementation of the heuristics based on the basic operations by evaluating candidates before their generation. The properties also reduce from O(n(3)m) to O(n(2)) the time complexity of well-known NEH heuristic and the complete evaluation of the insertion and exchange neighborhoods. Tabu search (TS) is applied to the considered problem, since TS tries to find the best neighbor of the current solution in each iteration and therefore can much benefit from the speedups. Three different ways to use insertion and exchange neighborhoods are compared in TS. Computational experiments show that the speedups are more helpful as job number increases and all proposed TS algorithms are more effective and robust than the existing algorithms. Although two- and single-neighborhood IS algorithms are not significantly different, two-neighborhood TS algorithms are more preferable. (C) 2010 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available