Demo OR-Tools — Lissage de charge

OR-Tools — Lissage de charge (CP-SAT)

On planifie le début de chaque tâche dans sa fenêtre [earliest, latest] pour minimiser le pic de charge journalière. Solveur : cp_model.

Mode d'emploi. Une ligne = une tâche à planifier. ID : nom auto de la tâche · Charge : charge consommée chaque jour où elle tourne (ex. h/jour, ETP) · Durée : nombre de jours consécutifs d'exécution · Earliest : 1^er jour de démarrage autorisé (0 = J0) · Latest : dernier jour de démarrage autorisé (doit laisser la place à la durée dans l'horizon). Le solveur choisit un start ∈ [Earliest, Latest] qui minimise le pic de charge journalière.

ID	Charge	Durée	Earliest	Latest

Pic naïf (tout au + tôt) –

Pic lissé –

Statut –

Planning résolu

📐 Modèle mathématique (CP-SAT)

Données

$T$ = tâches, horizon $H$ (jours $d \in \{0,\dots,H-1\}$). Pour chaque tâche $i$ : charge $\ell_i$, durée $p_i$, fenêtre de démarrage $[e_i,f_i]$.

Variables de décision

$$ s_i \in \{e_i,\dots,f_i\} \quad\text{(jour de début)},\qquad a_{i,d} \in \{0,1\} \quad\text{(tâche $i$ active au jour $d$)} $$ $$ C_d \in \mathbb{Z}_{\ge 0} \quad\text{(charge du jour $d$)},\qquad P \in \mathbb{Z}_{\ge 0} \quad\text{(pic)} $$

Contraintes

Lien activité ↔ date de début : $a_{i,d}=1 \iff s_i \le d \le s_i+p_i-1$

$$ a_{i,d}=1 \;\Rightarrow\; s_i \le d \;\wedge\; s_i+p_i-1 \ge d $$ $$ a_{i,d}=0 \;\Rightarrow\; s_i>d \;\vee\; s_i+p_i-1Charge journalière et pic :

$$ C_d = \sum_{i\in T} \ell_i \cdot a_{i,d}, \qquad P \ge C_d \;\;\forall d $$

Objectif

$$ \boxed{\;\min\; P \;=\; \min\; \max_{d} \; \sum_{i} \ell_i \, a_{i,d}\;} $$

Traduction en code (app.py)

s_i → NewIntVar(e_i, f_i) · a_{i,d} → NewBoolVar() avec OnlyEnforceIf + AddBoolOr · C_d = Σ ℓ·a → model.Add(v == sum(...)) · P = max C_d → AddMaxEquality · objectif → model.Minimize(peak).