Gerer les exceptions reelles dans CP-SAT

Le probleme des exceptions

Un solveur de planification qui ne gere que le cas "normal" est inutile. Les plannings reels sont remplis d'exceptions : jours feries, vacances, jours de repos personnels, regles de weekend par type de contrat, plafonds d'heures, limites par qualification. Chaque mois est different. Chaque employe a son propre jeu de contraintes.

La question n'est pas de savoir si le modele peut gerer les exceptions. C'est de savoir s'il peut les absorber sans modification de code. Si ajouter des vacances implique de modifier le code du solveur, le systeme est fragile. Si cela implique d'ajouter une ligne en base de donnees, le systeme est robuste.

Cet article decrit comment un modele de planification CP-SAT gere six types d'exceptions reelles, entierement par injection de donnees. Les types de contraintes, leur implementation dans le modele, et leur impact sur les calculs d'equite et le comportement du solveur.

HOLIDAY : jours feries

Quand un employe est en conge ferie le jour d, le solveur doit garantir qu'aucun shift ne lui est affecte ce jour-la. L'employe est en repos, point final.

Implementation

# Pour chaque employe e avec HOLIDAY le jour d :
for s in all_qualified_shifts(e):
    model.Add(assign[e, d, s] == 0)
model.Add(is_off[e, d] == 1)

Chaque variable d'affectation pour cet employe ce jour-la est fixee a 0. La variable de jour de repos est fixee a 1. Le solveur ne decide rien pour ce jour. Il le saute et optimise tout le reste autour.

L'employe ne compte pas dans la couverture de ce jour. Ses jours de travail cibles pour le mois sont reduits en consequence, le solveur ne le penalise donc pas pour un jour ou il n'etait de toute facon pas disponible.

VACATION : blocs d'absence contigus

Les vacances fonctionnent exactement comme HOLIDAY, mais pour un bloc de jours contigus. Si un employe est en vacances du jour 5 au jour 14, le solveur fixe toutes les variables d'affectation a 0 et toutes les variables de jour de repos a 1 pour ces 10 jours.

Implementation

# Pour chaque employe e avec VACATION du jour d_start au jour d_end :
for d in range(d_start, d_end + 1):
    for s in all_qualified_shifts(e):
        model.Add(assign[e, d, s] == 0)
    model.Add(is_off[e, d] == 1)

La difference cle avec HOLIDAY est l'impact sur les cibles mensuelles. 10 jours de vacances reduisent proportionnellement les heures cibles et les jours de travail cibles de l'employe. Le solveur ajuste automatiquement les attentes : il n'essaie pas de caser 22 jours de travail dans les 20 jours restants. Il recalcule la cible en fonction de la disponibilite reelle de l'employe.

C'est critique pour l'equite. Sans ajustement des cibles, un employe en vacances 2 semaines aurait environ moitie moins de jours travailles que ses collegues, creant un ecart d'equite artificiel que le solveur gaspillerait de l'effort a essayer de combler.

FIXED_OFF : jours de repos demandes

FIXED_OFF est le meme mecanisme que HOLIDAY, applique a un jour specifique demande a l'avance par l'employe. Utilisations courantes : rendez-vous medical, obligation personnelle, journee de formation, evenement familial.

Implementation

# Pour chaque employe e avec FIXED_OFF le jour d :
for s in all_qualified_shifts(e):
    model.Add(assign[e, d, s] == 0)
model.Add(is_off[e, d] == 1)

Du point de vue du solveur, FIXED_OFF est identique a HOLIDAY. La distinction existe dans la couche metier : HOLIDAY vient du calendrier des jours feries, FIXED_OFF vient d'une demande de l'employe validee par le planificateur. Le solveur ne se soucie pas de la raison. Il voit une contrainte et la respecte.

NOT_WEEKEND : regles contractuelles etudiants

Les employes etudiants ne devraient pas travailler les weekends. C'est une regle de niveau contrat, pas une demande individuelle. Chaque employe avec contract_type == "etudiant" recoit cette contrainte automatiquement.

Implementation

# Pour chaque employe etudiant e, pour chaque jour de weekend d (samedi/dimanche) :
for s in all_qualified_shifts(e):
    model.Add(assign[e, d, s] == 0)

Contrairement a HOLIDAY ou FIXED_OFF, on ne force pas is_off[e, d] = 1 les jours de weekend pour les etudiants. Le solveur est libre de leur donner le jour de repos ou non. La contrainte dit seulement : s'ils travaillent, ce ne peut pas etre un jour de weekend.

Les etudiants sont egalement exclus de la penalite de garantie de weekend. Puisqu'ils ne travaillent jamais les weekends, les penaliser pour ne pas avoir de weekend de repos serait absurde. La penalite ne s'applique qu'aux employes non etudiants.

MAX_HOURS et MAX_SHIFTS_PER_QUALIF

Deux contraintes supplementaires de niveau contrat plafonnent la charge de travail :

# MAX_HOURS : plafonner les minutes totales travaillees pour l'employe e
model.Add(total_minutes[e] <= max_hours_value * 60)

# MAX_SHIFTS_PER_QUALIF : plafonner les shifts dans la fonction f pour l'employe e
model.Add(total_shifts_per_function[e, f] <= max_shifts_value)

