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

DOI10.1007/s10951-021-00681-yzbMath1479.90093OpenAlexW3145877213MaRDI QIDQ2059081

Susumu Hashimoto, Shinji Mizuno

Publication date: 13 December 2021

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10951-021-00681-y

zbMATH Keywords

approximation algorithmsnon-renewable resourceslist scheduling algorithmsingle-machine scheduling problems

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Related Items (1)

Worst-case analysis of LPT scheduling on a small number of non-identical processors

Cites Work

• Approximability of scheduling problems with resource consuming jobs
• Exact algorithms for inventory constrained scheduling on a single machine
• Single machine scheduling problems with financial resource constraints: some complexity results and properties
• Preemptive scheduling of independent jobs on parallel machines subject to financial constraints
• Approximation algorithms for inventory constrained scheduling on a single machine
• Scheduling subject to nonrenewable-resource constraints
• Approximability of total weighted completion time with resource consuming jobs
• Scheduling with non-renewable resources: minimizing the sum of completion times
• Minimizing total weighted completion time on a single machine subject to non-renewable resource constraints
• Basic scheduling problems with raw material constraints
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey

This page was built for publication: A tight approximation ratio of a list scheduling algorithm for a single-machine scheduling problem with a non-renewable resource