An optimal rounding gives a better approximation for scheduling unrelated machines

DOI10.1016/j.orl.2004.05.004zbMath1099.90024OpenAlexW2052586468MaRDI QIDQ2488212

Publication date: 25 August 2005

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2004.05.004

zbMATH Keywords

Scheduling Approximation algorithm Unrelated machines Rounding

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)

Related Items

A faster combinatorial approximation algorithm for scheduling unrelated parallel machines ⋮ Scheduling with complete multipartite incompatibility graph on parallel machines: complexity and algorithms ⋮ Parallel machine scheduling with nested processing set restrictions ⋮ On the extension complexity of scheduling polytopes ⋮ Makespan minimization on unrelated parallel machines with a few bags ⋮ Unrelated parallel machine scheduling with new criteria: complexity and models ⋮ Resource-constrained machine scheduling with machine eligibility restriction and its applications to surgical operations scheduling ⋮ Fast approximation algorithms for job scheduling with processing set restrictions ⋮ Approximation algorithms for the graph balancing problem with two speeds and two job lengths ⋮ Approximation algorithms for scheduling jobs with release times and arbitrary sizes on batch machines with non-identical capacities ⋮ On the complexity of scheduling unrelated parallel machines with limited preemptions ⋮ On the complexity of constructing multiprocessor little-preemptive schedules ⋮ Scheduling jobs with equal processing times subject to machine eligibility constraints ⋮ Scheduling for electricity cost in a smart grid ⋮ Graph balancing: a special case of scheduling unrelated parallel machines ⋮ Restricted assignment scheduling with resource constraints ⋮ Matching with sizes (or scheduling with processing set restrictions) ⋮ Matching with sizes (or scheduling with processing set restrictions) ⋮ Scheduling unit length jobs on parallel machines with lookahead information ⋮ Makespan minimization in online scheduling with machine eligibility ⋮ On the configuration-LP for scheduling on unrelated machines ⋮ A 3/2-approximation algorithm for the graph balancing problem with two weights ⋮ On the geometry, preemptions and complexity of multiprocessor and shop scheduling ⋮ Approximation Algorithms for Unrelated Machine Scheduling with an Energy Budget ⋮ A Family of Scheduling Algorithms for Hybrid Parallel Platforms ⋮ Unrelated parallel machine scheduling -- perspectives and progress ⋮ Estimating the makespan of the two-valued restricted assignment problem ⋮ Approximation algorithms for scheduling on multi-core processor with shared speedup resources ⋮ Parallel batch scheduling with inclusive processing set restrictions and non-identical capacities to minimize makespan ⋮ Fast approximation algorithms for uniform machine scheduling with processing set restrictions ⋮ Parallel machine scheduling with speed-up resources ⋮ Makespan minimization in online scheduling with machine eligibility ⋮ A hierarchical solution approach for a multicommodity distribution problem under a special cost structure ⋮ Online scheduling of two job types on a set of multipurpose machines with unit processing times ⋮ Online scheduling with equal processing times and machine eligibility constraints ⋮ Unnamed Item ⋮ An optimal online algorithm for scheduling on two parallel machines with GoS eligibility constraints ⋮ Multipurpose machine scheduling with rejection and identical job processing times ⋮ A note on ``An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs ⋮ A note on graph balancing problems with restrictions ⋮ An improved lower bound for rank four scheduling ⋮ Iterated greedy local search methods for unrelated parallel machine scheduling ⋮ Scheduling jobs with release and delivery times subject to nested eligibility constraints ⋮ Computing Nash equilibria for scheduling on restricted parallel links ⋮ A PTAS for Scheduling Unrelated Machines of Few Different Types ⋮ Makespan minimization on unrelated parallel machines with simple job-intersection structure and bounded job assignments ⋮ New bounds for truthful scheduling on two unrelated selfish machines ⋮ Approximate algorithms for unrelated machine scheduling to minimize makespan ⋮ PREEMPTIVE SCHEDULING ALGORITHMS WITH NESTED PROCESSING SET RESTRICTION ⋮ On minimizing the makespan when some jobs cannot be assigned on the same machine ⋮ Scheduling parallel machines with inclusive processing set restrictions and job release times ⋮ Preemptive and non-preemptive scheduling on two unrelated parallel machines ⋮ THE PRICE OF MULTI-ORGANIZATION CONSTRAINT IN UNRELATED PARALLEL MACHINE SCHEDULING

Cites Work