Le problème d'horaire médical est un problème de recherche opérationnelle.

Le problème a un nom, et cinquante ans de littérature

Une gestionnaire de GMF qui cherche de l'aide tape « logiciel d'horaire clinique » et tombe sur des pages de vente. La même question posée avec le vocabulaire de la recherche opérationnelle ouvre une bibliothèque entière, parce que le problème est étudié formellement depuis les années 1970.

Pour le personnel soignant, on parle du nurse rostering problem, en français le problème de confection d'horaires infirmiers. La revue de référence reste « The state of the art of nurse rostering », signée par Burke et ses collègues dans le Journal of Scheduling en 2004. Pour les médecins, le terme est physician scheduling problem, et la synthèse la plus utile est « State of the art in physician scheduling », parue dans l'European Journal of Operational Research en 2018. Elle sépare le domaine en trois familles : la dotation, qui décide combien de personnes il faut, la confection de l'horaire proprement dite, et la replanification, qui traite ce qui arrive après la publication.

Cette troisième famille est celle que les équipes sous-estiment le plus, et la littérature lui donne un nom précis justement parce qu'elle se comporte différemment des deux autres.

Le sujet a aussi une histoire québécoise. Francis Forget a déposé en 2002 à l'Université de Montréal un mémoire de maîtrise intitulé « Confection automatisée des horaires de médecins dans une salle d'urgence », dirigé par Jacques Ferland et Bernard Gendron, qui traite le problème par programmation en nombres entiers. Montréal est un des centres mondiaux de la discipline depuis longtemps, à travers le GERAD et le CIRRELT, et la génération de colonnes, méthode centrale pour la confection d'horaires d'équipages, y a été développée en bonne partie. L'ouvrage de référence sur cette méthode est signé par Guy Desaulniers, Jacques Desrosiers et Marius M. Solomon chez Springer en 2005.

Ce qui rend le problème difficile, précisément

Even, Itai et Shamir ont publié en 1976, dans SIAM Journal on Computing, un article intitulé « On the Complexity of Timetable and Multicommodity Flow Problems ». Leur résultat tient en une phrase : une version très primitive du problème d'horaire de Gotlieb est NP-complète, donc tous les problèmes d'horaire courants le sont. Aucun algorithme connu ne garantit la solution optimale en temps raisonnable pour toutes les instances possibles.

La taille de l'espace de recherche donne une idée de l'ordre de grandeur. Répartir une seule garde par jour entre 12 médecins sur 28 jours produit 12 puissance 28 affectations possibles, soit environ 1 648 000 milliards de milliards de milliards de grilles, avant d'avoir écrit la moindre règle. Aucune énumération n'en viendra à bout, et c'est pour cette raison qu'un chiffrier ne peut pas optimiser : il peut vérifier une grille, jamais la chercher.

Ce chiffre impressionne mais il induit en erreur si on s'arrête là. Un solveur moderne ne parcourt pas cet espace, il l'élague, et les instances réelles d'un GMF se règlent en fractions de seconde. La difficulté pratique vient d'ailleurs, elle vient des contraintes qui se contredisent entre elles. Nos 27 contraintes réelles d'un horaire de GMF détaillent lesquelles. Une contrainte seule ne coûte rien. Deux contraintes qui s'excluent coûtent une soirée.

Les trois familles de méthodes

La programmation linéaire en nombres entiers écrit le problème comme un système d'inégalités et confie le tout à un solveur comme CBC, HiGHS ou Gurobi. C'est l'approche du mémoire de 2002 cité plus haut, et elle reste la plus efficace quand le modèle s'exprime naturellement en sommes et en bornes, notamment pour les questions de dotation.

