Zurück zu den Preprints des Jahres 2002


2002-03

The Two-Machine Flow-Shop Problem with Weighted Late Work Criterion and Common Due Date

by Blazewicz, J., Pesch, E., Sterna, M., Werner, F..


Series: 2002-03, Preprints

MSC:
90B35 Scheduling theory, deterministic

Abstract:
The paper is on the two-machine flow-shop scheduling problem with a
weighted late work criterion and a common due date. We prove its
binary NP-hardness by showing a transformation from the partition
problem to the decision counterpart of this scheduling
problem. Then a dynamic programming approach of pseudo-polynomial
time complexity will be formulated.

Keywords:
Scheduling, flow-shop, late work criteria, NP-hardness, dynamic programming

This paper was published in:
European Journal of Operati