Multi-crane scheduling in steel coil warehouse

摘要

This paper considers a multi-crane scheduling problem commonly encountered in real warehouse operations in steel enterprises. A given set of coils are to be retrieved to their designated places. If a required coil is in upper level or in lower level without being blocked, it can be picked up directly to its designated place; else, the blocking coils need to be picked up to another position first. Our problem aims to determine which positions for blocking coils to be shuffled to, and a joint transportation sequence of required coils to the designated places and blocking coils to be shuffled as soon as possible by multi-crane carrying these coils simultaneously.For describe the studied problem clearly, we first formulate it as a mixed integer linear programming (MILP) model. Then some feasible and optimal properties for assigning cranes to avoid collisions in possible positions are identified. Since a special case of our problem is demonstrated strongly NP-hard, we further propose a heuristic algorithm. A lower bound to the problem is developed and the performance of the heuristic algorithm is analyzed from the worst case point of view. Finally, computational experiments are used to evaluate the average performance of our proposed methods and the results show that the proposed heuristic algorithm is capable of generating good quality solutions.