💻 computer science

PyCSP3-Scheduling: A Scheduling Extension for PyCSP3

Cet article présente PyCSP3-Scheduling, une bibliothèque qui étend le cadre PyCSP3 avec des abstractions natives de planification telles que les variables d'intervalle et de séquence, lesquelles se transforment en contraintes standard pour préserver la séparation entre modélisation et solveur tout en démontrant des résultats de performance mixtes, avec des accélérations significatives sur certaines familles de problèmes et des régressions induites par la surcharge sur d'autres.

Auteurs originaux : Sohaib Afifi

Publié 2026-05-15

📖 4 min de lecture☕ Lecture pause café

CC BY 4.0

Auteurs originaux : Sohaib Afifi

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous êtes un chef étoilé tentant d'organiser un banquet massif et complexe. Vous avez des dizaines de plats à cuisiner, des cuisinières limitées, des temps de cuisson spécifiques et des règles strictes concernant l'ordre dans lequel les plats doivent être prêts avant qu'un autre puisse être servi.

Le Problème : La Cuisine « Manuelle »
Actuellement, si vous souhaitez utiliser le logiciel populaire « PyCSP3 » (un outil puissant pour résoudre des énigmes logiques complexes), vous devez décrire votre cuisine en termes très basiques. Vous devez lister manuellement chaque marmite, chaque seconde de temps de cuisson, et rédiger de longues et fastidieuses règles telles que : « Si la Marmite A est sur la cuisinière, la Marmite B ne peut pas être sur la cuisinière sauf si la Marmite A est terminée. »

Vous devez construire l'ensemble du planning à partir de zéro, brique par brique, en utilisant des mathématiques élémentaires. Cela fonctionne, mais c'est comme essayer d'écrire un roman en utilisant uniquement des lettres individuelles, sans aucun mot ni règles de grammaire. Il est facile de faire une erreur, et les instructions deviennent un mur de texte désordonné, difficile à lire ou à modifier.

La Solution : PyCSP3-Scheduling
Cet article présente un nouvel « assistant de cuisine » appelé PyCSP3-Scheduling. Au lieu de vous obliger à rédiger chaque règle concernant les marmites et les minuteries, cet outil vous fournit des « ingrédients intelligents » de haut niveau :

Variables d'Intervalle (La « Marmite Intelligente ») : Au lieu d'un simple nombre pour le temps, vous obtenez un objet « Marmite » qui connaît sa propre heure de début, son heure de fin et la durée nécessaire pour sa cuisson. Il sait même s'il est optionnel (peut-être n'avez-vous pas besoin de cuisiner ce plat aujourd'hui).
Variables de Séquence (Le « Convoyeur ») : Vous pouvez regrouper les marmites en une ligne. L'outil sait automatiquement que si la Marmite A est sur le convoyeur, la Marmite B ne peut pas s'y trouver en même temps. Il gère même automatiquement les « temps de préparation » (comme laver la marmite entre les plats).
Le Traducteur : La meilleure partie est que cet assistant ne tente pas de remplacer le chef (le solveur). Il prend vos instructions de haut niveau, faciles à lire, et les traduit en mathématiques basiques et désordonnées que l'ordinateur comprend parfaitement.

L'Expérience : Est-ce que cela a fonctionné ?
L'auteur a testé cet nouvel outil sur 261 « recettes » différentes (problèmes de planification), allant de simples ateliers d'usinage à des affectations de personnel hospitalier complexes et à la planification de tournois. Ils ont comparé la méthode « Manuelle » à la méthode « Assistant Intelligent ».

Voici ce qu'ils ont constaté :

