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

approximation algorithmsjob-shop schedulingprecedence-constrained schedulingrandomized algorithms

Mathematics Subject Classification ID

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

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

• 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
• 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?)
• 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

(12)

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

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)