A Polynomial Time Algorithm for Unloading Boxes Off a Gravity Conveyor

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 (n³ 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.