CP-SAT Planification : Modeliser 300 Employes

Le probleme : planification mensuelle a grande echelle

Prenons un probleme reel de planification : 300 employes repartis sur plusieurs groupes fonctionnels, chacun detenant une ou plusieurs qualifications. 50 types de shifts avec des horaires de debut, de fin et des structures de pause differentes. 30 jours a planifier. Des besoins journaliers variables qui dependent du jour de la semaine et des cycles d'activite.

Chaque employe a un type de contrat (fixe, auxiliaire, etudiant) qui determine ses heures cibles mensuelles, ses jours de repos et ses regles de weekend. Certains employes ont des absences pre-assignees : conges, vacances, jours de repos fixes. Le solveur doit respecter tout cela tout en produisant un planning qui couvre chaque besoin, distribue la charge equitablement et respecte les reglementations du travail.

Cet article decrit le modele CP-SAT exact que nous utilisons pour resoudre ce probleme. Chaque variable, contrainte et objectif decrit ici tourne en production.

Variables de decision

Le modele commence avec trois types de variables :

Variables d'affectation

assign[e, d, s]  # Booleen : l'employe e travaille le shift s le jour d

Une variable booleenne pour chaque combinaison employe-jour-shift possible. Pour 300 employes, 30 jours et 50 shifts, cela represente jusqu'a 450 000 variables. En pratique, le nombre est inferieur car les employes ne peuvent etre affectes qu'aux shifts correspondant a leurs qualifications.

Variables de jour de repos

is_off[e, d]  # Booleen : l'employe e ne travaille pas le jour d

Une variable par employe par jour. 300 × 30 = 9 000 variables. Liees aux variables d'affectation : is_off[e, d] = 1 si et seulement si aucun shift n'est affecte a l'employe e le jour d.

Variables agregees

total_minutes[e]            # Entier : minutes totales travaillees par l'employe e
total_shifts_per_function[e, f]  # Entier : shifts travailles par e dans la fonction f

Variables derivees que le solveur calcule a partir des variables d'affectation. Utilisees dans les objectifs d'equite pour mesurer la repartition de la charge au sein de l'equipe.

Contraintes dures

Les contraintes dures sont non negociables. Si le solveur ne peut pas toutes les satisfaire simultanement, le probleme est declare INFEASIBLE. Aucun planning n'est produit.

Un shift par jour

# Pour chaque employe e, pour chaque jour d :
sum(assign[e, d, s] for s in all_shifts) <= 1

Un employe travaille au plus un shift par jour. Combine avec is_off, cela signifie que chaque employe-jour est soit exactement un shift, soit un jour de repos.

Repos minimum entre shifts (11 heures)

La reglementation du travail impose un repos minimum entre la fin d'un shift et le debut du suivant. Le standard est de 11 heures. Au lieu de calculer les differences de temps pendant la resolution, nous pre-calculons les paires toxiques : les paires de shifts (s1, s2) ou le shift s1 le jour d suivi du shift s2 le jour d+1 violerait la regle des 11 heures.

# Pour chaque paire toxique (s1, s2), pour chaque employe e, pour chaque jour d :
assign[e, d, s1] + assign[e, d+1, s2] <= 1

Pre-calculer les paires toxiques est nettement plus efficace qu'encoder l'arithmetique temporelle dans le modele. Pour 50 types de shifts, le nombre de paires toxiques est typiquement de 200-400, ce qui genere un nombre gerable de contraintes.

Respect des qualifications

# Si l'employe e n'a pas la qualification pour le shift s :
assign[e, d, s] = 0  (pour tous les jours d)

Chaque shift appartient a une fonction (ex : securite, logistique, maintenance). Chaque employe detient des qualifications pour des fonctions specifiques. Le solveur ne peut affecter un employe qu'a un shift pour lequel il est qualifie. En pratique, cela est implemente en ne creant simplement pas la variable assign pour les combinaisons employe-shift invalides, ce qui reduit la taille du modele.

Absences pre-assignees

# HOLIDAY, VACATION, FIXED_OFF le jour d pour l'employe e :
assign[e, d, s] = 0  (pour tous les shifts s)
is_off[e, d] = 1

