NP-hard cases in scheduling deteriorating jobs on dedicated machines

A Kononov and S Gawiejnowicz ()
Additional contact information
A Kononov: Sobolev Institute of Mathematics
S Gawiejnowicz: Adam Mickiewicz University

Journal of the Operational Research Society, 2001, vol. 52, issue 6, 708-717

Abstract: Abstract In this paper problems of time-dependent scheduling on dedicated machines are considered. The processing time of each job is described by a function which is dependent on the starting time of the job. The objective is to minimise the maximum completion time (makespan). We prove that under linear deterioration the two-machine flow shop problem is strongly NP-hard and the two-machine open shop problem is ordinarily NP-hard. We show that for the three-machine flow shop and simple linear deterioration there does not exist a polynomial-time approximation algorithm with the worst case ratio bounded by a constant, unless P=NP. We also prove that the three-machine open shop problem with simple linear deterioration is ordinarily NP-hard, even if the jobs have got equal deterioration rates on the third machine.

Keywords: deteriorating jobs; flow shop; open shop; makespan; NP-hardness (search for similar items in EconPapers)
Date: 2001
References: Add references at CitEc
Citations: View citations in EconPapers (16)

Downloads: (external link)
http://link.springer.com/10.1057/palgrave.jors.2601117 Abstract (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:pal:jorsoc:v:52:y:2001:i:6:d:10.1057_palgrave.jors.2601117

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

DOI: 10.1057/palgrave.jors.2601117

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().