Top > IJAT > A Fast Scheduler for Multiagent in a Warehouse

single-au.php

IJAT Vol.3 No.2 pp. 165-173
doi: 10.20965/ijat.2009.p0165
(2009)

Paper:

Views over last 60 days: 540

A Fast Scheduler for Multiagent in a Warehouse

Jose Ildefonso U. Rubrico*, Toshimitsu Higashi**, Hirofumi Tamura***, Makoto Nikaido*, and Jun Ota*

*Graduate School of Engineering, The University of Tokyo
7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan

**Logistics and Automation Division, Murata Machinery Ltd.
2 Nakajima, Hashizume, Inuyama-shi, Aichi, Japan

***Murata Systems, Ltd., 3 Minamiochiai-cho, Kisshoin, Minami-ku, Kyoto, Japan

Received:
December 3, 2008
Accepted:
January 5, 2009
Published:
March 5, 2009
Creative Commons License
Keywords:
scheduling, planning, multiagent, automation, split delivery vehicle routing problem
Abstract
A major goal in scheduling multiagent for warehouse picking is to decrease operating cost by minimizing makespan among transport agents. Computational time must be within ten seconds for real-sized instances. Orders are initially batched by solving the split delivery vehicle routing problem, resulting trips are assigned to agents to balance their picking time, and trips are assigned to minimize blocking delays among agents. Simulation results confirmed that our proposal reduces picking time an average of 11.48% over conventional approaches.
Cite this article as:
J. Rubrico, T. Higashi, H. Tamura, M. Nikaido, and J. Ota, “A Fast Scheduler for Multiagent in a Warehouse,” Int. J. Automation Technol., Vol.3 No.2, pp. 165-173, 2009.
Data files:
References
  1. [1] J. P. van den Berg and W. H. M. Zijm, “Models for warehouse management:Classification and examples,” Int. J. Prod. Econ. 59, pp.519-528, 1999.
  2. [2] M. A. Hariga and P. E. Jackson, “The warehouse scheduling problemformulation and algorithms,” IIE Trans. 28, pp. 115-127, 1996.
  3. [3] N. Ascheuer, M. Grotschel, and A. Abdel-Aziz Abdel-Hamid, “Orderpicking in an automatic warehouse: Solving asymmetric TSPs,”Math. Methods Op. Res. 49, pp. 501-515, 1999.
  4. [4] J. A. Tompkins, et al., “Facilities Planning,” John Wiley & Sons,New York, 1996.
  5. [5] H. D. Ratliff and A. S. Rosenthal, “Order-picking in a rectangularwarehouse: A solvable case for the traveling salesman problem,”Op. Res. 31, pp. 507-521, 1983.
  6. [6] R.W. Hall, “Distance approximations for routing manual pickers ina warehouse,” IIE Trans. 25, pp. 76-87, 1993.
  7. [7] J. R. M. Gademann, J. P. Van Den Berg, and H. H. Van Der Hoff,“An order batching algorithm for wave picking in a parallel-aislewarehouse,” IIE Trans. 33, pp. 385-398, 2001.
  8. [8] S. S. Kim, R. Heragu, J. Graves, and A. St. Onge, “Intelligentagent based framework for warehouse control,” in IEEE Proc. 37thHawaii Int. Conf. on System Sciences, Hawaii, 2004.
  9. [9] P. J. Egbelu and J. M. A. Tanchoco, “Characterization of automaticguided vehicle dispatching rules,” Int. J. Prod. Res. 22, pp. 359-374,1984.
  10. [10] D. Liao and H. Fu, “Speedy delivery: A simulation-based, twophaseapproach for dynamic OHT allocation and dispatching inlarge-scale, 300mm AHMS management,” in IEEE Robotics &AutomationMagazine 11, M. Jeng, M. Zhou, and T. W. Chen (Eds.),pp. 22-32, 2004.
  11. [11] L. Qui, W.-J. Hsu, S.-H. Huang, and H. Wang, “Scheduling androuting algorithms for AGVs: A survey,” Int. J. Prod. Res. 40, pp.745-760, 2002.
  12. [12] J. I. U. Rubrico, J. Ota, T. Higashi, H. Tamura, and M. Akiyoshi,“Route generation for warehouse management using fast heuristics,”in IEEE/RSJ Int. Conf. on Intelligent Robots and Systems,Sendai, 2004.
  13. [13] M. Sipser, “Introduction to the Theory of Computation,” CourseTechnology, 1996.
  14. [14] C. R. Reeves, “Modern Heuristic Techniques for CombinatorialProblems,” Mcgraw Hill, 2000.
  15. [15] M. L. Fisher and R. Jaikumar, “A generalized assignment heuristicfor vehicle routing,” Networks 11, pp. 109-124, 1981.
  16. [16] M. Dror and P. Trudeau, “Split delivery routing,” Naval ResearchLogistics 37, pp. 383-402, 1990.
  17. [17] M. Dror, G. Laporte, and P. Trudeau, "Vehicle routing with splitdeliveries, Discrete Applied Mathematics 50, pp. 239-254, 1994.
  18. [18] C. Archetti, M. G. Speranza, and A. Hertz, “A Tabu Search Algorithmfor the Split Delivery Vehicle Routing Problem,” TransportationScience 40, 1, pp. 64-73, 2006.
  19. [19] P. M. Thompson and J. B. Orlin, “Theory of cyclic transfers, Working Paper No. OR 200-89,” Operations Research Center, MIT, Cambridge, Massachusetts, 1989.
  20. [20] M. R. Garey and D. S. Johnson, “Computers and Intractability,” W. H. Freeman and Co., New York, 1979.
  21. [21] J. I. U. Rubrico, J. Ota, T. Higashi, and H. Tamura, “Route assignment heuristics for picking products in a warehouse, in Human andArtificial Intelligence Systems: From Control to Autonomy,” Proc.of the 4th Int. Symp. on Human and Artifical Intelligence Systems, K. Murase, L. Jain, K. Sekiyama, T. Asakura (Eds.), Advanced Knowledge International, pp. 341-346, 2004.
  22. [22] K. J. Roodbergen and R. De Koster, “Routing Methods for Warehouses with Multiple Cross Aisles,” International Journal of Production Research, 39-9, 1865/1883, 2001.
  23. [23] R. Brooks, “A robust layered control system for a mobile robot,”IEEE J. Robotics and Automation 2, pp. 14-23, 1986.
  24. [24] Y. Koren and J. Borenstein, “Potential field methods and their inherent limitations for mobile robot navigation,” in Proc. IEEE Int.Conf. on Robotics and Automation, pp. 1398-1404, 1991.
  25. [25] J. I. U. Rubrico, J. Ota, T. Higashi, and H. Tamura, “Metaheuristic scheduling of multiple picking agents for warehouse management,” Industrial Robot, 35, 1, 58/6.

Creative Commons License  This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Sep. 09, 2024