Accelerated tabu search for no-wait flowshop scheduling problem with maximum lateness criterion

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.