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|dj=d|Yw , 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.