Groupe d’études et de recherche en analyse des décisions

In this talk, we study the problem introduced by Baptiste et al. of minimizing the number of steps to unloading a set of boxes with different destinations lined up on a gravity conveyor. We show that this problem can be solved in polynomial time, by presenting a dynamic programming algorithm that runs in $$O(n^3 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. We also study the online version of this problem, in which the destinations of the boxes are revealed as they are unloaded. We propose oblivious algorithms, as well as anticipatory algorithms which rely on the aforementioned algorithm for the offline problem. A computational study is performed to gauge the quality of the solutions that they provide.