La programmation par contraintes prend le problème par l'autre bout. Vous déclarez des variables, leurs domaines et des relations entre elles, et le solveur propage : dès que MD-03 prend la garde du samedi, toutes les affectations incompatibles disparaissent des domaines des autres variables. Les règles de séquence, du type « jamais deux gardes consécutives » ou « pas plus d'une fin de semaine sur trois », s'écrivent en une ligne, alors qu'elles demandent un détour en programmation linéaire.

Les métaheuristiques, recuit simulé, recherche tabou, algorithmes génétiques, explorent l'espace par essais successifs guidés. Elles servent quand le modèle devient trop gros pour une méthode exacte, et elles abandonnent en échange la garantie d'optimalité. Pour une équipe médicale de moins de cent personnes, cette garantie reste accessible, alors commencez par une méthode exacte.

Le point d'entrée le plus raisonnable aujourd'hui est CP-SAT, le solveur de programmation par contraintes de la trousse OR-Tools de Google. Il est gratuit, sous licence Apache 2.0, installable par une seule commande pip, et il a remporté l'or dans les catégories Fixed, Free et Parallel du MiniZinc Challenge 2025, la compétition internationale de référence du domaine.

Un modèle de garde complet, en quarante lignes

Voici une rotation de garde réelle, réduite à sa plus simple expression : 12 médecins, 28 jours, une garde par jour, jamais deux jours de suite, des indisponibilités déclarées, et une équité qui pèse une journée de fin de semaine trois fois une journée de semaine. Le code s'exécute tel quel après un pip install ortools.

from ortools.sat.python import cp_model

MEDECINS = [f"MD-{i:02d}" for i in range(1, 13)]
JOURS = range(28)                                        # 4 semaines, jour 0 = lundi
POIDS = [3 if j % 7 in (5, 6) else 1 for j in JOURS]     # fin de semaine 3, semaine 1
INDISPO = {"MD-03": {5, 6, 12, 13}, "MD-07": {7, 8, 9, 10, 11}}

m = cp_model.CpModel()
g = {(md, j): m.new_bool_var(f"{md}_{j}") for md in MEDECINS for j in JOURS}

for j in JOURS:
    m.add_exactly_one(g[md, j] for md in MEDECINS)       # une garde couverte par jour
for md in MEDECINS:
    for j in list(JOURS)[:-1]:
        m.add(g[md, j] + g[md, j + 1] <= 1)              # jamais deux jours de suite
    for j in INDISPO.get(md, set()):
        m.add(g[md, j] == 0)                             # indisponibilités déclarées

charge = {}
for md in MEDECINS:
    charge[md] = m.new_int_var(0, sum(POIDS), f"charge_{md}")
    m.add(charge[md] == sum(POIDS[j] * g[md, j] for j in JOURS))
haut = m.new_int_var(0, sum(POIDS), "haut")
bas = m.new_int_var(0, sum(POIDS), "bas")
m.add_max_equality(haut, charge.values())
m.add_min_equality(bas, charge.values())
m.minimize(haut - bas)                                   # équité pondérée

s = cp_model.CpSolver()
s.parameters.max_time_in_seconds = 10.0
s.parameters.num_workers = 1                             # résultat reproductible
s.parameters.random_seed = 42
etat = s.solve(m)

if etat not in (cp_model.OPTIMAL, cp_model.FEASIBLE):    # la ligne qu'on oublie
    raise SystemExit(f"aucun horaire ne respecte ces règles ({s.status_name(etat)})")

print(s.status_name(etat), "écart de charge", s.value(haut) - s.value(bas))
for md in MEDECINS:
    jours = [j for j in JOURS if s.boolean_value(g[md, j])]
    print(md, "charge", s.value(charge[md]), "gardes", len(jours), jours)

Ce que le solveur répond

Avec OR-Tools 9.15, ce modèle retourne le statut OPTIMAL en environ 0,015 seconde, avec un écart de charge de 1. La charge totale de la période vaut 44 points, soit 20 journées de semaine à 1 point et 8 journées de fin de semaine à 3 points, ce qui donne une moyenne de 3,67 points par médecin. Le solveur répartit ces points entre 3 et 4 par personne, et il est impossible de faire mieux.

