02-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.
Preprint series: 02-03, Preprints
The paper is published: European Journal of Operational Research, Vol. 165, No. 2, 2005, 408 - 415.
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
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.