A tight approximation ratio of a list scheduling algorithm for a single-machine scheduling problem with a non-renewable resource

Susumu Hashimoto () and Shinji Mizuno ()
Additional contact information
Susumu Hashimoto: Tokyo Institute of Technology
Shinji Mizuno: Tokyo Institute of Technology

Journal of Scheduling, 2021, vol. 24, issue 3, No 1, 259-267

Abstract: Abstract In this paper, we investigate an open problem by Györgyi and Kis for a single-machine scheduling problem with a non-renewable resource (NR-SSP) and total weighted completion time criterion. The problem is NP-hard, even if every job has the same processing time, and each weight is equal to its required amount of the resource. Györgyi and Kis prove that a simple list scheduling algorithm for this special case is a 3-approximation algorithm and conjecture that the algorithm for the case is a 2-approximation algorithm. We prove their conjecture. More strongly, we show that the approximation ratio is strictly less than 2 for any instance, and for any $$ \epsilon > 0 $$ ϵ > 0 , there exists an instance for which the approximation ratio is more than $$ 2-\epsilon $$ 2 - ϵ .

Keywords: Single-machine scheduling problems; Non-renewable resources; List scheduling algorithm; Approximation algorithms (search for similar items in EconPapers)
Date: 2021
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-021-00681-y 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:24:y:2021:i:3:d:10.1007_s10951-021-00681-y

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

DOI: 10.1007/s10951-021-00681-y

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