Improved Approximation Schemes for Scheduling Unrelated Parallel Machines

DOI10.1287/moor.26.2.324.10559zbMath1082.90525OpenAlexW2142033149MaRDI QIDQ5704042

Lorant Porkolab, Klaus Jansen

Publication date: 11 November 2005

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

Full work available at URL: https://doi.org/10.1287/moor.26.2.324.10559

zbMATH Keywords

Scheduling, parallel machines, makespan, fully polynomial approximation scheme

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (20)

Rectangle packing with one-dimensional resource augmentation ⋮ Scheduling algorithms for procrastinators ⋮ A faster combinatorial approximation algorithm for scheduling unrelated parallel machines ⋮ On the optimality of exact and approximation algorithms for scheduling problems ⋮ Scheduling on unrelated machines under tree-like precedence constraints ⋮ Exact makespan minimization of unrelated parallel machines ⋮ Algorithms for single machine scheduling problem with release dates and submodular penalties ⋮ Graph balancing: a special case of scheduling unrelated parallel machines ⋮ Approximation algorithms for general packing problems and their application to the multicast congestion problem ⋮ Improved bi-criteria approximation schemes for load balancing on unrelated machines with cost constraints ⋮ Grouping techniques for scheduling problems: simpler and faster ⋮ Heuristic for a new multiobjective scheduling problem ⋮ TWO APPROXIMATION SCHEMES FOR SCHEDULING ON PARALLEL MACHINES UNDER A GRADE OF SERVICE PROVISION ⋮ Parallel machine scheduling with speed-up resources ⋮ Partitioned EDF scheduling on a few types of unrelated multiprocessors ⋮ Unnamed Item ⋮ Multipurpose machine scheduling with rejection and identical job processing times ⋮ A PTAS for Scheduling Unrelated Machines of Few Different Types ⋮ Geometric quadrisection in linear time, with application to VLSI placement ⋮ Scheduling parallel machines with inclusive processing set restrictions and job release times

This page was built for publication: Improved Approximation Schemes for Scheduling Unrelated Parallel Machines