Les absences sont injectees comme valeurs fixes avant l'execution du solveur. Le solveur ne decide pas si un employe est en conge. Il respecte l'absence pre-assignee et optimise tout le reste autour.

Objectifs souples

Les contraintes souples sont des objectifs que le solveur tente d'atteindre mais peut violer si necessaire. Chaque violation ajoute une penalite a la fonction objectif. Le solveur minimise le score total de penalite : plus bas = meilleur.

Couverture

L'objectif le plus critique. Pour chaque fonction, chaque jour a un besoin en effectif (ex : "3 agents securite le lundi"). Le solveur penalise chaque poste non couvert.

# Pour chaque fonction f, pour chaque jour d :
assigned_count = sum(assign[e, d, s] for e qualifie pour f, s dans fonction f)
missing = max(0, need[f, d] - assigned_count)
penalty += missing * WEIGHT_COVERAGE

Jours de repos

Chaque employe a un nombre cible de jours de repos par mois (derive du type de contrat et des jours ouvrables du mois). Le solveur penalise les jours de repos manquants.

# Pour chaque employe e :
actual_off = sum(is_off[e, d] for d in mois)
missing_off = max(0, target_off[e] - actual_off)
penalty += missing_off * WEIGHT_DAYS_OFF

Garantie de weekend

Chaque employe devrait avoir au moins un weekend complet de repos (samedi + dimanche) par mois. Les employes de type "etudiant" sont exclus de cette contrainte.

# Pour chaque employe e (non etudiant) :
has_weekend_off = max sur tous les weekends w de :
    (is_off[e, samedi_w] AND is_off[e, dimanche_w])
penalty += (1 - has_weekend_off) * WEIGHT_WEEKEND

Equite de charge (jours travailles)

Au sein de chaque groupe fonctionnel, l'ecart entre l'employe qui travaille le plus et celui qui travaille le moins doit etre minimal. Les employes en conge ou en vacances sont exclus du calcul d'equite pour ne pas penaliser le solveur pour des absences qu'il ne controle pas.

# Pour chaque groupe g :
gap = max_jours_travailles[g] - min_jours_travailles[g]
penalty += gap * WEIGHT_WORKLOAD_EQUITY

Equite par qualification (shifts par fonction)

Au sein de chaque groupe, les shifts doivent etre distribues equitablement entre les types de qualification. Un employe qualifie pour la securite et la logistique ne devrait pas etre affecte exclusivement a la securite pendant que d'autres n'ont que la logistique.

# Pour chaque groupe g, pour chaque fonction f :
gap = max_shifts[g, f] - min_shifts[g, f]
penalty += gap * WEIGHT_QUALIF_EQUITY

Jours consecutifs de travail

Travailler plus de 6 jours consecutifs est penalise. C'est une contrainte souple plutot que dure car dans certains cas limites (sous-effectif), le solveur peut avoir besoin de depasser 6 jours pour maintenir la couverture.

# Pour chaque employe e, pour chaque fenetre de 7 jours consecutifs :
si les 7 jours sont travailles : penalty += WEIGHT_CONSECUTIVE

Jours de repos isoles

Un jour de repos isole entre deux jours de travail est moins reposant que des jours de repos consecutifs. Le solveur penalise ces jours isoles pour encourager le regroupement.

# Pour chaque employe e, pour chaque jour d (sauf premier et dernier) :
si is_off[e, d] AND NOT is_off[e, d-1] AND NOT is_off[e, d+1] :
    penalty += WEIGHT_ISOLATED_OFF

Calibration des penalites

Les poids de penalite creent une hierarchie de priorite. Le solveur sacrifiera les objectifs de priorite basse pour preserver les objectifs de priorite haute.

Objectif	Poids de penalite	Priorite
Couverture manquante	Tres eleve	Maximale
Pas de weekend garanti	Eleve	Haute
Jours consecutifs > 6	Eleve	Haute
Jours de repos manquants	Moyen	Moyenne
Jour de repos isole	Moyen	Moyenne
Ecart equite par qualification	Faible	Basse
Ecart equite charge de travail	Tres faible	Minimale

