Scheduling on unrelated machines under tree-like precedence constraints
From MaRDI portal
Publication:2391177
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
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