A polynomial time algorithm for unloading boxes off a gravity conveyor

In this paper, we study the problem introduced by Baptiste et al. (2011) [3] 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(n3AlogF)O(n3AlogF) time, where nn is the number of boxes initially lined up on the conveyor, AA is the size of the accessible zone, and FF is the forklift capacity.