Back

G-2012-78

A polynomial time algorithm for unloading boxes off a gravity conveyor

, , , and

BibTeX reference

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.

, 20 pages

Publication