A PTAS for scheduling unrelated machines of few different types

DOI10.1142/S0129054118410071MaRDI QIDQ5895057zbMATH OpenOpenAlexWikidataFDO

Authors Jan Clemens Gehrke, Stefan E. J. Kraft, Jakob Schikowski, Klaus Jansen

Publication date 24 July 2018

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054118410071

zbMATH Keywords

approximation algorithmPTASpolynomial time approximation schemescheduling on unrelated machinesscheduling on unrelated machines of few different typessingle exponential in approximation ratio

Mathematics Subject Classification ID

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

Recommendations

• A PTAS for scheduling unrelated machines of few different types
• scientific article; zbMATH DE number 1754639
• Improved approximation schemes for scheduling unrelated parallel machines

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• A faster combinatorial approximation algorithm for scheduling unrelated parallel machines
• An approximation algorithm for the generalized assignment problem
• An improved lower bound for rank four scheduling
• An optimal rounding gives a better approximation for scheduling unrelated machines
• Approximation algorithms for scheduling unrelated parallel machines
• Assigning real-time tasks on heterogeneous multiprocessors with two unrelated types of processors
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Grouping techniques for scheduling problems: simpler and faster
• Improved Approximation Schemes for Scheduling Unrelated Parallel Machines
• Minimum makespan scheduling with low rank processing times
• On \((1,\varepsilon)\)-restricted assignment makespan minimization
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Partitioned EDF scheduling on a few types of unrelated multiprocessors
• Polynomiality for bin packing with a constant number of item types
• Scheduling jobs on identical and uniform processors revisited
• Scheduling problems on two sets of identical machines
• Task assignment algorithms for two-type heterogeneous multiprocessors

Cited in

(5)

• Randomized approximation schemes for minimizing the weighted makespan on identical parallel machines
• Improved bi-criteria approximation schemes for load balancing on unrelated machines with cost constraints
• Makespan minimization on unrelated parallel machines with a few bags
• A PTAS for scheduling unrelated machines of few different types
• Bi-Criteria Approximation Algorithms for Load Balancing on Unrelated Machines with Costs

This page was built for publication: A PTAS for scheduling unrelated machines of few different types

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