SINGLE-MACHINE SCHEDULING WITH PROPORTIONALLY DETERIORATING JOBS SUBJECT TO AVAILABILITY CONSTRAINTS
Shisheng Li () and
Baoqiang Fan
Additional contact information
Shisheng Li: Department of Mathematics, Zhengzhou University, Zhengzhou 450001, PR China
Baoqiang Fan: Department of Mathematics and Information, Ludong University, Yantai 264025, PR China
Asia-Pacific Journal of Operational Research (APJOR), 2012, vol. 29, issue 04, 1-10
Abstract:
We address the nonresumable version of the scheduling problem with proportionally deteriorating jobs on a single machine subject to availability constraints. The objective is to minimize the total weighted completion time. We show that there exists no polynomial-time algorithm with a constant worst-case ratio for the problem with two nonavailability intervals unless $\mathcal{P} = \mathcal{NP}$. Furthermore, we propose a pseudo-polynomial-time algorithm and a fully polynomial-time approximation scheme for the problem with a single nonavailability interval.
Keywords: Scheduling; deteriorating jobs; availability constraint; FPTAS (search for similar items in EconPapers)
Date: 2012
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)
Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595912500194
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:wsi:apjorx:v:29:y:2012:i:04:n:s0217595912500194
Ordering information: This journal article can be ordered from
DOI: 10.1142/S0217595912500194
Access Statistics for this article
Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao
More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().