Two deadline reduction algorithms for scheduling dependent tasks on parallel processors

DOI10.1007/978-3-030-78230-6_14OpenAlexW3168834712MaRDI QIDQ2117220FDOQ2117220

Claire Hanen, Alix Munier-Kordon, Theo Pedersen

Publication date: 21 March 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-78230-6_14

zbMATH Keywords

energetic reasoningscheduling problemprecedence constraintspreemptive relaxation

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Combinatorial optimization (90C27)

Cites Work

• Introduction to algorithms.
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Algorithms for propagating resource constraints in AI planning and scheduling: Existing approaches and new results
• A new approach to the maximum-flow problem
• Enhanced energetic reasoning-based lower bounds for the resource constrained project scheduling problem
• Une méthode arborescente pour résoudre les problèmes cumulatifs
• Methods to solve multi-skill project scheduling problem
• Two-Processor Scheduling with Start-Times and Deadlines
• Preemptive Scheduling with Release Times, Deadlines, and Due Times
• NP-complete scheduling problems
• Satisfiability tests and time-bound adjustments for cumulative scheduling problems
• A preemptive bound for the resource constrained project scheduling problem
• A fixed-parameter algorithm for scheduling unit dependent tasks on parallel machines with time windows
• The worst-case analysis of the Garey-Johnson algorithm
• A \(O(n\log ^2 n)\) checker and \(O(n^2\log n)\) filtering algorithm for the energetic reasoning
• The equivalence of two classical list scheduling algorithms for dependent typed tasks with release dates, due dates and precedence delays
• An \(O(n^2)\) algorithm for time-bound adjustments for the cumulative scheduling problem

Cited In (1)

• Measuring the slack between lower bounds for scheduling on parallel machines

This page was built for publication: Two deadline reduction algorithms for scheduling dependent tasks on parallel processors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2117220)