Skip to main content
Optimal Movement of Factory Cranes
Tepper School of Business
  • Ionuţ Aron, Cura Capital Management
  • Latife Genç-Kaya, Carnegie Mellon University
  • Iiro Harjunkoski, ABB Corporate Research Center
  • Samid Hoda, Carnegie Mellon University
  • John N. Hooker, Carnegie Mellon University
Date of Original Version
Working Paper
Rights Management
All Rights Reserved
Abstract or Description
We study the problem of finding optimal space-time trajectories for two factory cranes or hoists that move along a single overhead track. Each crane is a assigned a sequence of pickups and deliveries at specified locations that must be performed within given time windows. The cranes must be operated so as not to interfere with each other, although one crane may need to yield to another. The objective is generally to follow a production schedule as closely as possible. We show that only certain types of trajectories need be considered to obtain an optimal solution. This simplifies the operation of the cranes and enhances safety, because the cranes move according to predictable patterns. We present a specialized dynamic programming algorithm that solves the problem. To control the state space size we use an innovative state space representation based on a cartesian product of intervals of states and an array of two-dimensional circular queues. The algorithm solves medium-sized instances of the problem to optimality and can be used to create benchmarks for tuning heuristic algorithms that solve larger instances.
Citation Information
Ionuţ Aron, Latife Genç-Kaya, Iiro Harjunkoski, Samid Hoda, et al.. "Optimal Movement of Factory Cranes" (2008)
Available at: