EPTAS for load balancing problem on parallel machines with a non-renewable resource

DOI10.1016/j.disopt.2023.100775zbMath1517.90050arXiv2108.04071OpenAlexW4372328721MaRDI QIDQ6108926

G. Jaykrishnan, Asaf Levin

Publication date: 30 June 2023

Published in: Discrete Optimization (Search for Journal in Brave)

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

zbMATH Keywords

schedulingapproximation schemesnon-renewable resource

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Approximability of scheduling problems with resource consuming jobs
• On the efficiency of polynomial time approximation schemes
• Minimising total tardiness for a single machine scheduling problem with family setups and resource constraints
• Approximation schemes for single machine scheduling with non-renewable resource constraints
• An efficient polynomial time approximation scheme for load balancing on uniformly related machines
• Reductions between scheduling problems with non-renewable resources and knapsack problems
• Approximation algorithms for scheduling unrelated parallel machines
• Preemptive scheduling of independent jobs on parallel machines subject to financial constraints
• Scheduling subject to nonrenewable-resource constraints
• Approximation schemes for scheduling on parallel machines
• Approximation schemes for parallel machine scheduling with non-renewable resources
• A PTAS for a resource scheduling problem with arbitrary number of parallel machines
• Approximability of total weighted completion time with resource consuming jobs
• Approximation schemes for scheduling on uniformly related and identical parallel machines
• 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 unified framework for designing EPTAS for load balancing on parallel machines
• Parametrized complexity theory.
• Integer Programming with a Fixed Number of Variables
• Basic scheduling problems with raw material constraints
• Closing the Gap for Makespan Scheduling via Sparsification Techniques
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables

This page was built for publication: EPTAS for load balancing problem on parallel machines with a non-renewable resource