04-14
A Comparison of Solution Procedures for Two-Machine Flow Shop Scheduling with Late Work Criterion
by Blazewicz, J.; Pesch, E.; Sterna, M.; Werner, F.
Preprint series: 04-14, Preprints
The paper is published: Computers & Industrial Engineering, Vol. 49, 2005, 611 - 624.
Abstract: In this paper, we analyze different solution procedures for the two-machine flow shop scheduling problem with a common due date and the weighted late work criterion, i.e. for problem F2|d_j = d|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 the consideration a priori.
Keywords: Flow shop, Late work, Dynamic programming, Enumerative method, List scheduling
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.