IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v307y2023i2p590-603.html
   My bibliography  Save this article

The parallel AGV scheduling problem with battery constraints: A new formulation and a matheuristic approach

Author

Listed:
  • Boccia, Maurizio
  • Masone, Adriano
  • Sterle, Claudio
  • Murino, Teresa

Abstract

Nowadays, automated guided vehicles (AGVs) are frequently used in larger systems, known as AGV-based transportation systems, for the movement of goods and materials from one location to another. The design of an efficient and effective AGV-based transportation system requires to address many tactical and operational issues. Among the others, the scheduling of transfer jobs on the AGVs represents one of the main operational issues that has to be solved to overcome delays in production and material handling processes. In this context, a significant research activity on AGV systems and on related scheduling problems has been conducted in the last twenty years. However, most of the contributions neglected the issues related to the AGV battery depletion and recharge. Thus, in this work, we study the AGV scheduling problem with battery constraints (ASP-BC). It consists in determining the scheduling of transfer jobs and charging operations of a fleet of homogeneous AGVs such that the makespan of the handling process is minimized. The methodological contribution of our work is twofold. On one side, we propose an original mixed integer linear programming formulation based on the bottleneck generalized assignment problem. On the other side, we propose a three step matheuristic based on the sequential solution of the two subproblems arising from the natural decomposition of the ASP-BC and a local search heuristic. The proposed approaches have been tested and validated on simulated and real instances provided by a manufacturing company. The results show the effectiveness and the scalability of the proposed solution methods.