Voici les quatre premières lignes de la sortie, telles quelles.

OPTIMAL écart de charge 1
MD-01 charge 4 gardes 2 [4, 27]
MD-02 charge 4 gardes 4 [0, 3, 18, 24]
MD-03 charge 4 gardes 4 [9, 11, 15, 17]
MD-04 charge 3 gardes 1 [19]

Le piège que cette sortie contient

Regardez la colonne du nombre de gardes. MD-02 et MD-03 en prennent quatre, MD-04 n'en prend qu'une. L'équité pondérée est parfaite et la répartition du nombre de gardes est absurde, parce que quatre gardes de semaine valent le même total que deux gardes touchant une fin de semaine.

Le solveur a fait exactement ce qu'on lui a demandé. La règle qui manque n'a jamais été écrite, parce que personne ne pense à formuler une évidence. Aucun médecin du groupe n'accepterait de faire quatre gardes pendant qu'un collègue en fait une, quel que soit le calcul de points qu'on lui présente. Deux lignes suffisent à corriger le modèle, à insérer avant le bloc de charge.

for md in MEDECINS:
    m.add(sum(g[md, j] for j in JOURS) >= 2)
    m.add(sum(g[md, j] for j in JOURS) <= 3)

Le solveur retourne alors OPTIMAL avec le même écart de charge de 1, mais chaque médecin porte deux ou trois gardes. Rien n'a été perdu, il fallait seulement le dire. C'est la partie du travail qui prend des mois, et elle se passe loin du clavier. Elle demande de découvrir, une par une, les règles que l'équipe applique sans les avoir jamais énoncées.

Le même modèle donne cinq horaires différents

Nous avons lancé cinq fois la version multifil du modèle, sans rien changer au code ni aux données. Elle a produit cinq horaires différents, tous optimaux, tous avec un écart de charge de 1. Le solveur cherche en parallèle sur plusieurs fils d'exécution, et la première solution optimale qui remonte dépend de l'ordonnancement du système.

Les contraintes et l'objectif ne désignent pas une grille unique, ils désignent une famille de grilles équivalentes. Pour une gestionnaire, la conséquence est concrète : elle corrige une indisponibilité, relance la génération, et tout l'horaire a bougé, y compris les affectations qu'elle avait validées. Les deux lignes num_workers = 1 et random_seed = 42 du code ci-dessus rendent le résultat reproductible, ce que nos cinq exécutions ont confirmé en donnant une sortie identique. Un outil de production a besoin de bien plus, il a besoin de conserver les affectations déjà acceptées et de ne rouvrir que le reste.

Quand aucun horaire n'existe

Remplacez la borne supérieure de 3 gardes par 2 et le problème devient impossible : 12 médecins à 2 gardes chacun couvrent 24 jours, pas 28. Le solveur retourne INFEASIBLE en 0,010 seconde.

Il ne lève aucune exception. C'est le comportement qui coûte le plus cher dans un premier moteur maison, parce que le programme continue. Nous avons retiré la vérification du statut pour voir ce que ça donne, et le code a imprimé une grille complète où un médecin portait 12 gardes dont plusieurs jours consécutifs et où neuf médecins n'en portaient aucune, en violation directe des règles du modèle. Rien dans la sortie n'annonçait un problème.

Un horaire faux d'apparence normale est pire qu'une erreur visible, et c'est le même mécanisme que nous avons documenté en demandant à ChatGPT de bâtir l'horaire d'un GMF : la grille a la même allure, qu'elle soit juste ou non. Vérifiez le statut avant toute lecture de la solution. Sans cette ligne, rien de ce que le modèle produit ne tient debout.

Ce qui sépare ce modèle d'un outil de production

