Skip to Main content Skip to Navigation
Conference papers

Cyclic hoist scheduling based on graph theory

Abstract : In this paper, we consider a cyclic hoist scheduling problem. This kind of problems often arise in PCB electroplating systems. We propose a model and a algorithm to find an optimal cyclic schedule of the hoist moves. The model shows analytical properties about the problem. These properties allow to eliminate dominated or infeasible solutions, and hence speed up our algorithm which is based on branch and bound technique. The computation of lower bounds and detecting infeasible solutions require the solution of a specific class of linear programming problems. These problems can be transformed into cycle time evaluation problems in bi-valued graphs. We develop a polynomial algorithm to solve these problems. Computational results show that our algorithm outperforms algorithms in the literature.
Document type :
Conference papers
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02565328
Contributor : Jean-Baptiste Vu Van <>
Submitted on : Wednesday, May 6, 2020 - 1:01:07 PM
Last modification on : Thursday, May 7, 2020 - 1:12:40 AM

Identifiers

Collections

Citation

Haoxun Chen, Chengbin Chu, Jean-Marie Proth. Cyclic hoist scheduling based on graph theory. 1995 INRIA/IEEE Symposium on Emerging Technologies and Factory Automation. ETFA'95, Oct 1995, Paris, France. pp.451-459, ⟨10.1109/ETFA.1995.496798⟩. ⟨hal-02565328⟩

Share

Metrics

Record views

9