CP-SAT Planification : Modéliser 300 Employés

Le problème : planification mensuelle à grande échelle

Prenons un problème réel de planification : 300 employés répartis sur plusieurs groupes fonctionnels, chacun détenant une ou plusieurs qualifications. 50 types de shifts avec des horaires de début, de fin et des structures de pause différentes. 30 jours à planifier. Des besoins journaliers variables qui dépendent du jour de la semaine et des cycles d'activité.

Chaque employé a un type de contrat (fixe, auxiliaire, étudiant) qui détermine ses heures cibles mensuelles, ses jours de repos et ses règles de weekend. Certains employés ont des absences pré-assignées : congés, vacances, jours de repos fixes. Le solveur doit respecter tout cela tout en produisant un planning qui couvre chaque besoin, distribue la charge équitablement et respecte les réglementations du travail.

Cet article décrit le modèle CP-SAT exact que nous utilisons pour résoudre ce problème. Chaque variable, contrainte et objectif décrit ici tourne en production.

Variables de décision

Le modèle 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 booléenne pour chaque combinaison employé-jour-shift possible. Pour 300 employés, 30 jours et 50 shifts, cela représente jusqu'à 450 000 variables. En pratique, le nombre est inférieur car les employés ne peuvent être affectés qu'aux shifts correspondant à leurs qualifications.

Variables de jour de repos

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

Une variable par employé par jour. 300 × 30 = 9 000 variables. Liées aux variables d'affectation : is_off[e, d] = 1 si et seulement si aucun shift n'est affecté à l'employé e le jour d.

Variables agrégées

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 dérivées que le solveur calcule à partir des variables d'affectation. Utilisées dans les objectifs d'équité pour mesurer la répartition de la charge au sein de l'équipe.

Contraintes dures

Les contraintes dures sont non négociables. Si le solveur ne peut pas toutes les satisfaire simultanément, le problème est déclaré 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 employé travaille au plus un shift par jour. Combiné avec is_off, cela signifie que chaque employé-jour est soit exactement un shift, soit un jour de repos.

Repos minimum entre shifts (11 heures)

La réglementation du travail impose un repos minimum entre la fin d'un shift et le début du suivant. Le standard est de 11 heures. Au lieu de calculer les différences de temps pendant la résolution, nous pré-calculons les paires toxiques : les paires de shifts (s1, s2) où le shift s1 le jour d suivi du shift s2 le jour d+1 violerait la règle 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

Pré-calculer les paires toxiques est nettement plus efficace qu'encoder l'arithmétique temporelle dans le modèle. Pour 50 types de shifts, le nombre de paires toxiques est typiquement de 200-400, ce qui génère un nombre gérable 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 à une fonction (ex : sécurité, logistique, maintenance). Chaque employé détient des qualifications pour des fonctions spécifiques. Le solveur ne peut affecter un employé qu'à un shift pour lequel il est qualifié. En pratique, cela est implémenté en ne créant simplement pas la variable assign pour les combinaisons employé-shift invalides, ce qui réduit la taille du modèle.

Absences pré-assignées

# 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 injectées comme valeurs fixes avant l'exécution du solveur. Le solveur ne décide pas si un employé est en congé. Il respecte l'absence pré-assignée et optimise tout le reste autour.

Objectifs souples

Les contraintes souples sont des objectifs que le solveur tente d'atteindre mais peut violer si nécessaire. Chaque violation ajoute une pénalité à la fonction objectif. Le solveur minimise le score total de pénalité : plus bas = meilleur.

Couverture

L'objectif le plus critique. Pour chaque fonction, chaque jour a un besoin en effectif (ex : "3 agents sécurité le lundi"). Le solveur pénalise 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 employé a un nombre cible de jours de repos par mois (dérivé du type de contrat et des jours ouvrables du mois). Le solveur pénalise 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 employé devrait avoir au moins un weekend complet de repos (samedi + dimanche) par mois. Les employés de type "étudiant" 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

Équité de charge (jours travaillés)

Au sein de chaque groupe fonctionnel, l'écart entre l'employé qui travaille le plus et celui qui travaille le moins doit être minimal. Les employés en congé ou en vacances sont exclus du calcul d'équité pour ne pas pénaliser le solveur pour des absences qu'il ne contrôle pas.

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

Équité par qualification (shifts par fonction)

