G-2012-78
A polynomial time algorithm for unloading boxes off a gravity conveyor
Pierre Baptiste, Alain Hertz, André Linhares, and Djamal Rebaïne
In this paper, we study the problem introduced by Baptiste et al. (2011) of minimizing the number of steps to unload a set of boxes off a gravity conveyor. We show that this problem can be solved in polynomial time with a dynamic programming algorithm that runs in O (n3 A log F) time, where n is the number of boxes initially lined up on the conveyor, A is the size of the accessible zone, and F is the forklift capacity.
Published December 2012 , 20 pages