Single machine scheduling with controllable processing times and an unavailability period to minimize the makespan
Dvir Shabtay and
Moshe Zofi
International Journal of Production Economics, 2018, vol. 198, issue C, 191-200
Abstract:
We study a single machine scheduling problem, where job processing times are controllable, and there is a fixed machine unavailability interval. We assume that the job processing time is a convex decreasing function of the amount of resource allocated to its processing operation. We further assume that there is a budget restriction on the total resource allocation cost. Our aim is to find a job schedule that minimizes the makespan. We prove that the problem is NP-hard and develop both a constant factor approximation algorithm and a fully polynomial time approximation scheme (FPTAS) for solving it. The FPTAS is obtained despite the fact that we could not design a pseudo-polynomial time algorithm for finding the optimal solution.
Keywords: Single machine scheduling; Machine unavailability period; Controllable processing time; Resource allocation; Approximation algorithm; Makespan (search for similar items in EconPapers)
Date: 2018
References: Add references at CitEc
Citations: View citations in EconPapers (7)
Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0925527317304310
Full text for ScienceDirect subscribers only
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:eee:proeco:v:198:y:2018:i:c:p:191-200
DOI: 10.1016/j.ijpe.2017.12.025
Access Statistics for this article
International Journal of Production Economics is currently edited by Stefan Minner
More articles in International Journal of Production Economics from Elsevier
Bibliographic data for series maintained by Catherine Liu (repec@elsevier.com).