Single machine scheduling with chain structured precedence constraints and minimal and maximal separation times

Abstract : We consider a single machine scheduling problem. This problem has been solved for a medical laboratory. It comprises not only chain-structured precedence constraints, but also minimal and maximal times separating successive jobs in the same chain. The criterion to be minimized is the makespan. This problem arises particularly in systems where chemical processes are involved. Consider a chemical plant in which every chemical process is a sequence of chemical reactions the duration of which is upper and lower bounded. Between two successive chemical reactions which are performed in different locations, a transportation system such as robot is used to carry the product from place to place. In this kind of plant, jobs are transportation operations and production processes can be modeled as chains. Therefore the problem studied in this paper is of practical importance. We first prove that the problem is NP-complete. As a consequence, we propose heuristics for large size problems and a branch and bound based algorithm for small size problems. Computational results are reported.
Type de document :
Rapport
[Research Report] RR-2268, INRIA. 1994, pp.16
Liste complète des métadonnées

https://hal.inria.fr/inria-00074403
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 15:14:06
Dernière modification le : samedi 17 septembre 2016 - 01:06:53
Document(s) archivé(s) le : mardi 12 avril 2011 - 16:52:01

Fichiers

Identifiants

  • HAL Id : inria-00074403, version 1

Collections

Citation

Chengbin Chu, Jean-Marie Proth. Single machine scheduling with chain structured precedence constraints and minimal and maximal separation times. [Research Report] RR-2268, INRIA. 1994, pp.16. 〈inria-00074403〉

Partager

Métriques

Consultations de la notice

81

Téléchargements de fichiers

53