Permutation Schedules Are Good For Realistic Flow Shop

Mikhail Y. Kovalyov Marie-Claude Portmann 1 Riad Aggoune 1
1 MACSI - Industrial system modeling, analysis and operation
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : It is well known that the permutation flow shop solutions are dominant subsets for problems with two machines to minimize any regular criterion and for problems with three machines to minimize the makespan. For m ³ 4, Potts et al. (1991) showed that the ratio (the best makespan for permutation solutions) / (the best makespan for general solutions) can increase to infinity with the number of jobs and the number of machines. Röck and Schmidt (1983) proved that this ratio is limited by half the number of machines. This work is an attempt to show that permutation solutions remain good when the shop satisfies some simple conditions which are natural and realistic for an industrial workshop. Some new results are proved for small particular cases.
Type de document :
Communication dans un congrès
International Conference on Industrial Engineering and Production Management - IEPM'2001, 2001, Quebec, Canada, 2, pp.1147-1155, 2001
Liste complète des métadonnées

https://hal.inria.fr/inria-00100515
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 14:46:23
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48

Identifiants

  • HAL Id : inria-00100515, version 1

Collections

Citation

Mikhail Y. Kovalyov, Marie-Claude Portmann, Riad Aggoune. Permutation Schedules Are Good For Realistic Flow Shop. International Conference on Industrial Engineering and Production Management - IEPM'2001, 2001, Quebec, Canada, 2, pp.1147-1155, 2001. 〈inria-00100515〉

Partager

Métriques

Consultations de la notice

127