Solving the resource constrained deadline scheduling problem via reduction to the network flow problem

DOI10.1016/0377-2217(81)90331-3zbMath0449.90053OpenAlexW2114366376MaRDI QIDQ1147628

Jacek Błażewicz

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

zbMATH Keywords

computational complexityreductionNP-complete problemsnetwork flow problembinary networkmaximal flowresource constrained deadline scheduling problem

Mathematics Subject Classification ID

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)

Two level heuristic for the resource constrained scheduling problem ⋮ An interactive decision support system for the resource constrained scheduling problem ⋮ Cellular control of manufacturing systems ⋮ Simulated annealing for resource-constrained scheduling ⋮ Parallel machine scheduling with additional resources: notation, classification, models and solution methods

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Solving the resource constrained deadline scheduling problem via reduction to the network flow problem