Scheduling on unrelated machines under tree-like precedence constraints
From MaRDI portal
Publication:2391177
DOI10.1007/s00453-007-9004-yzbMath1180.90112MaRDI 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
approximation algorithms; randomized algorithms; job-shop scheduling; precedence-constrained scheduling
90B35: Deterministic scheduling theory in operations research
68W25: Approximation algorithms
68W20: Randomized algorithms
Related Items
An improved approximation algorithm for scheduling under arborescence precedence constraints, Mixed integer programming model for scheduling in unrelated parallel processor system with priority consideration, Parallel dedicated machines scheduling with chain 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
