An Improved Mixed Integer Programming Approach for Multi-Hoist Cyclic Scheduling Problem

作者：Che, Ada^*; Lei, Weidong; Feng, Jianguang; Chu, Chengbin

来源：IEEE Transactions on Automation Science and Engineering, 2014, 11(1): 302-309.

DOI：10.1109/TASE.2013.2254713

• Cyclic scheduling
• multi-hoist scheduling
• mixed integer programming

This paper addresses the single-track multi-hoist cyclic scheduling problem. In most existing studies, loaded hoist moves are implicitly or explicitly assumed to start and end within the same cycle. We give a counterexample to demonstrate that the optimal solution obtained with such an assumption is not necessarily the best one among all feasible solutions, called globally optimal solution. To obtain a globally optimal solution, we propose an improved mixed integer programming (MIP) approach for the multi-hoist cyclic scheduling problem with relaxation of the above assumption. Computational results on benchmark and randomly generated instances are reported and analyzed.
Note to Practitioners-Automated electroplating lines with material handling hoists are widely used in the manufacture of many electronic or mechanical products. The higher productivity of these systems could be achieved by optimizing the sequence of the hoist moves. This paper presents an improved mixed integer programming (MIP) approach for the multi-hoist cyclic scheduling problem. In contrast with most previous approaches, our MIP approach can always find a globally optimal hoist schedule with the maximum productivity. The improved MIP approach can be easily implemented using a commercial optimization software package, such as ILOG CPLEX. The optimal hoist schedule obtained with our approach can be used to control the hoist operations via a programmable logic controller.

• 出版日期2014-1
• 单位西北工业大学