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.

MSC:
90B35 Scheduling theory, See also {68M20}

 

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.

Letzte Änderung: 01.03.2018 - Ansprechpartner: Webmaster