G-2012-78
A polynomial time algorithm for unloading boxes off a gravity conveyor
Pierre Baptiste, Alain Hertz, André Linhares et 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.
Paru en décembre 2012 , 20 pages