Optimizing a dynamic order-picking process

Yossi Bukchin

doi:10.1016/j.ejor.2011.12.041

2012-06-01

PRE

Yossi Bukchin

Eugene Khmelnitsky *

Pini Yakuel

DOI：10.1016/j.ejor.2011.12.041

原文链接

摘要

En 中文

This research studies the problem of batching orders in a dynamic, finite-horizon environment to minimize order tardiness and overtime costs of the pickers. The problem introduces the following trade-off: at every period, the picker has to decide whether to go on a tour and pick the accumulated orders, or to wait for more orders to arrive. By waiting, the picker risks higher tardiness of existing orders on the account of lower tardiness of future orders. We use a Markov decision process (MDP) based approach to set an optimal decision making policy. In order to evaluate the potential improvement of the proposed approach in practice, we compare the optimal policy with two naive heuristics: (1) Go on tour immediately after an order arrives, and, (2) Wait as long as the current orders can be picked and supplied on time. The optimal policy shows a considerable improvement over the naive heuristics, in the range of 7-99%, where the specific values depend on the picking process parameters. We have found that one measure, the slack percentage of the picking process, associated with the difference between the promised lead time and the single item picking time, predicts quite accurately the cost reduction generated by the optimal policy. Since relatively small-scale problems could be solved by the optimal algorithm, a heuristic was developed, based on the structure and properties of the optimal solutions. Numerical results show that the proposed heuristic, MDP-H, outperforms the naive heuristics in all experiments. As compared to the optimal solution, MDP-H provides close to optimal results for a slack of up to 40%. (C) 2011 Elsevier B.V. All rights reserved.

Keyword:

Warehouse activities

Markov decision process

Heuristic policies