ROADEF 2026>
Lower Bound for the Cumulative Scheduling Problem Using Redundant Resources and Jackson Scheduling
Kristina Kumbria  1@  , Jacques Carlier  1@  , Antoine Jouglet  1@  , Abderrahim Sahli  2@  
1 : Heudiasyc, Université de compiègne
Sorbonne Universités, UPMC, CNRS
2 : Laboratoire dÍnformatique Gaspard-Monge
Ecole des Ponts ParisTech, Centre National de la Recherche Scientifique, Université Gustave Eiffel, Centre National de la Recherche Scientifique : UMR8049


The Cumulative Scheduling Problem (CuSP) consists in scheduling a set of tasks under resource and time constraints in order to minimize the project makespan (\(C_{\max}\)). Each task \(i\) is characterized by its release date (\(r_i\)), processing time (\(p_i\)), tail (\(q_i\)), and a resource unit requirement (\(c_i\)) when $m$ is the total resource units available. A schedule is feasible if tasks start no earlier than their release dates and if, at any time $t$, the cumulative resource consumption satisfies
\(
\sum_{i \in I(t)} c_i \le m,
\)
where $I(t)$ is the set of tasks executing at time $t$.
The makespan is given by:
\(
C_{\max} = \max_{i \in I}(C_i + q_i),
\)
where \(C_i\) is the completion time of task \(i\).

 

Energetic reasoning (ER), introduced by Erschler and Lopez \cite{b12}, is a fundamental method for CuSP. It compares, over any interval $[\alpha,\delta]$, the available energy $m(\delta-\alpha)$ with the minimum energy required by the tasks.
Each task intersecting the interval requires a minimum amount of energy, defined as the product of its processing time executed within the interval and its resource requirement. If the required energy exceeds the available energy, the interval is
infeasible, and the candidate value of $C_{\max}$ must be increased.


In this work, we propose lower bounds for the CuCP. Our lower bound is computed as follows. First, redundant resources are used to strengthen energetic reasoning by transforming resource requirements while preserving feasibility. Then, a Jackson-scheduling-based filter eliminates intervals that cannot be critical, reducing the number of energetic tests that must be evaluated.


Chargement... Chargement...