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.

90B35 Scheduling theory, See also {68M20}


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.

Letzte Änderung: 01.03.2018 - Ansprechpartner: Webmaster