La logique : un poste non couvert (poids maximum) est toujours pire qu'un jour de repos manquant (poids moyen). Un jour de repos manquant est pire qu'une repartition legerement inequitable. Cette hierarchie garantit que le solveur fait les bons compromis quand il ne peut pas satisfaire parfaitement tous les objectifs.

Un bon planning se situe typiquement dans une fourchette previsible points. Un score de zero signifierait que chaque objectif est parfaitement atteint, ce qui est rarement possible avec des donnees reelles. La decomposition des penalites montre exactement d'ou vient le score, donnant au planificateur des indications claires sur ce qu'il faut ajuster dans les donnees d'entree.

Taille du modele en pratique

Voici a quoi ressemble le modele pour differentes tailles d'operation :

Employes	Variables booleennes	Contraintes (approx.)	Termes de penalite
100	~80 000	~120 000	~15 000
150	~130 000	~200 000	~25 000
200	~180 000	~300 000	~35 000
300	~280 000	~500 000	~55 000

Ces chiffres supposent le filtrage par qualification (pas de creation de variables pour les paires employe-shift invalides). Sans filtrage, le modele a 300 employes aurait 450 000 variables booleennes. Le filtrage en elimine typiquement 30 a 50%.

Benchmarks de performance

Mesures sur un serveur standard (8 coeurs, 16 Go RAM), avec la recherche multi-thread de CP-SAT a 8 workers :

Employes	Temps premiere solution	Temps meilleure solution	Ecart d'optimalite
100	< 30 secondes	2-3 minutes	< 1%
150	~1 minute	3-5 minutes	1-2%
200	~2 minutes	8-15 minutes	2-5%
300	~4 minutes	15-30 minutes	3-8%

"Temps premiere solution" est le temps necessaire pour trouver un planning faisable. "Temps meilleure solution" est le temps de convergence vers le meilleur score dans la limite de temps configuree. L'"ecart d'optimalite" est la difference entre la meilleure solution trouvee et la borne inferieure theorique.

En pratique, le solveur trouve une bonne solution rapidement, puis passe le temps restant a l'ameliorer incrementalement. Le planificateur peut configurer la limite de temps selon ses exigences de qualite. CP-SAT retourne toujours la meilleure solution trouvee dans le temps imparti.

Conseils pratiques pour passer a l'echelle

Reduire l'espace de variables

Ne creez pas assign[e, d, s] pour les combinaisons impossibles. Si l'employe e n'est pas qualifie pour le shift s, ou si e a une absence pre-assignee le jour d, ne creez pas la variable. Cela peut reduire le modele de 30 a 50%.

Pre-calculer les paires toxiques

Calculer les violations de repos au moment de la construction du modele (sous forme de liste de paires de shifts interdites) est beaucoup plus rapide qu'encoder l'arithmetique temporelle dans CP-SAT. Le solveur gere efficacement les implications booleennes.

Utiliser la recherche multi-thread

CP-SAT execute plusieurs strategies de recherche en parallele. Reglez num_workers sur le nombre de coeurs CPU disponibles. Sur une machine a 8 coeurs, cela reduit typiquement le temps de resolution de 3 a 5x par rapport a la recherche mono-thread.

Exclure les absents de l'equite

Les employes en conge ou en vacances doivent etre exclus des calculs d'equite intra-groupe. Sinon, le solveur se penalise pour un ecart qu'il ne peut pas combler, gaspillant de l'effort de recherche sur un objectif impossible.

Definir une limite de temps pertinente

Pour 100-150 employes, 5 minutes suffisent generalement. Pour 200-300+, accordez 15-30 minutes. Le comportement anytime de CP-SAT signifie qu'il a toujours une solution valide prete, meme s'il est interrompu tot. Une limite de temps plus longue produit un score marginalement meilleur, pas un planning fondamentalement different.

Surveiller la decomposition de l'objectif

Quand le score total de penalite est eleve, regardez la decomposition. Si 80% de la penalite vient des manques de couverture, le probleme est le sous-effectif, pas le tuning du solveur. Si les penalites d'equite dominent, les groupes sont peut-etre desequilibres. La structure de penalite transforme le solveur en outil de diagnostic.