A comparison of solution procedures for two-machine flow shop scheduling with late work criterion

In this paper we analyze different solution procedures for the two-machine flow shop scheduling problem with a common due date and weighted late work criterion, i.e. for problem F2 vertical bar d(j) = d vertical bar Y-w, which is known to be binary NP-hard. In computational experiments we compare the practical efficiency of a dynamic programming approach, an enumerative method and a heuristic list scheduling procedure. Test results show that each solution method has its advantages and none of them can be rejected from consideration a priori. (c) 2005 Elsevier Ltd. All rights reserved.