An \(O(n^2)\) algorithm for time-bound adjustments for the cumulative scheduling problem

DOI10.1016/j.ejor.2020.03.079zbMath1443.90174OpenAlexW3016605981MaRDI QIDQ2184136

Antoine Jouglet, Éric Pinson, Jacques Carlier, Abderrahim Sahli

Publication date: 27 May 2020

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2020.03.079

zbMATH Keywords

schedulingenergetic reasoningadjustmentcumulative resource

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items

Horizontally elastic edge-finder algorithm for cumulative resource constraint revisited, A data structure for efficiently managing a set of energy functions, Two deadline reduction algorithms for scheduling dependent tasks on parallel processors

Uses Software

• CHIP

Cites Work

• Unnamed Item
• Jackson's pseudo-preemptive schedule and cumulative scheduling problems
• Scheduling jobs with release dates and tails on identical machines to minimize the makespan
• The one-machine sequencing problem
• Jackson's pseudo preemptive schedule for the \(Pm/r_i, q_i/C_{\text{max}}\) scheduling problem
• Adjustment of heads and tails for the job-shop problem
• A linear programming and constraint propagation-based lower bound for the RCPSP
• A \(O(n\log ^2 n)\) checker and \(O(n^2\log n)\) filtering algorithm for the energetic reasoning
• Cumulative scheduling with variable task profiles and concave piecewise linear processing rate functions
• Satisfiability tests and time-bound adjustments for cumulative scheduling problems
• Energetic reasoning for energy-constrained scheduling with a continuous resource
• Timetable Edge Finding Filtering Algorithm for Discrete Cumulative Resources