IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v302y2021i1d10.1007_s10479-021-03967-8.html
   My bibliography  Save this article

Retrieval scheduling in crane-based 3D automated retrieval and storage systems with shuttles

Author

Listed:
  • Wenquan Dong

    (The University of Tennessee)

  • Mingzhou Jin

    (The University of Tennessee)

  • Yanyan Wang

    (Shandong University)

  • Peter Kelle

    (Louisiana State University)

Abstract

Retrieval task scheduling has been extensively studied for 2D automated retrieval and storage systems (AS/RS). A good schedule can significantly reduce the makespan for finishing a given group of retrieval tasks. However, the task scheduling problem has never been studied for crane-based 3D AS/RS with shuttle-based depth movement mechanisms (DMMs), which has become increasingly popular in practice. This study considered how to schedule a group of retrieval requests in a crane-based 3D AS/RS with shuttle-based DMMs with the objective to minimize the makespan. A mixed-integer programing model was developed to represent the problem, and the problem was proven to be NP-hard. Four heuristics were investigated for their computational performance. First-Come-First-Serve is the current practice while the Percentage Priority to Shuttle Reallocation with the Shortest Leg rule was developed based on the existing rule for scheduling storage and retrieval tasks in 3D AS/RS with conveyor-based DMMs. The Genetic Algorithm, which is popular for 2D systems, was adapted to deal with the 3D system. The Lowest-Waiting-Time-First heuristic was proposed based on the optimality condition of the scheduling problem and was demonstrated to outperform the other three algorithms in terms of solution quality and computational time. Further numerical results revealed insights for improving 3D AS/RS productivity. When the number of retrieval tasks is small (e.g., when a short planning horizon is adopted for high responsiveness), having more shuttles can improve the system performance. When there are many tasks to schedule, for example, in a situation with a long planning horizon, using a crane with higher speed rather than adding more shuttles can improve system efficiency more.

