Shop scheduling in manufacturing systems: algorithms and complexity
Pourquoi ce travail est dans la base
Une base qui oublie comment elle a trouvé un travail ne peut pas être vérifiée. Voici les voies qui ont admis celui-ci.
Notice bibliographique
Résumé
This thesis describes efficient algorithms and complexity results for some machine scheduling and related problems, which are encountered in automated manufacturing systems. We introduce a new class of robotic-cell scheduling models. The novel aspect is that parts need to reenter machines several times before they are finished. The problem is to find the sequence of robot move cycles and the part processing sequence that jointly minimize the cycle time or the makespan. We show that the problems are computationally intractable with three machines and present polynomial solutions for a variety of two-machine configurations. We then consider the problem of scheduling multi-component parts in a two-machine robotic cell, where each part is composed of K identical components to be processed together on the first machine, then processed on the second machine individually. We study the cycle time and makespan minimization problems, and show that both are polynomially solvable. We investigate the problem of minimizing cycle time in a two-machine job shop, where each job has at most three operations. We reduce the problem to a two-machine reentrant flow shop problem. By extending previous results on the reentrant flow shop problem, we propose a new pseudo-polynomial algorithm, as well as a fully polynomial-time approximation scheme for certain special cases of the job shop problem. We also describe a 4/3-approximation algorithm for the general problem, and identify several well-solvable cases. Finally, we study special cases of the traveling salesman problem on permuted Monge matrices, which arose from robotic-cell scheduling problems. By using the theory of subtour patching, we reduce the problems to finding a minimum-b-weight spanning tree in the patching graph. In general, this problem is NP -hard. We show, however, that newly defined special properties of the distance matrix allow us to find in polynomial time a minimum-b-weight spanning tree, and thus an optimal tour, for these new classes.
Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.
Prédiction distillée sur la base complète
Imitation des enseignantsNi prévalence calibrée, ni vérité terrain. Validation humaine à venir. Apprise à partir de 10 348 étiquettes directes de Codex et de 10 348 étiquettes directes de Gemma. Le mode candidate est l'union des têtes enseignantes seuillées; le consensus est leur intersection. Ces sorties portent le statut machine_predicted_unvalidated et ne sont ni des étiquettes humaines ni des étiquettes directes de modèles de pointe.
Scores Codex et Gemma par catégorie
| Catégorie | Codex | Gemma |
|---|---|---|
| Métarecherche | 0,000 | 0,000 |
| Méta-épidémiologie (sens strict) | 0,000 | 0,000 |
| Méta-épidémiologie (sens large) | 0,000 | 0,000 |
| Bibliométrie | 0,000 | 0,000 |
| Études des sciences et des technologies | 0,000 | 0,000 |
| Communication savante | 0,000 | 0,000 |
| Science ouverte | 0,000 | 0,000 |
| Intégrité de la recherche | 0,000 | 0,000 |
| Charge utile insuffisante (le modèle a refusé de juger) | 0,000 | 0,000 |
Scores machine (provisoires)
Les deux têtes enseignantes du modèle étudiant, lues sur ce travail. Un score ordonne la base pour la relecture; il n'affirme jamais une catégorie, et le statut de validation accompagne chaque rangée tel quel.
Scores de référence d'un modèle non mature (critères de maturité non atteints, 7 itérations). Un score ordonne; il n'affirme jamais une catégorie.
score_only:v0-immature-baseline · tel quel depuis la passe de notation : score_only signifie que le nombre peut ordonner les travaux, et qu'aucune étiquette de catégorie n'en découle