Algorithmes

DispatchAtlas sépare le comportement des solveurs de la génération de benchmarks et de l'exécution de campagnes. Chaque solveur vit dans dispatchatlas.solve derrière un unique registre, et les métadonnées du solveur sont le contrat public pour les objectifs, capacités, encodages, dépendances, stochasticité, visibilité par niveau de preuve et backends optionnels. Cette page explique les familles de solveurs au niveau opérationnel ; la page du registre du système de solveurs est le catalogue faisant autorité par solveur.

🏗️ Comment les solveurs sont organisés

default_solver_registry() renvoie le registre des fabriques de solveurs sans état. Chaque entrée déclare des étiquettes de capacité, les objectifs pris en charge, les critères d'arrêt par défaut, un comportement de rejeu déterministe ou stochastique-avec-graine, un encodage de solution, des exigences de dépendances optionnelles, la visibilité par niveau de preuve, et une citation canonique (ou une justification explicite de citation-non-applicable). Les citations échouent en position fermée : une famille avec une origine fondatrice canonique qui omet sa référence ne peut pas être construite.

🧰 Familles de solveurs

📋 Règles de répartition constructive

Les lignes de base déterministes incluses sont des solveurs constructifs de list-scheduling : chacune contrôle l'ordre des tâches, et le constructeur en série honore les demandes de ressources déclarées de chaque tâche. Les sept familles — earliest-start, shortest-processing-time, longest-processing-time, earliest-deadline, earliest-finish-time, minimum-slack et greedy-completion — nomment chacune leur référence fondatrice canonique dans les métadonnées. Elles sont le chemin le plus rapide vers un ordonnancement faisable et ancrent toute comparaison, comme dans le premier tutoriel.

🔀 Lignes de base métaheuristiques

Cinq métaheuristiques avec graine représentatives — algorithme génétique, recuit simulé, colonie de fourmis, essaim de particules et évolution différentielle — partagent les mêmes opérateurs de faisabilité, réparation, scoring et recherche locale, de sorte qu'une comparaison mesure la stratégie de recherche plutôt que des différences de plomberie incidentes.

🔌 Solveurs à adaptateur encodé

L'essaim de particules à apprentissage compréhensif (clpso, d-clpso) et l'évolution différentielle adaptative par historique-de-succès (lshade, d-lshade) recherchent un vecteur continu à valeurs réelles avec un composant par tâche. Chaque cœur est générique sur un objectif continu et est lié à l'ordonnancement via un adaptateur d'encodage nommé (random-key, spv, rounding, et les décodages par fonction de transfert) qui transforme un vecteur en un ordre de tâches à précédence faisable, avec une politique de réparation explicite qui enregistre si la réparation s'est déclenchée.

🥊 Concurrents diversifiés et le couloir multi-objectif

Un ensemble curé de pairs publiés récents élargit la comparaison au-delà des lignes de base représentatives, chacun portant sa référence en texte intégral, ses forces et ses réserves dans les métadonnées. Un pair rejoint le champ public uniquement quand il franchit une barre de force-de-venue sourcée ; un pool plus large de lignes de base classiques reste enregistré pour la comparaison interne. nsga3 est le concurrent multi-objectif nommé : il évalue chaque ordre à précédence sûre sur un vecteur multi-objectif (makespan, retard, équité de charge) et sélectionne les survivants par nichage de point de référence.

🎯 Adaptateurs exacts

Les adaptateurs à backend optionnel (CP-SAT, MILP, branch-and-bound) déclarent une dépendance optionnelle et sondent sa racine d'import au runtime ; quand le backend est absent, ils soulèvent MissingOptionalDependencyError avec le nom de l'extra et la note de licence au lieu d'importer une dépendance lourde à l'import du paquet. Les adaptateurs natifs-bornés (exhaustive-enumeration et decision-diagram-sequencing) ne portent aucune dépendance tierce et résolvent exactement de petites instances, soulevant UnsupportedCapabilityError au-delà du nombre de tâches pris en charge. Le wrapper commercial Gurobi reste derrière l'extra exact-commercial et n'est jamais inclus ; un pool plus large de backends optionnels reste enregistré pour usage interne.

🐝 La famille NDSO

NDSO est la famille de solveurs à encodage natif du registre : elle recherche directement sur des ordonnancements faisables, de sorte que chaque ordonnancement qu'elle produit est faisable par construction et la famille n'exécute jamais d'étape d'encodage/décodage ni de passe de réparation. Elle compose un petit ensemble de mécanismes nommés :

• une Matrice de Confiance de confiance apprise par cellule (position, tâche), renforcée par de meilleurs ordonnancements ;
• un Vote Pondéré par la Confiance, qui synthétise l'ordonnancement élite en votant à travers la population pondérée par cette matrice ;
• des ordonnancements Quantité-et-Qualité qui fixent à quel point un candidat change et de quelle source de guidage il apprend ;
• un guidage à trois sources — l'élite synthétisée (exploitation), un pair (diversité), ou une source de connaissance disparue (exploration radicale) ;
• un coefficient adaptatif unifié, un unique calendrier non linéaire qui décale la famille de l'exploration vers l'exploitation.

Une carte d'ablation énumère une configuration isolante par mécanisme nommé afin que l'analyse en aval puisse attribuer la contribution de chaque mécanisme, et un filtre d'export par étapes échoue en position fermée plutôt que d'exposer un mécanisme de niveau ultérieur sous une portée de rapport inférieure. Le détail complet des mécanismes, du conseil, de l'ablation et des diagnostics vit dans le système de solveurs ; aucune affirmation de performance n'est faite avant que les campagnes comparatives ne s'exécutent.

🎛️ Sélection

SolverRegistry.select apparie les solveurs par étiquettes de capacité, contraintes déclarées, objectif pris en charge et visibilité par niveau de preuve — le registry.select(objective="makespan", disclosure_label=DisclosureLabel.CORE) du démarrage rapide est le plus petit exemple. Au-dessus du registre, la couche de sélection classe les solveurs pour un problème à partir de caractéristiques de caractérisation et de métadonnées publiques, étiquette chaque recommandation par sa source et sa confiance, et n'affirme jamais un solveur universellement meilleur. Le recommandateur de solveurs présente ces explications, y compris pourquoi un solveur a été exclu.