New complexity and approximability results for minimizing the total weighted completion time on a single machine subject to non-renewable resource constraints

DOI10.1016/j.dam.2022.01.009zbMath1483.90056arXiv2004.00972OpenAlexW3015066369MaRDI QIDQ2078845

Péter Györgyi, Tamás Kis

Publication date: 4 March 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

high-multiplicity schedulingsingle machine schedulingapproximation algorithmsnon-renewable resourcesFPTAS

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Related Items (1)

A multivariate complexity analysis of the material consumption scheduling problem

Cites Work

• Unnamed Item
• Minimising total tardiness for a single machine scheduling problem with family setups and resource constraints
• 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 schemes for parallel machine scheduling with non-renewable resources
• 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
• A Dynamic Programming Approach for Sequencing Groups of Identical Jobs
• Strongly Polynomial Algorithms for the High Multiplicity Scheduling Problem
• Scheduling under a Non-renewable Resource Constraint
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Scheduling start time dependent jobs to minimize the total weighted completion time

This page was built for publication: New complexity and approximability results for minimizing the total weighted completion time on a single machine subject to non-renewable resource constraints