Title :
Sequencing with chain structured precedence constraints and minimal and maximal separation times
Author :
Chu, Chengbin ; Jean-Marie Proth
Author_Institution :
Projet SAGEP, Inst. Nat. de Recherche en Inf. et Autom.-Lorraine, Metz, France
Abstract :
Considers a single machine scheduling problem which has been solved for a medical laboratory. In this problem, there are not only chain structured precedence constraints, but also minimal and maximal times separating successive jobs in a same chain. The criterion to be minimized is the makespan. This problem arises particularly in systems where chemical processes are involved. In these systems, jobs are transportation operations and chemical processes can be modeled as chains. Therefore the problem studied in this paper is of practical importance. The authors first state that the problem is NP-complete. As a consequence, the authors propose heuristics for large size problems and a branch and bound algorithm for small size problems. Computational results are reported
Keywords :
laboratories; minimisation; scheduling; NP-complete; branch and bound algorithm; chain structured precedence constraints; chemical processes; heuristics; makespan minimisation; medical laboratory; separation times; sequencing; single machine scheduling; transportation operations; Chemical processes; Chemical products; Educational institutions; Job production systems; Laboratories; Road transportation; Scheduling algorithm; Single machine scheduling; Tires;
Conference_Titel :
Computer Integrated Manufacturing and Automation Technology, 1994., Proceedings of the Fourth International Conference on
Conference_Location :
Troy, NY
Print_ISBN :
0-8186-6510-6
DOI :
10.1109/CIMAT.1994.389052