Zurück zu den Preprints des Jahres 2004


2004-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..


Series: 2004-14, Preprints

MSC:
90B35 Scheduling theory, deterministic

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

This paper was published in:
Computers & Industrial Engineering, Vol. 49, 2005, 611 - 624.