Le modèle ci-dessus tient en quarante lignes et traite un seul type d'affectation. Un horaire de GMF en superpose au moins trois, la garde, la plage de sans rendez-vous et le bureau partagé, et ces trois dimensions interagissent : un médecin affecté à une plage sans local disponible produit un horaire imaginaire.

Il traite ensuite toutes les règles comme absolues. Un horaire réel distingue les règles dures, celles qui ne se négocient jamais, des règles souples qu'on préfère respecter mais qu'on relâche quand il le faut. Cette distinction se modélise avec des variables d'écart pénalisées dans l'objectif, et elle double la taille du modèle et de la conversation avec l'équipe.

Il ne sait pas dire pourquoi il échoue. INFEASIBLE est un statut, et une gestionnaire a besoin de savoir quelles règles se contredisent. CP-SAT peut désigner les règles responsables, mais seulement si chaque règle relâchable a été rattachée à une hypothèse déclarée avant la résolution. Sans cette préparation, la seule réponse disponible est qu'il n'existe pas de solution.

Enfin, il ignore ce qui arrive après la publication, ce que la littérature appelle la replanification. Un retrait le vendredi après-midi ne se traite pas en relançant la génération complète, il se traite en modifiant le minimum autour du trou, en prévenant les bonnes personnes et en gardant la trace de qui a accepté quoi. C'est là que se trouve la majeure partie des heures de gestion, et le modèle ci-dessus n'en couvre rien.

S'ajoutent les parties qui ne relèvent pas de l'optimisation : une interface qu'un médecin ouvre trois minutes par mois sur son téléphone, l'authentification, les journaux, les sauvegardes, et les obligations qui suivent des renseignements personnels comme les absences et les disponibilités. Notre comparatif entre Synchro et une solution maison chiffre ces postes, avec les cas où bâtir demeure le bon choix.

Par où commencer si vous bâtissez

1. Écrivez vos règles avant votre code. Numérotez-les, et notez pour chacune si elle est absolue ou négociable. C'est le livrable le plus utile du projet, et il sert même si vous achetez ensuite.
2. Reprenez le modèle de cet article avec vos vraies données. Une période déjà publiée, dont vous connaissez la bonne réponse, vous dira en une soirée si votre formulation tient.
3. Cherchez ce que le solveur a le droit de faire et que vous n'accepteriez pas. C'est ainsi qu'on trouve les règles jamais écrites, comme celle du nombre de gardes plus haut.
4. Rendez le résultat reproductible dès le premier jour, puis conservez les affectations déjà acceptées d'une génération à l'autre.
5. Traitez la replanification comme un projet distinct, parce qu'elle pèse plus lourd que la génération initiale et qu'elle ne se résout pas avec le même outil.

Où Synchro intervient

Synchro utilise CP-SAT d'OR-Tools pour l'attribution des bureaux et des activités, sur le même principe que le modèle publié ici, avec les trois dimensions superposées et la distinction entre règles dures et règles souples. Chaque médecin déclare ses contraintes en français, la liste de garde se pondère au lieu de se compter, et un quart libéré se reprend en libre-service plutôt que par une chaîne d'appels. Le prix est affiché, 10 $ CAD par utilisateur par mois en facturation annuelle.

Ce que Synchro ne fait pas, à ce jour. La plateforme ne contient aucune donnée de patient et ne remplace pas votre DME. Elle ne produit pas votre liste d'AMP et ne calcule pas votre taux d'assiduité. Si votre besoin se limite à une rotation de garde dans une petite équipe stable, un chiffrier bien tenu vous mènera plus loin qu'un abonnement.

Pour aller plus loin

• Les 27 contraintes réelles d'un horaire de GMF
• Synchro et une solution maison : bâtir ou acheter
• J'ai demandé à ChatGPT de bâtir l'horaire de mon GMF
• Airtable, Notion et le no-code pour l'horaire d'une clinique
• Logiciel d'horaire pour GMF, le guide complet