A polynomial time algorithm for unloading boxes off a gravity conveyor

作者：Baptiste Pierre; Hertz Alain^*; Linhares Andre; Rebaine Djamal

来源：Discrete Optimization, 2013, 10(4): 251-262.

DOI：10.1016/j.disopt.2013.07.004

• Dynamic programming
• Gravity conveyor
• Boxes
• Unloading

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

• 出版日期2013-11