Cyclic hoist scheduling based on graph theory - Archive ouverte HAL Access content directly
Conference Papers Year :

Cyclic hoist scheduling based on graph theory

(1) , (1) , (1)
1
Haoxun Chen
  • Function : Author
  • PersonId : 182315
  • IdHAL : haoxun-chen
Chengbin Chu
Jean-Marie Proth
  • Function : Author

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.
Not file

Dates and versions

hal-02565328 , version 1 (06-05-2020)

Identifiers

Cite

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⟩

Collections

INRIA INRIA2
15 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More