Suggested Citation

  • Wenquan Dong & Mingzhou Jin & Yanyan Wang & Peter Kelle, 2021. "Retrieval scheduling in crane-based 3D automated retrieval and storage systems with shuttles," Annals of Operations Research, Springer, vol. 302(1), pages 111-135, July.
    • Handle: RePEc:spr:annopr:v:302:y:2021:i:1:d:10.1007_s10479-021-03967-8
    DOI: 10.1007/s10479-021-03967-8
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-021-03967-8
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10479-021-03967-8?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Yingying Wu & Chen Zhou & Wenkai Ma & Xiang T. R. Kong, 2020. "Modelling and design for a shuttle-based storage and retrieval system," International Journal of Production Research, Taylor & Francis Journals, vol. 58(16), pages 4808-4828, July.
    2. Yugang Yu & René de Koster, 2009. "Optimal zone boundaries for two-class-based compact three-dimensional automated storage and retrieval systems," IISE Transactions, Taylor & Francis Journals, vol. 41(3), pages 194-208.
    3. Boysen, Nils & Emde, Simon & Hoeck, Michael & Kauderer, Markus, 2015. "Part logistics in the automotive industry: Decision problems, literature review and research agenda," European Journal of Operational Research, Elsevier, vol. 242(1), pages 107-120.
    4. Bipan Zou & Xianhao Xu & Yeming Gong & René de Koster, 2016. "Modeling parallel movement of lifts and vehicles in tier-captive vehicle-based warehousing systems," Post-Print hal-02313400, HAL.
    5. Xiao Cai & Sunderesh S. Heragu & Yang Liu, 2014. "Modeling and evaluating the AVS/RS with tier-to-tier vehicles using a semi-open queueing network," IISE Transactions, Taylor & Francis Journals, vol. 46(9), pages 905-927, September.
    6. Yugang Yu & René De Koster, 2012. "Sequencing heuristics for storing and retrieving unit loads in 3D compact automated warehousing systems," IISE Transactions, Taylor & Francis Journals, vol. 44(2), pages 69-87.
    7. Boysen, Nils & Emde, Simon & Hoeck, Michael & Kauderer, Markus, 2015. "Part logistics in the automotive industry: Decision problems, literature review and research agenda," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 79443, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    8. Carlo, Héctor J. & Vis, Iris F.A., 2012. "Sequencing dynamic storage systems with multiple lifts and shuttles," International Journal of Production Economics, Elsevier, vol. 140(2), pages 844-853.
    9. Boysen, Nils & Stephan, Konrad, 2016. "A survey on single crane scheduling in automated storage/retrieval systems," European Journal of Operational Research, Elsevier, vol. 254(3), pages 691-704.
    10. Yanyan Wang & Shandong Mou & Yaohua Wu, 2015. "Task scheduling for multi-tier shuttle warehousing systems," International Journal of Production Research, Taylor & Francis Journals, vol. 53(19), pages 5884-5895, October.
    11. Yang, Peng & Yang, Kaidong & Qi, Mingyao & Miao, Lixin & Ye, Bin, 2017. "Designing the optimal multi-deep AS/RS storage rack under full turnover-based storage policy based on non-approximate speed model of S/R machine," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 104(C), pages 113-130.
    12. Tone Lerher, 2016. "Travel time model for double-deep shuttle-based storage and retrieval systems," International Journal of Production Research, Taylor & Francis Journals, vol. 54(9), pages 2519-2540, May.
    13. Jianbin Li & Rihuan Huang & James B. Dai, 2017. "Joint optimisation of order batching and picker routing in the online retailer’s warehouse in China," International Journal of Production Research, Taylor & Francis Journals, vol. 55(2), pages 447-461, January.
    14. Azadeh, K. & de Koster, M.B.M. & Roy, D., 2017. "Robotized Warehouse Systems: Developments and Research Opportunities," ERIM Report Series Research in Management ERS-2017-009-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    15. Bipan Zou & Xianhao Xu & Yeming Gong & René de Koster, 2016. "Modeling parallel movement of lifts and vehicles in tier-captive vehicle-based warehousing systems," Post-Print hal-01892897, HAL.
    16. Xianhao Xu & Yeming (Yale) Gong & Xiangxiang Fan & Guwen Shen & Bipan Zou, 2018. "Travel-time model of dual-command cycles in a 3D compact AS/RS with lower mid-point I/O dwell point policy," International Journal of Production Research, Taylor & Francis Journals, vol. 56(4), pages 1620-1641, February.
    17. Nima Zaerpour & Yugang Yu & René B.M. Koster, 2015. "Storing Fresh Produce for Fast Retrieval in an Automated Compact Cross-Dock System," Production and Operations Management, Production and Operations Management Society, vol. 24(8), pages 1266-1284, August.
    18. Xianhao Xu & Yeming Gong & Xiangxiang Fan & Guwen Shen & Bipan Zou, 2018. "Travel-time model of dual-command cycles in a 3D compact AS/RS with lower mid-point I/O dwell point policy," Post-Print hal-02312021, HAL.
    19. Mahmut Tutam & John A. White, 2019. "A multi-dock, unit-load warehouse design," IISE Transactions, Taylor & Francis Journals, vol. 51(3), pages 232-247, March.
    20. Elena Tappia & Debjit Roy & René de Koster & Marco Melacini, 2017. "Modeling, Analysis, and Design Insights for Shuttle-Based Compact Storage Systems," Transportation Science, INFORMS, vol. 51(1), pages 269-295, February.
    21. Zou, Bipan & Xu, Xianhao & (Yale) Gong, Yeming & De Koster, René, 2016. "Modeling parallel movement of lifts and vehicles in tier-captive vehicle-based warehousing systems," European Journal of Operational Research, Elsevier, vol. 254(1), pages 51-67.
    22. Yunsoo Ha & Junjae Chae, 2019. "A decision model to determine the number of shuttles in a tier-to-tier SBS/RS," International Journal of Production Research, Taylor & Francis Journals, vol. 57(4), pages 963-984, February.
    23. Roodbergen, Kees Jan & Vis, Iris F.A., 2009. "A survey of literature on automated storage and retrieval systems," European Journal of Operational Research, Elsevier, vol. 194(2), pages 343-362, April.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Dong, Wenquan & Jin, Mingzhou, 2024. "Automated storage and retrieval system design with variant lane depths," European Journal of Operational Research, Elsevier, vol. 314(2), pages 630-646.
    2. Chen, Ran & Yang, Jingjing & Yu, Yugang & Guo, Xiaolong, 2023. "Retrieval request scheduling in a shuttle-based storage and retrieval system with two lifts," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 174(C).
    3. Lei Deng & Lei Chen & Jingjie Zhao & Ruimei Wang, 2021. "Modeling and performance analysis of shuttle-based compact storage systems under parallel processing policy," PLOS ONE, Public Library of Science, vol. 16(11), pages 1-26, November.
    4. Yang, Jingjing & de Koster, René B.M. & Guo, Xiaolong & Yu, Yugang, 2023. "Scheduling shuttles in deep-lane shuttle-based storage systems," European Journal of Operational Research, Elsevier, vol. 308(2), pages 696-708.
    5. Polten, Lukas & Emde, Simon, 2022. "Multi-shuttle crane scheduling in automated storage and retrieval systems," European Journal of Operational Research, Elsevier, vol. 302(3), pages 892-908.
    6. Lu Zhen & Jingwen Wu & Haolin Li & Zheyi Tan & Yingying Yuan, 2023. "Scheduling multiple types of equipment in an automated warehouse," Annals of Operations Research, Springer, vol. 322(2), pages 1119-1141, March.
    7. Dong, Wenquan & Jin, Mingzhou, 2021. "Travel time models for tier-to-tier SBS/RS with different storage assignment policies and shuttle dispatching rules," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 155(C).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Dong, Wenquan & Jin, Mingzhou, 2024. "Automated storage and retrieval system design with variant lane depths," European Journal of Operational Research, Elsevier, vol. 314(2), pages 630-646.
    2. Dong, Wenquan & Jin, Mingzhou, 2021. "Travel time models for tier-to-tier SBS/RS with different storage assignment policies and shuttle dispatching rules," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 155(C).
    3. Chen, Ran & Yang, Jingjing & Yu, Yugang & Guo, Xiaolong, 2023. "Retrieval request scheduling in a shuttle-based storage and retrieval system with two lifts," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 174(C).
    4. Yang, Jingjing & de Koster, René B.M. & Guo, Xiaolong & Yu, Yugang, 2023. "Scheduling shuttles in deep-lane shuttle-based storage systems," European Journal of Operational Research, Elsevier, vol. 308(2), pages 696-708.
    5. Kaveh Azadeh & René De Koster & Debjit Roy, 2019. "Robotized and Automated Warehouse Systems: Review and Recent Developments," Transportation Science, INFORMS, vol. 53(4), pages 917-945, July.
    6. Tappia, Elena & Roy, Debjit & Melacini, Marco & De Koster, René, 2019. "Integrated storage-order picking systems: Technology, performance models, and design insights," European Journal of Operational Research, Elsevier, vol. 274(3), pages 947-965.
    7. Bipan Zou & René De Koster & Xianhao Xu, 2018. "Operating Policies in Robotic Compact Storage and Retrieval Systems," Transportation Science, INFORMS, vol. 52(4), pages 788-811, August.
    8. Yanyan Wang & Jinning Qin & Shandong Mou & Ke Huang & Xiaofeng Zhao, 2023. "DSS approach for sustainable system design of shuttle-based storage and retrieval systems," Flexible Services and Manufacturing Journal, Springer, vol. 35(3), pages 698-726, September.
    9. Emilio Moretti & Elena Tappia & Martina Mauri & Marco Melacini, 2022. "A performance model for mobile robot-based part feeding systems to supermarkets," Flexible Services and Manufacturing Journal, Springer, vol. 34(3), pages 580-613, September.
    10. Kumawat, Govind Lal & Roy, Debjit & De Koster, René & Adan, Ivo, 2021. "Stochastic modeling of parallel process flows in intra-logistics systems: Applications in container terminals and compact storage systems," European Journal of Operational Research, Elsevier, vol. 290(1), pages 159-176.
    11. Wu, Guangmei & Xu, Xianhao & Gong, Yeming (Yale) & De Koster, René & Zou, Bipan, 2019. "Optimal design and planning for compact automated parking systems," European Journal of Operational Research, Elsevier, vol. 273(3), pages 948-967.
    12. Kaveh Azadeh & Debjit Roy & René De Koster, 2019. "Design, Modeling, and Analysis of Vertical Robotic Storage and Retrieval Systems," Transportation Science, INFORMS, vol. 53(5), pages 1213-1234, September.
    13. Chen, Gang & Feng, Haolin & Luo, Kaiyi & Tang, Yanli, 2021. "Retrieval-oriented storage relocation optimization of an automated storage and retrieval system," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 155(C).
    14. Nils Boysen & David Boywitz & Felix Weidinger, 2018. "Deep-lane storage of time-critical items: one-sided versus two-sided access," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(4), pages 1141-1170, October.
    15. Gharehgozli, Amir & Xu, Chao & Zhang, Wenda, 2021. "High multiplicity asymmetric traveling salesman problem with feedback vertex set and its application to storage/retrieval system," European Journal of Operational Research, Elsevier, vol. 289(2), pages 495-507.
    16. Liu, Tian & Gong, Yeming & De Koster, René B.M., 2018. "Travel time models for split-platform automated storage and retrieval systems," International Journal of Production Economics, Elsevier, vol. 197(C), pages 197-214.
    17. Boysen, Nils & de Koster, René & Füßler, David, 2021. "The forgotten sons: Warehousing systems for brick-and-mortar retail chains," European Journal of Operational Research, Elsevier, vol. 288(2), pages 361-381.
    18. Boysen, Nils & Briskorn, Dirk & Meisel, Frank, 2017. "A generalized classification scheme for crane scheduling with interference," European Journal of Operational Research, Elsevier, vol. 258(1), pages 343-357.
    19. Azadeh, K. & de Koster, M.B.M. & Roy, D., 2017. "Robotized Warehouse Systems: Developments and Research Opportunities," ERIM Report Series Research in Management ERS-2017-009-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    20. Boysen, Nils & de Koster, René & Weidinger, Felix, 2019. "Warehousing in the e-commerce era: A survey," European Journal of Operational Research, Elsevier, vol. 277(2), pages 396-411.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:annopr:v:302:y:2021:i:1:d:10.1007_s10479-021-03967-8. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.