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

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

Full description

Saved in:
Bibliographic Details
Published in:Journal of scheduling 2021-06, Vol.24 (3), p.259-267
Main Authors: Hashimoto, Susumu, Mizuno, Shinji
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Artificial Intelligence
Business and Management
Calculus of Variations and Optimal Control
Optimization
Completion time
Mathematical analysis
Nonrenewable resources
Operations Research/Decision Theory
Optimization
Ratios
Renewable resources
Scheduling
Supply Chain Management
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 ϵ > 0 , there exists an instance for which the approximation ratio is more than 2 - ϵ .
ISSN:1094-6136
1099-1425
DOI:10.1007/s10951-021-00681-y