Skip to main content
Article
Factory Crane Scheduling by Dynamic Programming
R. Kevin Wood and Robert F. Dell, eds., Operations Research, Computing and Homeland Defense (ICS 2011 Proceedings), INFORMS
  • Ionuţ D Aron, WorldQuant LLC
  • Latife Genç-Kaya, Istanbul Sehir University
  • Iiro Harjunkoski, ABB Corporate Research Center
  • Samid Hoda, Carnegie Mellon University
  • John N. Hooker, Carnegie Mellon University
Date of Original Version
12-1-2010
Type
Conference Proceeding
Abstract or Description
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.
DOI
10.1287/ics.2011.0009
Citation Information
Ionuţ D Aron, Latife Genç-Kaya, Iiro Harjunkoski, Samid Hoda, et al.. "Factory Crane Scheduling by Dynamic Programming" R. Kevin Wood and Robert F. Dell, eds., Operations Research, Computing and Homeland Defense (ICS 2011 Proceedings), INFORMS (2010) p. 93 - 107
Available at: http://works.bepress.com/jnhooker/6/