Les Résultats sont Identiques : Lorsque l'ordinateur résout parfaitement le problème, les deux méthodes obtiennent exactement la même réponse. La traduction était précise à 100 %.
La Vitesse est Mitigée :
- Les Victoires : Pour certains problèmes (comme la planification des atterrissages d'avions ou des répétitions théâtrales), le nouvel outil était jusqu'à 5,8 fois plus rapide. C'était comme passer d'un vélo à une voiture de sport.
- Les Perte : Pour d'autres problèmes (comme certains types de fabrication ou d'ateliers d'usinage flexibles), le nouvel outil était en réalité plus lent.
- Pourquoi ? L'auteur explique que parfois, le processus de « traduction » ajoute trop de bagage supplémentaire. Par exemple, si un problème implique des tâches « optionnelles », l'outil doit parfois rédiger des milliers de règles supplémentaires « si/alors » pour couvrir chaque possibilité, ce qui ralentit l'ordinateur. C'est comme faire une valise avec des couches supplémentaires de film plastique juste pour être sûr ; cela protège les objets, mais rend la valise lourde.

La Conclusion
PyCSP3-Scheduling est un pont. Il permet aux humains d'écrire des modèles de planification de manière naturelle et logique (en utilisant des « Intervalle » et des « Séquences ») sans rompre le lien avec les solveurs puissants qui effectuent le gros du travail.

C'est Open Source : N'importe qui peut l'utiliser gratuitement.
C'est Sûr : Il ne vous enferme pas dans un programme informatique spécifique ; il traduit votre modèle dans un format standard que n'importe quel solveur compatible peut lire.
Ce n'est pas une Solution Magique : Bien qu'il rende la modélisation beaucoup plus facile et rapide pour certains problèmes, il ne rend pas automatiquement tous les problèmes plus rapides. Dans certains cas, les étapes supplémentaires de « traduction » ajoutent une légère surcharge.

En bref, cet outil rend le travail du « chef » (le modélisateur) beaucoup plus facile et moins sujet aux erreurs, même si la « cuisine » (le solveur informatique) prend parfois quelques étapes supplémentaires pour traiter les nouvelles instructions.

Résumé Technique : PyCSP3-Scheduling

Énoncé du Problème

Bien que PyCSP3 offre un environnement productif pour la modélisation de problèmes combinatoires et leur exportation vers le standard XCSP3, il manque de support natif pour des abstractions de planification de haut niveau. Actuellement, les modélisateurs doivent encoder les problèmes de planification en utilisant des variables entières de bas niveau (dates de début, durées) et construire manuellement des contraintes d'ordre arithmétique et des disjonctions pour les conflits de ressources. Bien que PyCSP3 fournisse des contraintes globales comme NoOverlap et Cumulative sur des tableaux d'entiers, le modélisateur doit gérer explicitement des tableaux de dates de début, des listes de durées et des hauteurs de ressources. Cette approche obscurcit la structure inhérente de la planification, complique l'ajout de fonctionnalités telles que l'optionnalité (tâches qui peuvent ou non se produire) ou des temps de préparation dépendants de la séquence, et nécessite de reconstruire les encodages à partir de zéro pour de nouveaux modèles. Les outils industriels existants (par exemple, CP Optimizer) offrent des objets de planification mais couplent souvent les modèles à des solveurs spécifiques, parfois commerciaux, tandis que des langages autonomes comme MiniZinc manquent de types de variables d'intervalle de première classe.

Méthodologie

L'article présente PyCSP3-Scheduling, une bibliothèque qui étend PyCSP3 avec une couche dédiée à la planification. La méthodologie centrale comprend :

Couche d'Abstraction : La bibliothèque introduit deux types de variables principaux :
- IntervalVar : Représente une tâche avec des attributs pour le début, la fin, la taille (durée) et la présence. Elle prend en charge cinq variantes : Fixe, Flexible, Optionnelle, Bornée et Mise à l'échelle (couplant la durée à des profils d'intensité).
- SequenceVar : Regroupe une liste de variables d'intervalle en une séquence ordonnée, représentant typiquement une ressource disjonctive (par exemple, une machine), et prend en charge des temps de transition dépendants du type.
Schéma de Compilation : La bibliothèque n'introduit pas un nouveau backend de solveur. Au lieu de cela, elle compile ces abstractions de haut niveau vers des variables et contraintes standard de PyCSP3, qui sont ensuite exportées sous forme d'instances XCSP3 standard.
- Mappage Direct : Lorsque les motifs correspondent à des contraintes globales existantes (par exemple, des intervalles obligatoires sans transitions), la bibliothèque émet des globaux XCSP3 standards tels que noOverlap et Cumulative.
- Décomposition : Pour les cas complexes (par exemple, des intervalles optionnels avec des gardes de présence ou des préparations dépendantes de la séquence), la bibliothèque décompose les abstractions en contraintes primitives. Par exemple, SeqNoOverlap avec des intervalles optionnels revient à des disjonctions par paires de complexité $O(n^2)$ gardées par des littéraux de présence, car le standard XCSP3 actuel ne prend pas en charge les intervalles optionnels dans les contraintes globales.
- Modélisation Hybride : La couche est intégrée dans PyCSP3, permettant aux modélisateurs de mélanger des constructions de planification de haut niveau avec des contraintes brutes de PyCSP3 (par exemple, utiliser presence_of pour déclencher une logique de comptage personnalisée).
Système d'Expressions : La bibliothèque fournit des accesseurs (start_of, end_of, presence_of, etc.) qui retournent des expressions PyCSP3, permettant des combinaisons arithmétiques et logiques complexes directement sur les attributs des intervalles.

