Factory Crane Scheduling by Dynamic Programming

We describe a specialized dynamic programming algorithm for factory crane scheduling. An innovative data structure controls the memory requirements of the state space and enables solution of problems of realistic size. The algorithm finds optimal spacetime trajectories for two factory cranes or hoists that move along a single overhead track. Each crane is assigned a sequence of pickups and deliveries at specified locations that must be performed within given time windows. The cranes must not interfere with each other, although one may yield to the other. The state space representation permits a wide variety of constraints and objective functions. It is stored in a compressed data structure that uses a cartesian product of intervals of states and an array of two-dimensional circular queues. We also show that only certain types of trajectories need be considered. The algorithm found optimal solutions in less than a minute for medium-sized instances of the problem (160 tasks, spanning four hours). It can also be used to create benchmarks for tuning heuristic algorithms that solve larger instances.