Résolution d'un problème de satisfaction de contraintes pour l'ordonnancement d'une chaîne d'assemblage automobile
Bibliographic record
Abstract
Plusieurs avenues existent dans la littérature pour la résolution des problèmes d'ordonnancement de la production. La complexité de ces problèmes rend nécessaire l'emploi de stratégies de recherche de solutions évoluées. Parmi celles-ci figurent leur modélisation sous la forme de problème de satisfaction de contraintes (CSP). Ce travail de recherche a pour but d'intégrer les formalismes des méthodes de résolution des CSP pour la résolution d'un problème d'ordonnancement de la production soit le problème de "carsequencing". Les travaux effectués s'inscrivent dans une optique d'exploration des algorithmes de résolution de CSP et de leur application aux problèmes d'ordonnancement de la production. \n \nDans un premier temps, les algorithmes de résolution de CSP existants sont étudiés et une comparaison entre ceux-ci est effectuée afin de déceler les avantages et les inconvénients de chacune des différentes méthodes de résolution suggérées dans la littérature. Entre autres, les algorithmes basés sur un principe de retour en arrière lors des situations d'inconsistance tels le BackTracking et le BackJumping sont étudiés. De plus, l'ajout d'heuristiques guidant la recherche de solutions ainsi que les méthodes d'apprentissage lors de la recherche sont exposées dans ce mémoire. Les algorithmes de diminution de domaines développés dans la littérature tels le Forward-Checking et les algorithmes de propagation de contraintes (AC) sont décrits et leurs implications sur la recherche sont quantifiées. Finalement, quelques méthodes de parallélisation de la recherche sont définies dans le cadre du présent travail de recherche. \n \nSuite à l'énumération des méthodes de résolution développées et à leur comparaison, ce travail de recherche couvre le développement d'un algorithme de résolution de CSP appliqué au problème de "car-sequencing". Premièrement, une étude de ce problème ainsi que des formulations possibles pour celui-ci est effectuée. Par la suite, le graphe de contraintes associé au problème de "car-sequencing" est défini et une stratégie de résolution du problème est décrite. Plus particulièrement, une méthode de diminution de l'espace de recherche de solutions possibles induit par les contraintes de ce problème est définie. L'algorithme de Forward-Checking est alors utilisé pour la résolution de ce problème particulier. De plus, une étude sur l'utilisation d'heuristiques guidant la recherche de solutions est effectuée. Finalement, une méthode de subdivision du problème initial en sous-problèmes indépendants a été développée afin de favoriser la diversification de la recherche de solutions lors d'une résolution concurrente. \n \nLes instances de problèmes suggérées dans la librairie de problèmes CSPLib sont utilisées comme base d'évaluation des méthodes développées. Les résultats obtenus dans le cadre de ce projet de recherche ont été comparés aux meilleurs résultats obtenus dans la littérature sur ces instances de problème. De plus, les résultats ont été comparés avec un outil de résolution commercial soit ILOG Solver 6.O. \n \nLes méthodes développées ont obtenu des résultats intéressants. En effet, pour un premier groupe de 70 instances du problème de "car-sequencing", le Forward-Checking développé a permis de surpasser les résultats obtenus par le solveur commercial ILOG Solver 6.O. Par contre, sur un deuxième groupe de problèmes, certaines bonifications des méthodes développées s'avèrent nécessaires. La diminution de l'espace de recherche représente une voie à explorer dans des recherches futures pour ainsi favoriser la résolution d'instances de problèmes non-satisfiables. \n
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
How this classification was reachedexpand
Full frame machine prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. The Gemma side is a direct model label for every work in the frame, read from the title-only record. The Codex side is a classifier learned from the 10,348 direct Codex labels and calibrated to design-weighted sample rates; fields without enough sample support carry no Codex call. Candidate is the union of the two sides; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels.
Distilled classifier scores by category (both heads)
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.001 | 0.003 |
| Meta-epidemiology (narrow) | 0.002 | 0.001 |
| Meta-epidemiology (broad) | 0.001 | 0.003 |
| Bibliometrics | 0.001 | 0.001 |
| Science and technology studies | 0.001 | 0.001 |
| Scholarly communication | 0.002 | 0.001 |
| Open science | 0.001 | 0.002 |
| Research integrity | 0.001 | 0.002 |
| Insufficient payload (model declined to judge) | 0.012 | 0.002 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from itClassification
machine, unvalidatedMachine predicted; a candidate call from one source (direct Gemma or distilled Codex), not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".