Au sein de chaque groupe, les shifts doivent être distribués équitablement entre les types de qualification. Un employé qualifié pour la sécurité et la logistique ne devrait pas être affecté exclusivement à la sécurité 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 consécutifs de travail

Travailler plus de 6 jours consécutifs est pénalisé. C'est une contrainte souple plutôt que dure car dans certains cas limites (sous-effectif), le solveur peut avoir besoin de dépasser 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 isolés

Un jour de repos isolé entre deux jours de travail est moins reposant que des jours de repos consécutifs. Le solveur pénalise ces jours isolés 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 pénalités

Les poids de pénalité créent une hiérarchie de priorité. Le solveur sacrifiera les objectifs de priorité basse pour préserver les objectifs de priorité haute.

Objectif	Poids de pénalité	Priorité
Couverture manquante	Très élevé	Maximale
Pas de weekend garanti	Élevé	Haute
Jours consécutifs > 6	Élevé	Haute
Jours de repos manquants	Moyen	Moyenne
Jour de repos isolé	Moyen	Moyenne
Écart équité par qualification	Faible	Basse
Écart équité charge de travail	Très 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 répartition légèrement inéquitable. Cette hiérarchie 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 prévisible points. Un score de zéro signifierait que chaque objectif est parfaitement atteint, ce qui est rarement possible avec des données réelles. La décomposition des pénalités montre exactement d'où vient le score, donnant au planificateur des indications claires sur ce qu'il faut ajuster dans les données d'entrée.

Taille du modèle en pratique

Voici à quoi ressemble le modèle pour différentes tailles d'opération :

Employés	Variables booléennes	Contraintes (approx.)	Termes de pénalité
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 création de variables pour les paires employé-shift invalides). Sans filtrage, le modèle à 300 employés aurait 450 000 variables booléennes. Le filtrage en élimine typiquement 30 à 50%.

Benchmarks de performance

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

Employés	Temps première solution	Temps meilleure solution	Écart d'optimalité
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 première solution" est le temps nécessaire pour trouver un planning faisable. "Temps meilleure solution" est le temps de convergence vers le meilleur score dans la limite de temps configurée. L'"écart d'optimalité" est la différence entre la meilleure solution trouvée et la borne inférieure théorique.

En pratique, le solveur trouve une bonne solution rapidement, puis passe le temps restant à l'améliorer incrémentalement. Le planificateur peut configurer la limite de temps selon ses exigences de qualité. CP-SAT retourne toujours la meilleure solution trouvée dans le temps imparti.

Conseils pratiques pour passer à l'échelle

Réduire l'espace de variables

Ne créez pas assign[e, d, s] pour les combinaisons impossibles. Si l'employé e n'est pas qualifié pour le shift s, ou si e à une absence pré-assignée le jour d, ne créez pas la variable. Cela peut réduire le modèle de 30 à 50%.

Pré-calculer les paires toxiques

Calculer les violations de repos au moment de la construction du modèle (sous forme de liste de paires de shifts interdites) est beaucoup plus rapide qu'encoder l'arithmétique temporelle dans CP-SAT. Le solveur gère efficacement les implications booléennes.

Utiliser la recherche multi-thread

CP-SAT exécute plusieurs stratégies de recherche en parallèle. Réglez num_workers sur le nombre de coeurs CPU disponibles. Sur une machine à 8 coeurs, cela réduit typiquement le temps de résolution de 3 à 5x par rapport à la recherche mono-thread.

Exclure les absents de l'équité

Les employés en congé ou en vacances doivent être exclus des calculs d'équité intra-groupe. Sinon, le solveur se pénalise pour un écart qu'il ne peut pas combler, gaspillant de l'effort de recherche sur un objectif impossible.

Définir une limite de temps pertinente

Pour 100-150 employés, 5 minutes suffisent généralement. Pour 200-300+, accordez 15-30 minutes. Le comportement anytime de CP-SAT signifie qu'il a toujours une solution valide prête, même s'il est interrompu tôt. Une limite de temps plus longue produit un score marginalement meilleur, pas un planning fondamentalement différent.

Surveiller la décomposition de l'objectif

Quand le score total de pénalité est élevé, regardez la décomposition. Si 80% de la pénalité vient des manques de couverture, le problème est le sous-effectif, pas le tuning du solveur. Si les pénalités d'équité dominent, les groupes sont peut-être déséquilibrés. La structure de pénalité transforme le solveur en outil de diagnostic.