Scheduling on unrelated machines under tree-like precedence constraints

DOI10.1007/s00453-007-9004-yzbMath1180.90112OpenAlexW2173690244MaRDI QIDQ2391177

Madhav V. Marathe, Srinivasan Parthasarathy, V. S. Anil Kumar, 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 algorithmsrandomized algorithmsjob-shop schedulingprecedence-constrained scheduling

Mathematics Subject Classification ID

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

Related Items (4)

Parallel dedicated machines scheduling with chain 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 ⋮ Unrelated Parallel Machine Scheduling Problem with Precedence Constraints: Polyhedral Analysis and Branch-and-Cut

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for scheduling unrelated parallel machines
• On dependent randomized rounding algorithms
• Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps
• The power of \(\alpha\)-points in preemptive single machine scheduling.
• Approximation algorithms for shop scheduling problems with minsum objective
• Fast algorithms for finding \(O\)(Congestion+Dilation) packet routing schedules
• Better Approximation Guarantees for Job-Shop Scheduling
• An Efficient Approximation Algorithm for Minimizing Makespan on Uniformly Related Machines
• Convex quadratic and semidefinite programming relaxations in scheduling
• Multi-processor scheduling to minimize flow time with ε resource augmentation
• Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines that Run at Different Speeds
• Improved Approximation Algorithms for Shop Scheduling Problems
• 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
• Makespan Minimization in Job Shops: A Linear Time Approximation Scheme
• Parallel Processing and Applied Mathematics
• Improved Approximation Schemes for Scheduling Unrelated Parallel Machines

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