Approximability of scheduling problems with resource consuming jobs

DOI10.1007/s10479-015-1993-3zbMath1332.90111OpenAlexW2105376160MaRDI QIDQ256641

Tamás Kis, Péter Györgyi

Publication date: 9 March 2016

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: http://real.mtak.hu/26075/13/anor_ptas%20rev1.pdf

zbMATH Keywords

approximation schemessingle machine schedulingnon-renewable resourcesvertex cover problem

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (10)

Bi-objective optimization algorithms for joint production and maintenance scheduling under a global resource constraint: application to the permutation flow shop problem ⋮ Minimizing makespan on a single machine with release dates and inventory constraints ⋮ A multivariate complexity analysis of the material consumption scheduling problem ⋮ Approximation schemes for parallel machine scheduling with non-renewable resources ⋮ A PTAS for a resource scheduling problem with arbitrary number of parallel machines ⋮ EPTAS for load balancing problem on parallel machines with a non-renewable resource ⋮ Minimizing total weighted completion time on a single machine subject to non-renewable resource constraints ⋮ A tight approximation ratio of a list scheduling algorithm for a single-machine scheduling problem with a non-renewable resource ⋮ EPTAS for load balancing problem on parallel machines with a non-renewable resource ⋮ An FPTAS of minimizing total weighted completion time on single machine with position constraint

Cites Work

• Unnamed Item
• Exact algorithms for inventory constrained scheduling on a single machine
• Approximation schemes for single machine scheduling with non-renewable resource constraints
• Reductions between scheduling problems with non-renewable resources and knapsack problems
• Single machine scheduling problems with financial resource constraints: some complexity results and properties
• Approximability results for the resource-constrained project scheduling problem with a single type of resources
• Preemptive scheduling of independent jobs on parallel machines subject to financial constraints
• Algorithms for propagating resource constraints in AI planning and scheduling: Existing approaches and new results
• Approximation algorithms for inventory constrained scheduling on a single machine
• Complexity of single machine scheduling subject to nonnegative inventory constraints
• Scheduling subject to nonrenewable-resource constraints
• Optimization, approximation, and complexity classes
• Some APX-completeness results for cubic graphs
• Project scheduling with inventory constraints
• Tight Approximation Algorithms for Maximum Separable Assignment Problems
• On the Approximability of Single-Machine Scheduling with Precedence Constraints
• Basic scheduling problems with raw material constraints
• Khachiyan’s algorithm for linear programming
• Scheduling under a Non-renewable Resource Constraint
• Optimal Sequencing of a Single Machine Subject to Precedence Constraints

This page was built for publication: Approximability of scheduling problems with resource consuming jobs