The BCS algorithm: optimizing crane schedules on multiple bays in conjunction with continuous time simulation

Abstract

This thesis introduces the Bay Crane Scheduling (BCS) problem and related BCS algorithm. The purpose of this algorithm is to optimize the assignment of jobs to overhead cranes as well as the sequence in which each crane performs its assigned jobs. This problem is unique from other Overhead Crane Scheduling (OCS) problems through its increased complexity. Up until now, OCS problems involve a set number of cranes operating in a single common area, referred to as a bay, and are unable to pass over each other. The BCS problem involves a varying number of active cranes operating in multiple bays. Each crane is allowed to move from one bay to the next, through specific locations called bridges. This is crucial to completing certain “special” jobs that require two cranes operating in unison to transport an item. The BCS algorithm employs two continuous time simulations in conjunction with an initial job-assignment algorithm and a Simulated Annealing (SA) improvement heuristic in order to minimize the non-productive crane time, while avoiding overloading any crane. To the extent of the author’s knowledge, this is the first time a continuous time simulation has been used to model an OC system. The BCS algorithm was originally developed for a large manufacturing facility, and when it was tested against the facility’s current scheduling methods, it shows a 20% improvement in the overall active crane time required to complete equivalent set of jobs. This improved efficiency is crucial to the manufacturing facility being able to increase its production rate without the addition of new cranes. In addition, BCS is statistically shown to be superior to the current strategy. The results from BCS are substantial and practitioners are encouraged to utilize BCS’s methodologies to improve other overhead crane systems.