by Blazewicz, J., Pesch, E., Sterna, M., Werner, F..
Series: 2002-03, Preprints
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