Single-machine scheduling with resource-dependent processing times and multiple unavailability periods

Byung-Cheon Choi () and Myoung-Ju Park ()
Additional contact information
Byung-Cheon Choi: Chungnam National University
Myoung-Ju Park: Kyung Hee University

Journal of Scheduling, 2022, vol. 25, issue 2, No 4, 202 pages

Abstract: Abstract We consider a single-machine scheduling problem with multiple unavailability periods such that the processing time of each job is inversely proportional to the kth power of its own resource consumption amount. The objective is to minimize the sum of the makespan and the total resource consumption cost. For every $$k>0$$ k > 0 , we show that the problem with one unavailability period is NP-hard while it admits a fully polynomial-time approximation scheme. Furthermore, we analyze the (in)approximability for the case with multiple unavailability periods. For every $$k>0$$ k > 0 , we show that the problem with an arbitrary number of unavailability periods is strongly NP-hard. Finally, we extend the results to the problem of minimizing the makespan with a constraint on the total resource consumption cost.

Keywords: Scheduling; Convex resource consumption functions; Machine unavailability period; Computational complexity; Inapproximability (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-022-00723-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jsched:v:25:y:2022:i:2:d:10.1007_s10951-022-00723-z

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-022-00723-z

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().