×

zbMATH — the first resource for mathematics

Algorithms for on-line order batching in an order picking warehouse. (English) Zbl 1251.90007
Summary: In manual order picking systems, order pickers walk or ride through a distribution warehouse in order to collect items required by (internal or external) customers. Order batching consists of combining these – indivisible – customer orders into picking orders. With respect to order batching, two problem types can be distinguished: in off-line (static) batching, all customer orders are known in advance; in on-line (dynamic) batching, customer orders become available dynamically over time. This paper considers an on-line order batching problem in which the maximum completion time of the customer orders arriving within a certain time period has to be minimized. The author shows how heuristic approaches for off-line order batching can be modified in order to deal with the on-line situation. In a competitive analysis, lower and upper bounds for the competitive ratios of the proposed algorithms are presented. The proposed algorithms are evaluated in a series of extensive numerical experiments. It is demonstrated that the choice of an appropriate batching method can lead to a substantial reduction of the maximum completion time.

MSC:
90-04 Software, source code, etc. for problems pertaining to operations research and mathematical programming
90B35 Deterministic scheduling theory in operations research
PDF BibTeX Cite
Full Text: DOI
References:
[1] de Koster, R.; Le-Duc, T.; Roodbergen, K., Design and control of warehouse order picking: a literature review, European journal of operational research, 182, 2, 481-501, (2007) · Zbl 1121.90385
[2] Wäscher, G., Order picking: a survey of planning problems and methods, (), 323-347
[3] Caron, F.; Marchet, G.; Perego, A., Routing policies and COI-based storage policies in picker-to-part systems, International journal of production research, 36, 3, 713-732, (1998) · Zbl 0951.90507
[4] de Koster, R.; Roodbergen, K.; van Voorden, R., Reduction of walking time in the distribution center of de bijenkorf, (), 215-234 · Zbl 0969.90060
[5] Yu, M.; de Koster, R., The impact of order batching and picking area zoning on order picking system performance, European journal of operational research, 198, 2, 480-490, (2009) · Zbl 1163.90433
[6] Ratliff, H.; Rosenthal, A., Order-picking in a rectangular warehouse: a solvable case of the traveling salesman problem, Operations research, 31, 2, 507-521, (1983) · Zbl 0523.90060
[7] Chew, E.; Tang, L., Travel time analysis for general item location assignment in a rectangular warehouse, European journal of operational research, 112, 3, 582-597, (1999) · Zbl 0933.90042
[8] Gademann, N.; van de Velde, S., Order batching to minimize total travel time in a parallel-aisle warehouse, IIE transactions, 37, 1, 63-75, (2005)
[9] Bozer, Y.; Kile, J., Order batching in walk-and-Pick order picking systems, International journal of production research, 46, 7, 1887-1909, (2008) · Zbl 1153.90302
[10] Gibson, D.; Sharp, G., Order batching procedures, European journal of operational research, 58, 1, 57-67, (1992)
[11] Elsayed, E., Algorithms for optimal material handling in automatic warehousing systems, International journal of production research, 19, 5, 525-535, (1981)
[12] Ho, Y.C.; Su, T.S.; Shi, Z.B., Order-batching methods for an order-picking warehouse with two cross aisles, Computers & industrial engineering, 55, 2, 321-347, (2008)
[13] Clarke, G.; Wright, J., Scheduling of vehicles from a central depot to a number of delivery points, Operations research, 12, 4, 568-581, (1964)
[14] de Koster, M.; van der Poort, E.; Wolters, M., Efficient orderbatching methods in warehouses, International journal of production research, 37, 7, 1479-1504, (1999) · Zbl 0948.90508
[15] Hsu, C.; Chen, K.; Chen, M., Batching orders in warehouses by minimizing travel distance with genetic algorithms, Computers in industry, 56, 2, 169-178, (2005)
[16] Tsai, C.Y.; Liou, J.; Huang, T.M., Using a multiple-GA method to solve the batch picking problem: considering travel distance and order due time, International journal of production research, 46, 22, 6533-6555, (2008) · Zbl 1154.90381
[17] Henn, S.; Koch, S.; Doerner, K.; Strauss, C.; Wäscher, G., Metaheuristics for the order batching problem in manual order picking systems, Bur: business research, 3, 1, 82-105, (2010)
[18] Kamin, N., On-line optimization of order picking in an automated warehouse, (1998), Shaker Aachen
[19] Won, J.; Olafsson, S., Joint order batching and order picking in warehouse operations, International journal of production research, 43, 7, 1427-1442, (2005) · Zbl 1068.90011
[20] Elsayed, E.; Lee, M.K., Order processing in automated storage/retrieval systems with due dates, IIE transactions, 28, 7, 567-577, (1996)
[21] van Nieuwenhuyse, I.; de Koster, R., Evaluating order throughput time in 2-block warehouses with time window batching, International journal of production economics, 121, 654-664, (2009)
[22] Le-Duc, T.; de Koster, R., Travel time estimation and order batching in a 2-block warehouse, European journal of operational research, 176, 1, 374-388, (2007) · Zbl 1137.90332
[23] Zhang, G.; Cai, X.; Lee, C.Y.; Wong, C., On-line algorithms for minimizing makespan on batch processing machines, Naval research logistics, 48, 3, 241-258, (2001) · Zbl 1018.90017
[24] Poon, C.; Yu, W., On-line scheduling algorithms for a batch machine with finite capacity, Journal of combinatorial optimization, 9, 167-186, (2005) · Zbl 1079.90060
[25] Ascheuer, N.; Krumke, S.; Rambau, J., Online dial-a-ride problems: minimizing the completion time, (), 639-650 · Zbl 0971.68621
[26] Feuerstein, E.; Stougie, L., On-line single-server dial-a-ride problems, Theoretical computer science, 268, 91-105, (2001) · Zbl 0984.68003
[27] Hall, R., Distance approximations for routing manual pickers in a warehouse, IIE transactions, 25, 4, 76-87, (1993)
[28] Fiat, A.; Woeginger, G., Competitive analysis of algorithms, (), 1-12
[29] Sleator, D.; Tarjan, R., Amortized efficiency of List update and paging rules, Communications of the ACM, 28, 2, 202-208, (1985)
[30] Angelelli, E.; Speranza, G.; Savelsbergh, M., Competitive analysis for dynamic multiperiod uncapacitated routing problems, Networks, 49, 4, 308-317, (2007) · Zbl 1141.90334
[31] Gfeller, B.; Peeters, L.; Weber, B.; Widmayer, P., Online single machine batch scheduling, (), 424-435 · Zbl 1132.90323
[32] Krumke, S.; de Paepe, W.; Poensgen, D.; Lipmann, M.; Marchetti-Spaccamela, A.; Stougie, L., On minimizing the maximum flow time in the online dial-a-ride problem, (), 258-269 · Zbl 1177.90394
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.