No-wait flowshops with bicriteria of makespan and maximum lateness

We address the m-machine no-wait flowshop scheduling problem with a weighted sum of makespan and maximum lateness criteria, known as bicriteria. The problem reduces to the single criterion of makespan or maximum lateness when a weight of zero is assigned to makespan or maximum lateness. There are many heuristics for the single criterion of makespan. However, no heuristic has been reported in the literature on the single criterion of maximum lateness or the bicriteria problem. We propose a hybrid simulated annealing and a hybrid genetic heuristics, which can be used for the single criterion of makespan or maximum lateness, or the bicriteria problem. We also propose a dominance relation (DR) and a branch-and-bound algorithm. Extensive computational experiments show that the proposed heuristics perform much better than the best existing heuristics for makespan, and perform very well for the single criterion of maximum lateness and the bicriteria problem. The experiments also show that the DR and the branch-and-bound algorithm are quite efficient. (C) 2002 Elsevier B.V. All rights reserved.