Approximation Schemes for Machine Scheduling with Resource (In-)dependent Processing Times

DOI10.1145/3302250zbMath1454.68185OpenAlexW2944073560WikidataQ127943111 ScholiaQ127943111MaRDI QIDQ4972675

Malin Rau, Marten Maack, Klaus Jansen

Publication date: 25 November 2019

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3302250

zbMATH Keywords

scheduling with resource-dependent processing timessingle resource-constrained scheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Related Items (3)

Inverse interval scheduling via reduction on a single machine ⋮ EPTAS for the dual of splittable bin packing with cardinality constraint ⋮ An improved algorithm for parallel machine scheduling under additional resource constraints

Cites Work

• A note on the Kenyon-Remila strip-packing algorithm
• Machine scheduling with resource dependent processing times
• Fast rectangular matrix multiplication and some applications
• An approximation algorithm for identical parallel machine scheduling with resource dependent processing times
• Scheduling jobs with time-resource tradeoff via nonlinear programming
• Bin packing can be solved within 1+epsilon in linear time
• Using fast matrix multiplication to find basic solutions
• Scheduling malleable parallel tasks: an asymptotic fully polynomial time approximation scheme
• Scheduling with an orthogonal resource constraint
• Hybrid rounding techniques for knapsack problems
• Approximate Max-Min Resource Sharing for Structured Concave Optimization
• A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem
• APPROXIMATION ALGORITHMS FOR MULTIPLE STRIP PACKING AND SCHEDULING PARALLEL JOBS IN PLATFORMS
• AFPTAS Results for Common Variants of Bin Packing: A New Method for Handling the Small Items
• Fast Approximation Algorithms for Knapsack Problems
• Bounds for Multiprocessor Scheduling with Resource Constraints
• Complexity Results for Multiprocessor Scheduling under Resource Constraints
• Approximation schemes for machine scheduling with resource (in-)dependent processing times

This page was built for publication: Approximation Schemes for Machine Scheduling with Resource (In-)dependent Processing Times