EconPapers    
Economics at your fingertips  
 

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).

 
Page updated 2025-01-08
Handle: RePEc:eee:proeco:v:198:y:2018:i:c:p:191-200