| Issue |
RAIRO-Oper. Res.
Volume 33, Number 4, October-December 1999
|
|
|---|---|---|
| Page(s) | 439 - 445 | |
| DOI | https://doi.org/10.1051/ro:1999120 | |
| Published online | 15 August 2002 | |
Optimal scheduling of the 3-machine assembly-type flow shop
1
Ecole Polytechnique de Tunisie,
BP. 743, 2078 La Marsa, Tunisia.
2
Institut des Hautes Etudes Commerciales,
2016 Carthage-Presidence, Tunisia.
We address the 3-Machine Assembly-Type Flowshop Scheduling Problem (3MAF). This problem is known to be NP-complete in the strong sense. We propose an exact branch and bound method based on a recursive enumeration of potential inputs and outputs of the machines. Using this algorithm, several large size instances have been solved to optimality.
Résumé
Nous nous interessons au probleme d'ordonnancement de 3 machines dans un atelier d'assemblage de type flowshop. Ce probleme est connu comme etant NP-complet au sens fort. Nous proposons un algorithme exact de separation et evaluation progressives, base sur une enumeration recursive des entrees et des sorties potentielles des machines. Des problemes de grande taille ont ete resolus d'une maniere optimale. À notre connaissance, il s'agit de la premiere fois, ou ce probleme est resolu exactement.
Key words: Scheduling / flow shop / branch and bound / assembly-type production.
© EDP Sciences, 1999
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.