Journal
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volume 165, Issue 2, Pages 408-415Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.ejor.2004.04.011
Keywords
scheduling; flow-shop; late work criteria; NP-hardness; dynamic programming
Ask authors/readers for more resources
The paper is on the two-machine non-preemptive flow-shop scheduling problem with a total weighted late work criterion and a common due date (F2 vertical bar d(i) = d vertical bar Y-w). The late work performance measure estimates the quality of the obtained solution with regard to the duration of late parts of tasks not taking into account the quantity of this delay. We prove the binary NP-hardness of the problem mentioned by showing a transformation from the partition problem to its decision counterpart. Then, a dynamic programming approach of pseudo-polynomial time complexity is formulated. (c) 2004 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available