Scheduling on unrelated machines under tree-like precedence constraints

DOI10.1007/S00453-007-9004-YMaRDI QIDQ2391177zbMATH OpenOpenAlexFDO

Authors V. S. Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy, Aravind Srinivasan

Publication date 24 July 2009

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-007-9004-y

zbMATH Keywords

randomized algorithmsapproximation algorithmsjob-shop schedulingprecedence-constrained scheduling

Mathematics Subject Classification ID

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

Recommendations

• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• scientific article; zbMATH DE number 1187166
• Approximation algorithms for scheduling with resource and precedence constraints
• Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines that Run at Different Speeds
• The Power of Preemption on Unrelated Machines and Applications to Scheduling Orders

Cites work

• scientific article; zbMATH DE number 1559527 (Why is no real title available?)
• scientific article; zbMATH DE number 1775401 (Why is no real title available?)
• scientific article; zbMATH DE number 1775452 (Why is no real title available?)
• An efficient approximation algorithm for minimizing makespan on uniformly related machines.
• Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines that Run at Different Speeds
• Approximation algorithms for scheduling unrelated parallel machines
• Approximation algorithms for shop scheduling problems with minsum objective
• Better approximation guarantees for job-shop scheduling
• Convex quadratic and semidefinite programming relaxations in scheduling
• Fast algorithms for finding \(O\)(Congestion+Dilation) packet routing schedules
• Improved Approximation Algorithms for Shop Scheduling Problems
• Improved Approximation Schemes for Scheduling Unrelated Parallel Machines
• Makespan Minimization in Job Shops: A Linear Time Approximation Scheme
• Multi-processor scheduling to minimize flow time with \(\epsilon\) resource augmentation
• On dependent randomized rounding algorithms
• Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps
• Parallel Processing and Applied Mathematics
• Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• The power of \(\alpha\)-points in preemptive single machine scheduling.

Cited in

(10)

• Chains and trees: `Strong' -- `weak' order in job scheduling
• Parallel dedicated machines scheduling with chain precedence constraints
• Approximation schemes for scheduling jobs with chain precedence constraints
• An improved approximation algorithm for scheduling under arborescence precedence constraints
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Tree precedence in scheduling: The strong-weak distinction
• The power of preemption on unrelated machines and applications to scheduling orders
• Approximation algorithms for scheduling with resource and precedence constraints
• Unrelated parallel machine scheduling problem with precedence constraints: polyhedral analysis and branch-and-cut
• Mixed integer programming model for scheduling in unrelated parallel processor system with priority consideration

This page was built for publication: Scheduling on unrelated machines under tree-like precedence constraints

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