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.009MaRDI QIDQ2078845zbMATH OpenOpenAlexFDO

Authors Péter Györgyi, Tamás Kis

Publication date 4 March 2022

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

approximation algorithmsFPTAShigh-multiplicity schedulingnon-renewable resourcessingle machine scheduling

Mathematics Subject Classification ID

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

Abstract: In this paper we consider single machine scheduling problems with additional non-renewable resource constraints. Examples for non-renewable resources include raw materials, energy, or money. Usually they have an initial stock and replenishments arrive over time at a-priori known time points and quantities. The jobs have some requirements from the resources and a job can only be started if the available quantity from each of the required resources exceeds the requirements of the job. Upon starting a job, it consumes its requirements which decreases the available quantities of the respective non-renewable resources. There is a broad theoretical and practical background for this class of problems. Most of the literature concentrate on the makespan, and the maximum lateness objectives. This paper focuses on the total weighted completion time objective for which the list of the approximation algorithms is very short. In this paper we extend that list by considering new special cases and obtain new complexity results and approximation algorithms. We show that even if there is only a single non-renewable resource, and each job has unit weight and requires only one unit from the resource, the problem is still NP-hard, however, in our construction we need a high-multiplicity encoding of the jobs in the input. We also propose an FPTAS for a variant in which the jobs have arbitrary weights, and the number of supply time points is bounded by a constant. Finally, we prove some non-trivial approximation guarantees for simple greedy algorithms for some further variants of the problem.

Recommendations

• 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 3-approximation list scheduling algorithm for a single-machine scheduling problem with a non-renewable resource and total weighted completion time criterion
• Approximability of total weighted completion time with resource consuming jobs
• Approximation schemes for single machine scheduling with non-renewable resource constraints

Cites work

• A Dynamic Programming Approach for Sequencing Groups of Identical Jobs
• Approximability of total weighted completion time with resource consuming jobs
• Approximation schemes for parallel machine scheduling with non-renewable resources
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Minimising total tardiness for a single machine scheduling problem with family setups and resource constraints
• Minimizing total weighted completion time on a single machine subject to non-renewable resource constraints
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Preemptive scheduling of independent jobs on parallel machines subject to financial constraints
• Scheduling start time dependent jobs to minimize the total weighted completion time
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Scheduling under a Non-renewable Resource Constraint
• Scheduling with non-renewable resources: minimizing the sum of completion times
• Single machine scheduling problems with financial resource constraints: some complexity results and properties
• Strongly Polynomial Algorithms for the High Multiplicity Scheduling Problem

Cited in

(15)

• Approximation schemes for parallel machine scheduling with non-renewable resources
• Approximability of total weighted completion time with resource consuming jobs
• A tight approximation ratio of a list scheduling algorithm for a single-machine scheduling problem with a non-renewable resource
• 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
• Approximability of scheduling problems with resource consuming jobs
• Efficiency of equilibria in restricted uniform machine scheduling with total weighted completion time as social cost
• Approximation schemes for single machine scheduling with non-renewable resource constraints
• Strongly Fully Polynomial Time Approximation Scheme for the weighted completion time minimization problem on two-parallel capacitated machines
• Weighted Completion Time Minimization for Unrelated Machines via Iterative Fair Contention Resolution
• Single machine scheduling problems with financial resource constraints: some complexity results and properties
• A 3-approximation list scheduling algorithm for a single-machine scheduling problem with a non-renewable resource and total weighted completion time criterion
• A multivariate complexity analysis of the material consumption scheduling problem
• Scheduling with non-renewable resources: minimizing the sum of completion times
• NP-hardness of the single-variable-resource scheduling problem 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

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