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

DOI10.1016/J.EJOR.2020.03.079MaRDI QIDQ2184136zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• Satisfiability tests and time-bound adjustments for cumulative scheduling problems
• A cumulative not-first/not-last filtering algorithm in \(O(n^2 \log(n))\)
• Energetic reasoning revisited: Application to parallel machine scheduling
• A \(O(n\log ^2 n)\) checker and \(O(n^2\log n)\) filtering algorithm for the energetic reasoning
• A quadratic edge-finding filtering algorithm for cumulative resource constraints

Cites work

• scientific article; zbMATH DE number 1220053 (Why is no real title available?)
• A \(O(n\log ^2 n)\) checker and \(O(n^2\log n)\) filtering algorithm for the energetic reasoning
• A linear programming and constraint propagation-based lower bound for the RCPSP
• Adjustment of heads and tails for the job-shop problem
• Cumulative scheduling with variable task profiles and concave piecewise linear processing rate functions
• Energetic reasoning for energy-constrained scheduling with a continuous resource
• Jackson's pseudo preemptive schedule for the \(Pm/r_i, q_i/C_{\text{max}}\) scheduling problem
• Jackson's pseudo-preemptive schedule and cumulative scheduling problems
• Satisfiability tests and time-bound adjustments for cumulative scheduling problems
• Scheduling jobs with release dates and tails on identical machines to minimize the makespan
• The one-machine sequencing problem
• Timetable edge finding filtering algorithm for discrete cumulative resources

Cited in

(6)

• Two deadline reduction algorithms for scheduling dependent tasks on parallel processors
• Algorithms to compute the energetic lower bounds of the cumulative scheduling problem
• Measuring the slack between lower bounds for scheduling on parallel machines
• Horizontally elastic edge-finder algorithm for cumulative resource constraint revisited
• Satisfiability tests and time-bound adjustments for cumulative scheduling problems
• A data structure for efficiently managing a set of energy functions

Describes a project that uses

Uses Software

• CHIP

This page was built for publication: An \(O(n^2)\) algorithm for time-bound adjustments for the cumulative scheduling problem

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