A 3-approximation list scheduling algorithm for a single-machine scheduling problem with a non-renewable resource and total weighted completion time criterion

zbMATH Open1506.90100arXiv2105.04735MaRDI QIDQ5876237FDOQ5876237

Authors: Susumu Hashimoto, Shinji Mizuno 

Publication date: 31 January 2023

Abstract: This paper studies a single-machine scheduling problem with a non-renewable resource (NR-SSP) and total weighted completion time criterion. The non-renewable resource is consumed when the machine starts processing a job. We consider the case where each job's weight in the objective function is proportional to its resource consumption amount. The problem is known to be NP-hard in this case. We propose a 3-approximation list scheduling algorithm for this problem. Besides, we show that the approximation ratio 3 is tight for the algorithm.

Full work available at URL: https://arxiv.org/abs/2105.04735

Recommendations

• A tight approximation ratio of a list scheduling algorithm for a single-machine scheduling problem with a non-renewable resource
• Minimizing total weighted completion time on a single machine subject to non-renewable resource constraints
• Scheduling with non-renewable resources: minimizing the sum of completion times
• New complexity and approximability results for minimizing the total weighted completion time on a single machine subject to non-renewable resource constraints
• Approximation schemes for single machine scheduling with non-renewable resource constraints

zbMATH Keywords

approximation algorithmschedulingnon-renewable resourcelist scheduling algorithm

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Cited In (5)

• Scheduling with non-renewable resources: minimizing the sum of completion times
• New complexity and approximability results for minimizing the total weighted completion time on a single machine subject to non-renewable resource constraints
• Minimizing total weighted completion time on a single machine subject to non-renewable resource constraints
• Scheduling with non-renewable resources: minimizing the sum of completion times
• A tight approximation ratio of a list scheduling algorithm for a single-machine scheduling problem with a non-renewable resource

This page was built for publication: A 3-approximation list scheduling algorithm for a single-machine scheduling problem with a non-renewable resource and total weighted completion time criterion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5876237)