MAX_HOURS empeche un employe de depasser sa limite contractuelle d'heures. MAX_SHIFTS_PER_QUALIF empeche la surconcentration sur une seule fonction, garantissant que les employes maintiennent une experience diversifiee a travers leurs qualifications.

Impact sur les calculs d'equite

Les objectifs d'equite mesurent la repartition equitable du travail au sein de chaque groupe. Le solveur minimise l'ecart entre l'employe qui travaille le plus et celui qui travaille le moins. Mais que se passe-t-il quand certains employes sont absents une partie du mois ?

Le probleme sans exclusion

Prenons un groupe de 10 employes. 8 sont disponibles tout le mois. 2 sont en vacances 2 semaines. Sans traitement special, les 2 employes en vacances auraient environ moitie moins de jours travailles que leurs collegues. L'ecart d'equite serait enorme, et le solveur gaspillerait de l'effort de recherche a essayer de le reduire, degradant potentiellement d'autres objectifs.

La solution : exclure les employes absents

# Equite charge de travail : exclure les employes avec HOLIDAY ou VACATION
active_employees = [e for e in group if not has_holiday_or_vacation(e)]
gap = max_days_worked[active] - min_days_worked[active]
penalty += gap * WEIGHT_WORKLOAD_EQUITY

# Equite par qualification : meme exclusion
active_employees = [e for e in group if not has_holiday_or_vacation(e)]
gap = max_shifts[active, f] - min_shifts[active, f]
penalty += gap * WEIGHT_QUALIF_EQUITY

Les employes avec des contraintes HOLIDAY ou VACATION sont exclus des deux calculs d'equite : equite de charge (jours travailles) et equite par qualification (shifts par fonction). Cela garantit que le solveur ne mesure l'equite qu'entre les employes reellement disponibles sur toute la periode.

Le resultat : les penalites d'equite refletent des desequilibres reels que le solveur peut corriger, pas des ecarts artificiels causes par des absences planifiees.

Adaptation dynamique

L'injection de contraintes est entierement pilotee par les donnees. Le modele ne contient aucun nom d'employe, date ou regle d'exception en dur. Tout provient des donnees d'entree.

Le flux de donnees

# 1. Charger les contraintes depuis la base de donnees / JSON
constraints = load_constraints()
# Exemple : [
#   {"employee_id": 42, "type": "VACATION", "start": "2026-03-10", "end": "2026-03-21"},
#   {"employee_id": 17, "type": "HOLIDAY", "day": "2026-03-28"},
#   {"employee_id": 55, "type": "NOT_WEEKEND"},
#   {"employee_id": 8,  "type": "MAX_HOURS", "value": 160},
# ]

# 2. Injecter dans le modele au moment de la construction
for c in constraints:
    if c["type"] == "HOLIDAY":
        inject_holiday(model, c["employee_id"], c["day"])
    elif c["type"] == "VACATION":
        inject_vacation(model, c["employee_id"], c["start"], c["end"])
    elif c["type"] == "FIXED_OFF":
        inject_fixed_off(model, c["employee_id"], c["day"])
    elif c["type"] == "NOT_WEEKEND":
        inject_not_weekend(model, c["employee_id"])
    elif c["type"] == "MAX_HOURS":
        inject_max_hours(model, c["employee_id"], c["value"])
    elif c["type"] == "MAX_SHIFTS_PER_QUALIF":
        inject_max_shifts(model, c["employee_id"], c["function"], c["value"])

Ajouter de nouvelles vacances est un changement de donnees, pas un changement de code. Le planificateur saisit la contrainte via le tableau de bord, elle est stockee en base de donnees, et le prochain lancement du solveur la prend en compte automatiquement. Pas de deploiement, pas de recompilation, pas de risque de casser le modele.

Pas de recodage necessaire

Les six types de contraintes couvrent la grande majorite des exceptions de planification reelles :

Type de contrainte	Portee	Effet sur le modele	Effet sur l'equite
HOLIDAY	Jour unique	assign = 0, is_off = 1	Employe exclu
VACATION	Plage de jours	assign = 0, is_off = 1 (chaque jour)	Employe exclu
FIXED_OFF	Jour unique	assign = 0, is_off = 1	Pas d'exclusion
NOT_WEEKEND	Tous les weekends	assign = 0 sam/dim	Exclu de la penalite weekend
MAX_HOURS	Mois entier	total_minutes ≤ plafond	Pas d'effet
MAX_SHIFTS_PER_QUALIF	Par fonction	total_shifts_per_function ≤ plafond	Pas d'effet

Ces six types gerent environ 95% des exceptions rencontrees dans les operations reelles de ground handling. Le planificateur les saisit via l'interface du tableau de bord, elles transitent par la base de donnees vers le solveur sous forme de donnees structurees, et le modele les absorbe au moment de la construction.

Les 5% restants ? Des cas limites comme les echanges de shifts entre deux employes specifiques, ou les montees en competence temporaires. Ceux-ci sont geres en dehors du solveur, comme ajustements manuels apres la generation du planning. Essayer d'encoder chaque cas limite dans le modele ajouterait de la complexite sans benefice significatif.

Le principe de conception est clair : le solveur gere les regles, les donnees gerent les exceptions. Quand les regles ne changent pas mais les exceptions si (ce qui est le cas chaque mois), aucun code ne doit changer. Le planificateur garde le controle via l'interface, et le solveur s'adapte automatiquement.