Solving the resource constrained deadline scheduling problem via reduction to the network flow problem
Publication:1147628
DOI10.1016/0377-2217(81)90331-3zbMath0449.90053OpenAlexW2114366376MaRDI QIDQ1147628
Publication date: 1981
Published in: European Journal of Operational Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0377-2217(81)90331-3
computational complexityreductionNP-complete problemsnetwork flow problembinary networkmaximal flowresource constrained deadline scheduling problem
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Deterministic network models in operations research (90B10)
Related Items (5)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Simple algorithms for multiprocessor scheduling to meet deadlines
- Deadline scheduling of tasks with ready times and resource constraints
- New Methods in Mathematical Programming—Optimal Flow Through Networks with Gains
- Minimizing maximum lateness on one machine: computational experience and some applications
- Scheduling Tasks with Nonuniform Deadlines on Two Processors
- Complexity Results for Multiprocessor Scheduling under Resource Constraints
- Two-Processor Scheduling with Start-Times and Deadlines
- Maximal Flow with Gains through a Special Network
- Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment
This page was built for publication: Solving the resource constrained deadline scheduling problem via reduction to the network flow problem