Scheduling and Controlling Work-in-Process : An on Line Study for Shop Problems

Abstract : In this paper, we address the problem of production systems having two characteristics. First, the manufacturing times can be chosen between given bounds. Such a production system is said to have controllable processing times. Second, an operation must start as soon as the previous operation on the same part (if any) is completed. A production system having this characteristic is said to be no-wait. Several on-line schedules are considered to minimize the makespan in flow shop and job shop situations. We prove that in the worst case, the makespan provided by these schedules is m times longer than the optimal one (for different flow shops and job shops), m being the number of machines. We give several related results on competitive ratio.
Type de document :
Rapport
[Research Report] RR-3950, INRIA. 2000, pp.15
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00072699
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 10:37:39
Dernière modification le : samedi 17 septembre 2016 - 01:06:55
Document(s) archivé(s) le : jeudi 24 mars 2011 - 12:04:17

Fichiers

Identifiants

  • HAL Id : inria-00072699, version 1

Collections

Citation

Fabrice Chauvet, Jean-Marie Proth. Scheduling and Controlling Work-in-Process : An on Line Study for Shop Problems. [Research Report] RR-3950, INRIA. 2000, pp.15. 〈inria-00072699〉

Partager

Métriques

Consultations de la notice

77

Téléchargements de fichiers

158