Gérer les exceptions réelles dans CP-SAT

Le problème des exceptions

Un solveur de planification qui ne gère que le cas "normal" est inutile. Les plannings réels sont remplis d'exceptions : jours fériés, vacances, jours de repos personnels, règles de weekend par type de contrat, plafonds d'heures, limites par qualification. Chaque mois est différent. Chaque employé a son propre jeu de contraintes.

La question n'est pas de savoir si le modèle peut gérer 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 système est fragile. Si cela implique d'ajouter une ligne en base de données, le système est robuste.

Cet article décrit comment un modèle de planification CP-SAT gère six types d'exceptions réelles, entièrement par injection de données. Les types de contraintes, leur implémentation dans le modèle, et leur impact sur les calculs d'équité et le comportement du solveur.

HOLIDAY : jours fériés

Quand un employé est en congé férié le jour d, le solveur doit garantir qu'aucun shift ne lui est affecté ce jour-là. L'employé est en repos, point final.

Implémentation

# 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 employé ce jour-là est fixée à 0. La variable de jour de repos est fixée à 1. Le solveur ne décide rien pour ce jour. Il le saute et optimise tout le reste autour.

L'employé ne compte pas dans la couverture de ce jour. Ses jours de travail cibles pour le mois sont réduits en conséquence, le solveur ne le pénalise donc pas pour un jour où il n'était de toute façon pas disponible.

VACATION : blocs d'absence contigus

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

Implémentation

# 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 différence clé avec HOLIDAY est l'impact sur les cibles mensuelles. 10 jours de vacances réduisent proportionnellement les heures cibles et les jours de travail cibles de l'employé. 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 disponibilité réelle de l'employé.

C'est critique pour l'équité. Sans ajustement des cibles, un employé en vacances 2 semaines aurait environ moitié moins de jours travaillés que ses collègues, créant un écart d'équité artificiel que le solveur gaspillerait de l'effort à essayer de combler.

FIXED_OFF : jours de repos demandes

FIXED_OFF est le même mécanisme que HOLIDAY, applique à un jour spécifique demandé à l'avance par l'employé. Utilisations courantes : rendez-vous médical, obligation personnelle, journée de formation, événement familial.

Implémentation

# 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 à HOLIDAY. La distinction existe dans la couche métier : HOLIDAY vient du calendrier des jours fériés, FIXED_OFF vient d'une demande de l'employé validée par le planificateur. Le solveur ne se soucie pas de la raison. Il voit une contrainte et la respecte.

NOT_WEEKEND : règles contractuelles étudiants

Les employés étudiants ne devraient pas travailler les weekends. C'est une règle de niveau contrat, pas une demande individuelle. Chaque employé avec contract_type == "etudiant" reçoit cette contrainte automatiquement.

Implémentation

# 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 à HOLIDAY ou FIXED_OFF, on ne force pas is_off[e, d] = 1 les jours de weekend pour les étudiants. Le solveur est libre de leur donner le jour de repos ou non. La contrainte dit seulement : s'ils travaillent, ce ne peut pas être un jour de weekend.

Les étudiants sont également exclus de la pénalité de garantie de weekend. Puisqu'ils ne travaillent jamais les weekends, les pénaliser pour ne pas avoir de weekend de repos serait absurde. La pénalité ne s'applique qu'aux employés non étudiants.

MAX_HOURS et MAX_SHIFTS_PER_QUALIF

Deux contraintes supplémentaires 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 empêche un employé de dépasser sa limite contractuelle d'heures. MAX_SHIFTS_PER_QUALIF empêche la surconcentration sur une seule fonction, garantissant que les employés maintiennent une expérience diversifiée à travers leurs qualifications.

Impact sur les calculs d'équité

Les objectifs d'équité mesurent la répartition équitable du travail au sein de chaque groupe. Le solveur minimise l'écart entre l'employé qui travaille le plus et celui qui travaille le moins. Mais que se passe-t-il quand certains employés sont absents une partie du mois ?

Le problème sans exclusion

Prenons un groupe de 10 employés. 8 sont disponibles tout le mois. 2 sont en vacances 2 semaines. Sans traitement spécial, les 2 employés en vacances auraient environ moitié moins de jours travaillés que leurs collègues. L'écart d'équité serait énorme, et le solveur gaspillerait de l'effort de recherche à essayer de le réduire, dégradant potentiellement d'autres objectifs.

La solution : exclure les employés 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 employés avec des contraintes HOLIDAY ou VACATION sont exclus des deux calculs d'équité : équité de charge (jours travaillés) et équité par qualification (shifts par fonction). Cela garantit que le solveur ne mesure l'équité qu'entre les employés réellement disponibles sur toute la période.

Le résultat : les pénalités d'équité reflètent des déséquilibres réels que le solveur peut corriger, pas des écarts artificiels causes par des absences planifiées.

Adaptation dynamique

L'injection de contraintes est entièrement pilotée par les données. Le modèle ne contient aucun nom d'employé, date ou règle d'exception en dur. Tout provient des données d'entrée.

Le flux de données

# 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 données, pas un changement de code. Le planificateur saisit la contrainte via l'interface, elle est stockée en base de données, et le prochain lancement du solveur la prend en compte automatiquement. Pas de déploiement, pas de recompilation, pas de risque de casser le modèle.

Pas de recodage nécessaire

Les six types de contraintes couvrent la grande majorité des exceptions de planification réelles :

Type de contrainte	Portée	Effet sur le modèle	Effet sur l'équité
HOLIDAY	Jour unique	assign = 0, is_off = 1	Employé exclu
VACATION	Plage de jours	assign = 0, is_off = 1 (chaque jour)	Employé 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 pénalité 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 gèrent environ 95% des exceptions rencontrées dans les opérations réelles de ground handling. Le planificateur les saisit via l'interface de l'application, elles transitent par la base de données vers le solveur sous forme de données structurées, et le modèle les absorbe au moment de la construction.

Les 5% restants ? Des cas limites comme les échanges de shifts entre deux employés spécifiques, ou les montées en compétence temporaires. Ceux-ci sont gérés en dehors du solveur, comme ajustements manuels après la génération du planning. Essayer d'encoder chaque cas limite dans le modèle ajouterait de la complexité sans bénéfice significatif.

Le principe de conception est clair : le solveur gère les règles, les données gèrent les exceptions. Quand les règles ne changent pas mais les exceptions si (ce qui est le cas chaque mois), aucun code ne doit changer. Le planificateur garde le contrôle via l'interface, et le solveur s'adapte automatiquement.