Contributions Clés

L'article apporte trois contributions spécifiques :

Une API de Planification : Une API complète pour PyCSP3 centrée sur les abstractions d'intervalle et de séquence, prenant en charge l'optionnalité, les fonctions d'intensité et le séquencement conscient des transitions.
Un Schéma de Compilation : Un mécanisme qui abaisse ces abstractions vers des contraintes PyCSP3/XCSP3 indépendantes du solveur tout en préservant la satisfiabilité et l'optimalité.
Évaluation Empirique : Une comparaison rigoureuse de 261 instances appariées (formulation PyCSP3 classique vs formulation de planification) à travers 17 familles de modèles.

Résultats

L'évaluation a été menée sur 261 instances appariées en utilisant le solveur ACE avec un délai d'attente de 1200 secondes. Les principales conclusions incluent :

Correction Sémantique : Sur les 72 instances où les deux formulations ont prouvé l'optimalité, les valeurs objectives correspondaient exactement (100 %), confirmant que la compilation n'introduit aucune divergence sémantique.
Accord sur l'État du Solveur : Les deux formulations étaient d'accord sur l'état du solveur (Optimum, Sat, Unsat, Timeout) dans 80,8 % des paires. Les désaccords étaient principalement dus à des différences de progression de recherche liées au délai d'attente plutôt qu'à des erreurs logiques.
Variance de Performance : La performance d'exécution variait considérablement selon les familles :
- Gains : Trois familles ont montré des accélérations claires : MSPSP (5,82×), AircraftLanding (3,47×) et Rehearsal (3,31×). Le gain de MSPSP a été attribué à des artefacts de l'ordre des variables dans la déclaration des variables PyCSP3 plutôt qu'aux abstractions elles-mêmes, tandis que AircraftLanding et Rehearsal ont bénéficié d'une réduction de la taille du modèle et d'une meilleure capture structurelle.
- Régressions : Trois familles ont régressé : LotSizing (0,29×), MRCPSP (0,61×) et FlexibleJobshopScen (0,89×).
  - La régression de MRCPSP a été attribuée à la compilation des intervalles optionnels retournant à des disjonctions par paires au lieu d'émettre une contrainte globale noOverlap, empêchant une propagation efficace.
  - La régression de LotSizing était liée à des problèmes d'encodage au niveau des contraintes et à la force de propagation sous délai d'attente.
  - FlexibleJobshopScen a souffert d'une augmentation structurelle significative (explosion des variables et des contraintes) due à la duplication des décisions optionnelles à travers les scénarios.
Impact Structurel : 8 des 17 familles ont montré une augmentation structurelle négligeable (< 1 % de changement). Pour les autres, la formulation de planification a parfois réduit la taille du modèle (par exemple, BACP, Rehearsal) et parfois l'a augmentée de manière significative (par exemple, FlexibleJobshopScen +383,7 % de contraintes).

Importance et Affirmations

L'article positionne PyCSP3-Scheduling comme la première couche de planification à fournir des abstractions de variables d'intervalle (IntervalVar) et de séquence (SequenceVar) de première classe avec optionnalité et séquencement conscient des transitions, tout en compilant vers un standard indépendant du solveur (XCSP3).

Les auteurs soulignent que la bibliothèque préserve la séparation complète entre la modélisation et la résolution, un principe fondamental de l'écosystème PyCSP3. Cela permet aux modèles de rester utilisables avec un large éventail de solveurs (ACE, Choco, CoSoCo, OR-Tools, CP Optimizer, etc.) sans modification.

L'article est modeste concernant les affirmations de performance, notant que les gains de temps d'exécution ne sont pas universels et sont souvent liés à des structures de problèmes spécifiques ou à des heuristiques de solveur (par exemple, l'ordre des variables). Les auteurs déclarent explicitement que l'accélération significative de MSPSP est probablement un artefact des motifs de déclaration de variables plutôt que des abstractions de planification elles-mêmes. La principale proposition de valeur est l'expressivité et la maintenabilité de la formulation de planification, qui réduit la complexité du code (par exemple, une réduction de 31 % du nombre de lignes pour un modèle d'atelier flexible) et simplifie l'ajout de fonctionnalités telles que l'optionnalité, même si cela entraîne occasionnellement une surcharge de compilation qui affecte les performances d'exécution sur des familles de problèmes spécifiques.

Les travaux futurs sont identifiés comme l'extension de la compilation pour émettre des contraintes globales XCSP3 avec un support d'optionnalité (pour éviter la décomposition par paires) et le raffinement des règles de compilation afin de réduire la surcharge structurelle dans les familles aberrantes.