A faster combinatorial approximation algorithm for scheduling unrelated parallel machines

DOI10.1016/J.TCS.2007.02.056MaRDI QIDQ2373738zbMATH OpenOpenAlexFDO

Authors Martin Gairing, Burkhard Monien, Andreas Woclaw

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

zbMATH Keywords

approximation algorithmsschedulingunrelated parallel machinesunsplittable network flow

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25) Deterministic scheduling theory in operations research (90B35)

Recommendations

• Automata, Languages and Programming
• Approximation algorithms for scheduling unrelated parallel machines
• Improved approximation schemes for scheduling unrelated parallel machines
• Approximating scheduling unrelated parallel machines in parallel
• Improved Approximation Schemes for Scheduling Unrelated Parallel Machines
• Experimental comparison of approximation algorithms for scheduling unrelated parallel machines
• A unified approach to scheduling on unrelated parallel machines
• 2-approximation algorithm for a generalization of scheduling on unrelated parallel machines
• Approximation for scheduling on uniform nonsimultaneous parallel machines

Cites work

• A cutting plane algorithm for the unrelated parallel machine scheduling problem
• An approximation algorithm for the generalized assignment problem
• An optimal rounding gives a better approximation for scheduling unrelated machines
• Approximation algorithms for NP-hard problems.
• Approximation algorithms for scheduling unrelated parallel machines
• Approximation algorithms for single-source unsplittable flow
• Bounds for Certain Multiprocessing Anomalies
• Combinatorial Algorithms for the Generalized Circulation Problem
• Computing Nash equilibria for scheduling on restricted parallel links
• Dioïds and semirings: Links to fuzzy sets and other applications
• Duality-Based Algorithms for Scheduling Unrelated Parallel Machines
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Fast and simple approximation schemes for generalized flow.
• Fast Approximation Algorithms for Fractional Packing and Covering Problems
• Faster algorithms for the generalized network flow problem
• scientific article; zbMATH DE number 1187161 (Why is no real title available?)
• scientific article; zbMATH DE number 3177183 (Why is no real title available?)
• Improved Approximation Schemes for Scheduling Unrelated Parallel Machines
• Improving time bounds on maximum generalised flow computations by contracting the network
• Network flows. Theory, algorithms, and applications.
• New Methods in Mathematical Programming—Optimal Flow Through Networks with Gains
• On Max Flows with Gains and Pure Min-Cost Flows
• On the single-source unsplittable flow problem
• Optimum flows in general communication networks
• Polynomial-Time Highest-Gain Augmenting Path Algorithms for the Generalized Circulation Problem
• Scheduling tasks on unrelated machines: large neighborhood improvement procedures

Cited in

(26)

• A hybrid multi-objective evolutionary algorithm approach for handling sequence- and machine-dependent set-up times in unrelated parallel machine scheduling problem
• A 3/2-approximation algorithm for the graph balancing problem with two weights
• Fast approximation algorithms for uniform machine scheduling with processing set restrictions
• 2-approximation algorithm for a generalization of scheduling on unrelated parallel machines
• The \(C^{\max}\) problem of scheduling multiple groups of jobs on multiple processors at different speeds
• Makespan minimization on unrelated parallel machines with a few bags
• Approximation algorithms for the graph balancing problem with two speeds and two job lengths
• Graph balancing: a special case of scheduling unrelated parallel machines
• Task swapping networks in distributed systems
• On the Configuration-LP for Scheduling on Unrelated Machines
• An absolute approximation algorithm for scheduling unrelated machines
• A unified approach to scheduling on unrelated parallel machines
• On the configuration-LP for scheduling on unrelated machines
• Unrelated parallel machine scheduling -- perspectives and progress
• Scheduling Unrelated Parallel Machines Computational Results
• Approximating Scheduling Machines with Capacity Constraints
• Automata, Languages and Programming
• A PTAS for scheduling unrelated machines of few different types
• Computing Nash equilibria for scheduling on restricted parallel links
• Makespan minimization on unrelated parallel machines with simple job-intersection structure and bounded job assignments
• Heuristics for minimizing regular performance measures in unrelated parallel machine scheduling problems
• A Bi-Criteria FPTAS for Scheduling with Memory Constraints on Graphs with Bounded Tree-Width
• Online unrelated-machine load balancing and generalized flow with recourse
• Fast exact and approximate algorithms for k-partition and scheduling independent tasks
• Scheduling with locality by routing
• Iterated greedy local search methods for unrelated parallel machine scheduling

This page was built for publication: A faster combinatorial approximation algorithm for scheduling unrelated parallel machines

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