Skip to Main content Skip to Navigation
Reports

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.
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00074403
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 3:14:06 PM
Last modification on : Saturday, September 17, 2016 - 1:06:53 AM
Long-term archiving on: : Tuesday, April 12, 2011 - 4:52:01 PM

Identifiers

  • 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⟩

Share

Metrics

Record views

111

Files downloads

74