Zurück zu den Preprints des Jahres 2002


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

90B35 Scheduling theory, deterministic

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.

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

This paper was published in:
European Journal of Operati