A faster combinatorial approximation algorithm for scheduling unrelated parallel machines
From MaRDI portal
Publication:2373738
DOI10.1016/j.tcs.2007.02.056zbMath1118.68192OpenAlexW2000850616MaRDI QIDQ2373738
Martin Gairing, Andreas Woclaw, Burkhard Monien
Publication date: 16 July 2007
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2007.02.056
Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)
Related Items (15)
Approximating Scheduling Machines with Capacity Constraints ⋮ Makespan minimization on unrelated parallel machines with a few bags ⋮ Heuristics for minimizing regular performance measures in unrelated parallel machine scheduling problems ⋮ A hybrid multi-objective evolutionary algorithm approach for handling sequence- and machine-dependent set-up times in unrelated parallel machine scheduling problem ⋮ Approximation algorithms for the graph balancing problem with two speeds and two job lengths ⋮ The \(C^{\max}\) problem of scheduling multiple groups of jobs on multiple processors at different speeds ⋮ Graph balancing: a special case of scheduling unrelated parallel machines ⋮ On the configuration-LP for scheduling on unrelated machines ⋮ A 3/2-approximation algorithm for the graph balancing problem with two weights ⋮ Unrelated parallel machine scheduling -- perspectives and progress ⋮ Iterated greedy local search methods for unrelated parallel machine scheduling ⋮ 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 ⋮ Task swapping networks in distributed systems
Cites Work
- Approximation algorithms for scheduling unrelated parallel machines
- On the single-source unsplittable flow problem
- An approximation algorithm for the generalized assignment problem
- A cutting plane algorithm for the unrelated parallel machine scheduling problem
- Improving time bounds on maximum generalised flow computations by contracting the network
- Dioïds and semirings: Links to fuzzy sets and other applications
- An optimal rounding gives a better approximation for scheduling unrelated machines
- Optimum flows in general communication networks
- Faster Algorithms for the Generalized Network Flow Problem
- Approximation Algorithms for Single-Source Unsplittable Flow
- Combinatorial Algorithms for the Generalized Circulation Problem
- New Methods in Mathematical Programming—Optimal Flow Through Networks with Gains
- Exact and Approximate Algorithms for Scheduling Nonidentical Processors
- On Max Flows with Gains and Pure Min-Cost Flows
- Duality-Based Algorithms for Scheduling Unrelated Parallel Machines
- Polynomial-Time Highest-Gain Augmenting Path Algorithms for the Generalized Circulation Problem
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
- Bounds for Certain Multiprocessing Anomalies
- Improved Approximation Schemes for Scheduling Unrelated Parallel Machines
- Computing Nash equilibria for scheduling on restricted parallel links
- Fast and simple approximation schemes for generalized flow.
- Scheduling tasks on unrelated machines: large neighborhood improvement procedures
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: A faster combinatorial approximation algorithm for scheduling unrelated parallel machines
