Single machine scheduling with chain structured precedence constraints and minimal and maximal separation times - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1994

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

Résumé

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.
Fichier principal
Vignette du fichier
RR-2268.pdf (652.07 Ko) Télécharger le fichier

Dates et versions

inria-00074403 , version 1 (24-05-2006)

Identifiants

  • HAL Id : inria-00074403 , version 1

Citer

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⟩
56 Consultations
45 Téléchargements

Partager

Gmail Facebook X LinkedIn More