Suggested Citation

  • Boccia, Maurizio & Masone, Adriano & Sterle, Claudio & Murino, Teresa, 2023. "The parallel AGV scheduling problem with battery constraints: A new formulation and a matheuristic approach," European Journal of Operational Research, Elsevier, vol. 307(2), pages 590-603.
  • Handle: RePEc:eee:ejores:v:307:y:2023:i:2:p:590-603
    DOI: 10.1016/j.ejor.2022.10.023
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221722008116
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ejor.2022.10.023?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. Martello, Silvano & Toth, Paolo, 1995. "The bottleneck generalized assignment problem," European Journal of Operational Research, Elsevier, vol. 83(3), pages 621-638, June.
    2. Aggoune, Riad, 2004. "Minimizing the makespan for the flow shop scheduling problem with availability constraints," European Journal of Operational Research, Elsevier, vol. 153(3), pages 534-543, March.
    3. Lijun Wei & Zhixing Luo, & Roberto Baldacci & Andrew Lim, 2020. "A New Branch-and-Price-and-Cut Algorithm for One-Dimensional Bin-Packing Problems," INFORMS Journal on Computing, INFORMS, vol. 32(2), pages 428-443, April.
    4. Mellouli, Racem & Sadfi, Chrif & Chu, Chengbin & Kacem, Imed, 2009. "Identical parallel-machine scheduling under availability constraints to minimize the sum of completion times," European Journal of Operational Research, Elsevier, vol. 197(3), pages 1150-1165, September.
    5. Mohammad Asghari & Amir M. Fathollahi-Fard & S. M. J. Mirzapour Al-e-hashem & Maxim A. Dulebenets, 2022. "Transformation and Linearization Techniques in Optimization: A State-of-the-Art Survey," Mathematics, MDPI, vol. 10(2), pages 1-26, January.
    6. Fragapane, Giuseppe & de Koster, René & Sgarbossa, Fabio & Strandhagen, Jan Ola, 2021. "Planning and control of autonomous mobile robots for intralogistics: Literature review and research agenda," European Journal of Operational Research, Elsevier, vol. 294(2), pages 405-426.
    7. Vis, Iris F.A., 2006. "Survey of research in the design and control of automated guided vehicle systems," European Journal of Operational Research, Elsevier, vol. 170(3), pages 677-709, May.
    8. Gregory H. Graves & Chung‐Yee Lee, 1999. "Scheduling maintenance and semiresumable jobs on a single machine," Naval Research Logistics (NRL), John Wiley & Sons, vol. 46(7), pages 845-863, October.
    9. Martello, Silvano & Toth, Paolo, 1995. "A note on exact algorithms for the bottleneck generalized assignment problem," European Journal of Operational Research, Elsevier, vol. 83(3), pages 711-712, June.
    10. Liao, Lu-Wen & Sheen, Gwo-Ji, 2008. "Parallel machine scheduling with machine availability and eligibility constraints," European Journal of Operational Research, Elsevier, vol. 184(2), pages 458-467, January.
    11. Bongiovanni, Claudia & Kaspi, Mor & Geroliminis, Nikolas, 2019. "The electric autonomous dial-a-ride problem," Transportation Research Part B: Methodological, Elsevier, vol. 122(C), pages 436-456.
    12. Wang, Xiuli & Cheng, T.C.E., 2015. "A heuristic for scheduling jobs on two identical parallel machines with a machine availability constraint," International Journal of Production Economics, Elsevier, vol. 161(C), pages 74-82.
    13. Sun, Kaibiao & Li, Hongxing, 2010. "Scheduling problems with multiple maintenance activities and non-preemptive jobs on two identical parallel machines," International Journal of Production Economics, Elsevier, vol. 124(1), pages 151-158, March.
    14. Chung‐Yee Lee & Zhi‐Long Chen, 2000. "Scheduling jobs and maintenance activities on parallel machines," Naval Research Logistics (NRL), John Wiley & Sons, vol. 47(2), pages 145-165, March.
    15. Masmoudi, Mohamed Amine & Hosny, Manar & Demir, Emrah & Genikomsakis, Konstantinos N. & Cheikhrouhou, Naoufel, 2018. "The dial-a-ride problem with electric vehicles and battery swapping stations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 118(C), pages 392-420.
    16. Gedik, Ridvan & Rainwater, Chase & Nachtmann, Heather & Pohl, Ed A., 2016. "Analysis of a parallel machine scheduling problem with sequence dependent setup times and job availability intervals," European Journal of Operational Research, Elsevier, vol. 251(2), pages 640-650.
    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. Chen, Wanying & Gong, Yeming & Chen, Qi & Wang, Hongwei, 2024. "Does battery management matter? Performance evaluation and operating policies in a self-climbing robotic warehouse," European Journal of Operational Research, Elsevier, vol. 312(1), pages 164-181.
    2. Li, Kunpeng & Liu, Tengbo & Ram Kumar, P.N. & Han, Xuefang, 2024. "A reinforcement learning-based hyper-heuristic for AGV task assignment and route planning in parts-to-picker warehouses," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 185(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. Seyed Habib A. Rahmati & Abbas Ahmadi & Kannan Govindan, 2018. "A novel integrated condition-based maintenance and stochastic flexible job shop scheduling problem: simulation-based optimization approach," Annals of Operations Research, Springer, vol. 269(1), pages 583-621, October.
    2. Behrooz Shahbazi & Seyed Habib A. Rahmati, 2021. "Developing a Flexible Manufacturing Control System Considering Mixed Uncertain Predictive Maintenance Model: a Simulation-Based Optimization Approach," SN Operations Research Forum, Springer, vol. 2(4), pages 1-43, December.
    3. Cortés-Murcia, David L. & Prodhon, Caroline & Murat Afsar, H., 2019. "The electric vehicle routing problem with time windows, partial recharges and satellite customers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 130(C), pages 184-206.
    4. K. H. Adjallah & K. P. Adzakpa, 2007. "Minimizing maintenance cost involving flow-time and tardiness penalty with unequal release dates," Journal of Risk and Reliability, , vol. 221(1), pages 57-65, March.
    5. Christian Billing & Florian Jaehn & Thomas Wensing, 2020. "Fair task allocation problem," Annals of Operations Research, Springer, vol. 284(1), pages 131-146, January.
    6. Sonia & Puri, M.C., 2008. "Two-stage time minimizing assignment problem," Omega, Elsevier, vol. 36(5), pages 730-740, October.
    7. Xia, Tangbin & Jin, Xiaoning & Xi, Lifeng & Ni, Jun, 2015. "Production-driven opportunistic maintenance for batch production based on MAM–APB scheduling," European Journal of Operational Research, Elsevier, vol. 240(3), pages 781-790.
    8. Zhang, Li & Liu, Zhongshan & Yu, Lan & Fang, Ke & Yao, Baozhen & Yu, Bin, 2022. "Routing optimization of shared autonomous electric vehicles under uncertain travel time and uncertain service time," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 157(C).
    9. Yelin Fu & Jianshan Sun & K. Lai & John Leung, 2015. "A robust optimization solution to bottleneck generalized assignment problem under uncertainty," Annals of Operations Research, Springer, vol. 233(1), pages 123-133, October.
    10. Yarlin Kuo & Zi‐Ann Chang, 2007. "Integrated production scheduling and preventive maintenance planning for a single machine under a cumulative damage failure process," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(6), pages 602-614, September.
    11. Liles, Joseph M. & Robbins, Matthew J. & Lunday, Brian J., 2023. "Improving defensive air battle management by solving a stochastic dynamic assignment problem via approximate dynamic programming," European Journal of Operational Research, Elsevier, vol. 305(3), pages 1435-1449.
    12. J-J Wang & J-B Wang & F Liu, 2011. "Parallel machines scheduling with a deteriorating maintenance activity," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(10), pages 1898-1902, October.
    13. Zhang, Li & Liu, Zhongshan & Yu, Bin & Long, Jiancheng, 2024. "A ridesharing routing problem for airport riders with electric vehicles," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 184(C).
    14. Geurtsen, M. & Didden, Jeroen B.H.C. & Adan, J. & Atan, Z. & Adan, I., 2023. "Production, maintenance and resource scheduling: A review," European Journal of Operational Research, Elsevier, vol. 305(2), pages 501-529.
    15. Zheng, Feifeng & Cheng, Yongxi & Xu, Yinfeng & Liu, Ming, 2013. "Competitive strategies for an online generalized assignment problem with a service consecution constraint," European Journal of Operational Research, Elsevier, vol. 229(1), pages 59-66.
    16. Li, Guo & Liu, Mengqi & Sethi, Suresh P. & Xu, Dehua, 2017. "Parallel-machine scheduling with machine-dependent maintenance periodic recycles," International Journal of Production Economics, Elsevier, vol. 186(C), pages 1-7.
    17. Su, Yue & Dupin, Nicolas & Puchinger, Jakob, 2023. "A deterministic annealing local search for the electric autonomous dial-a-ride problem," European Journal of Operational Research, Elsevier, vol. 309(3), pages 1091-1111.
    18. Detienne, Boris, 2014. "A mixed integer linear programming approach to minimize the number of late jobs with and without machine availability constraints," European Journal of Operational Research, Elsevier, vol. 235(3), pages 540-552.
    19. Wenchang Luo & Yao Xu & Weitian Tong & Guohui Lin, 2019. "Single-machine scheduling with job-dependent machine deterioration," Journal of Scheduling, Springer, vol. 22(6), pages 691-707, December.
    20. Özlem Karsu & Meral Azizoğlu, 2014. "Bicriteria multiresource generalized assignment problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 61(8), pages 621-636, December.

    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:eee:ejores:v:307:y:2023:i:2:p:590-603. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.