SOR 1996 (Springer Verlag, pp. 111-116)

Jochen Rethmann, Hochschule Niederrhein, FB Elektrotechnik und Informatik, Reinarzstraße 49, 47805 Krefeld

Storage controlled pile-up systems
SOR 1996 (Springer Verlag, pp. 111-116)

J. Rethmann

E. Wanke

Abstract

A pile-up system consists of one or more stacker cranes picking up bins from a conveyor and placing them onto pallets with respect to customer orders. We give a mathematical definition of the pile-up problem, define a data structure for control algorithms, introduce polynomial time algorithms for deciding whether a system can be blocked by making bad decisions, and show that controlling pile-up systems is in general NP-complete. For pile-up systems with a restricted storage capacity or with a fixed number of pile-up places the pile-up problem is proved to be solvable very efficiently.