IDEAS home Printed from https://ideas.repec.org/a/taf/tprsxx/v54y2016i16p4773-4792.html
   My bibliography  Save this article

A coloured Petri net-based hybrid heuristic search approach to simultaneous scheduling of machines and automated guided vehicles

Author

Listed:
  • Olatunde T. Baruwa
  • Miquel A. Piera

Abstract

To achieve a significant improvement in the overall performance of a flexible manufacturing system, the scheduling process must consider the interdependencies that exist between the machining and transport systems. However, most works have addressed the scheduling problem as two independent decision making problems, assuming sufficient capacity in the transport system. In this paper, we study the simultaneous scheduling (SS) problem of machines and automated guided vehicles using a timed coloured Petri net (TCPN) approach under two performance objectives; makespan and exit time of the last job. The modelling approach allows the evaluation of all the feasible vehicle assignments as opposed to the traditional dispatching rules and demonstrates the benefits of vehicle-controlled assignments over machine-controlled for certain production scenarios. In contrast with the hierarchical decomposition technique of existing approaches, TCPN is capable of describing the dynamics and evaluating the performance of the SS problem in a single model. Based on TCPN modelling, SS is performed using a hybrid heuristic search algorithm to find optimal or near-optimal schedules by searching through the reachability graph of the TCPN with heuristic functions. Large-sized instances are solved in relatively short computation times, which were a priori unsolvable with conventional search algorithms. The algorithm’s performance is evaluated on a benchmark of 82 test problems. Experimental results indicate that the proposed algorithm performs better than the conventional ones and compares favourably with other approaches.

Suggested Citation

  • Olatunde T. Baruwa & Miquel A. Piera, 2016. "A coloured Petri net-based hybrid heuristic search approach to simultaneous scheduling of machines and automated guided vehicles," International Journal of Production Research, Taylor & Francis Journals, vol. 54(16), pages 4773-4792, August.
  • Handle: RePEc:taf:tprsxx:v:54:y:2016:i:16:p:4773-4792
    DOI: 10.1080/00207543.2015.1087656
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1080/00207543.2015.1087656
    Download Restriction: Access to full text is restricted to subscribers.

    File URL: https://libkey.io/10.1080/00207543.2015.1087656?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. Ümit Bilge & Gündüz Ulusoy, 1995. "A Time Window Approach to Simultaneous Scheduling of Machines and Material Handling System in an FMS," Operations Research, INFORMS, vol. 43(6), pages 1058-1070, December.
    2. Hurink, Johann & Knust, Sigrid, 2005. "Tabu search algorithms for job-shop problems with a single transport robot," European Journal of Operational Research, Elsevier, vol. 162(1), pages 99-111, April.
    3. Lacomme, Philippe & Larabi, Mohand & Tchernev, Nikolay, 2013. "Job-shop based framework for simultaneous scheduling of machines and automated guided vehicles," International Journal of Production Economics, Elsevier, vol. 143(1), pages 24-34.
    4. Khayat, Ghada El & Langevin, Andre & Riopel, Diane, 2006. "Integrated production and material handling scheduling using mathematical programming and constraint programming," European Journal of Operational Research, Elsevier, vol. 175(3), pages 1818-1832, December.
    5. Caumond, A. & Lacomme, P. & Moukrim, A. & Tchernev, N., 2009. "An MILP for scheduling problems in an FMS with one vehicle," European Journal of Operational Research, Elsevier, vol. 199(3), pages 706-722, December.
    6. Piera, M.A. & Mušič, G., 2011. "Coloured Petri net scheduling models: Timed state space exploration shortages," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 82(3), pages 428-441.
    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. Grzegorz Bocewicz & Zbigniew Banaszak & Izabela Nielsen, 2019. "Multimodal processes prototyping subject to grid-like network and fuzzy operation time constraints," Annals of Operations Research, Springer, vol. 273(1), pages 561-585, February.
    2. Dalila B. M. M. Fontes & Seyed Mahdi Homayouni, 2019. "Joint production and transportation scheduling in flexible manufacturing systems," Journal of Global Optimization, Springer, vol. 74(4), pages 879-908, August.
    3. 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.
    4. Moussa Abderrahim & Abdelghani Bekrar & Damien Trentesaux & Nassima Aissani & Karim Bouamrane, 2020. "Manufacturing 4.0 Operations Scheduling with AGV Battery Management Constraints," Energies, MDPI, vol. 13(18), pages 1-19, September.
    5. Fontes, Dalila B.M.M. & Homayouni, S. Mahdi & Gonçalves, José F., 2023. "A hybrid particle swarm optimization and simulated annealing algorithm for the job shop scheduling problem with transport resources," European Journal of Operational Research, Elsevier, vol. 306(3), pages 1140-1157.
    6. Wenxiang Xu & Shunsheng Guo, 2019. "A Multi-Objective and Multi-Dimensional Optimization Scheduling Method Using a Hybrid Evolutionary Algorithms with a Sectional Encoding Mode," Sustainability, MDPI, vol. 11(5), pages 1-24, March.
    7. Andy Ham, 2020. "Transfer-robot task scheduling in flexible job shop," Journal of Intelligent Manufacturing, Springer, vol. 31(7), pages 1783-1793, October.

    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. Dalila B. M. M. Fontes & Seyed Mahdi Homayouni, 2019. "Joint production and transportation scheduling in flexible manufacturing systems," Journal of Global Optimization, Springer, vol. 74(4), pages 879-908, August.
    2. Arash Amirteimoori & Reza Kia, 2023. "Concurrent scheduling of jobs and AGVs in a flexible job shop system: a parallel hybrid PSO-GA meta-heuristic," Flexible Services and Manufacturing Journal, Springer, vol. 35(3), pages 727-753, September.
    3. Fontes, Dalila B.M.M. & Homayouni, S. Mahdi & Gonçalves, José F., 2023. "A hybrid particle swarm optimization and simulated annealing algorithm for the job shop scheduling problem with transport resources," European Journal of Operational Research, Elsevier, vol. 306(3), pages 1140-1157.
    4. Lacomme, Philippe & Larabi, Mohand & Tchernev, Nikolay, 2013. "Job-shop based framework for simultaneous scheduling of machines and automated guided vehicles," International Journal of Production Economics, Elsevier, vol. 143(1), pages 24-34.
    5. Reinhard Bürgy & Heinz Gröflin, 2016. "The blocking job shop with rail-bound transportation," Journal of Combinatorial Optimization, Springer, vol. 31(1), pages 152-181, January.
    6. Philippe Lacomme & Aziz Moukrim & Alain Quilliot & Marina Vinot, 2019. "Integration of routing into a resource-constrained project scheduling problem," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 7(4), pages 421-464, December.
    7. James T. Lin & Chun-Chih Chiu & Edward Huang & Hung-Ming Chen, 2018. "A Multi-Fidelity Model Approach for Simultaneous Scheduling of Machines and Vehicles in Flexible Manufacturing Systems," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 35(01), pages 1-20, February.
    8. Sun, Yige & Chung, Sai-Ho & Wen, Xin & Ma, Hoi-Lam, 2021. "Novel robotic job-shop scheduling models with deadlock and robot movement considerations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 149(C).
    9. Chen, Lu & Langevin, André & Lu, Zhiqiang, 2013. "Integrated scheduling of crane handling and truck transportation in a maritime container terminal," European Journal of Operational Research, Elsevier, vol. 225(1), pages 142-152.
    10. Marie-Laure Espinouse & Grzegorz Pawlak & Malgorzata Sterna, 2017. "Complexity of Scheduling Problem in Single-Machine Flexible Manufacturing System with Cyclic Transportation and Unlimited Buffers," Journal of Optimization Theory and Applications, Springer, vol. 173(3), pages 1042-1054, June.
    11. James T. Lin & Chun-Chih Chiu & Yu-Hsiang Chang, 2019. "Simulation-based optimization approach for simultaneous scheduling of vehicles and machines with processing time uncertainty in FMS," Flexible Services and Manufacturing Journal, Springer, vol. 31(1), pages 104-141, March.
    12. Moussa Abderrahim & Abdelghani Bekrar & Damien Trentesaux & Nassima Aissani & Karim Bouamrane, 2020. "Manufacturing 4.0 Operations Scheduling with AGV Battery Management Constraints," Energies, MDPI, vol. 13(18), pages 1-19, September.
    13. Quang-Vinh Dang & Cong Thanh Nguyen & Hana Rudová, 2019. "Scheduling of mobile robots for transportation and manufacturing tasks," Journal of Heuristics, Springer, vol. 25(2), pages 175-213, April.
    14. Torres, Isidro Ramos & Romero Dessens, Luis Felipe & Martínez Flores, José Luis & Olivares Benítez, Elías, 2015. "Review of Comprehensive Approaches in Optimizing AGV Systems," Chapters from the Proceedings of the Hamburg International Conference of Logistics (HICL), in: Blecker, Thorsten & Kersten, Wolfgang & Ringle, Christian M. (ed.), Operational Excellence in Logistics and Supply Chains: Optimization Methods, Data-driven Approaches and Security Insights. Proceedings of the Hamburg , volume 22, pages 203-232, Hamburg University of Technology (TUHH), Institute of Business Logistics and General Management.
    15. Jianxun Li & Wenjie Cheng & Kin Keung Lai & Bhagwat Ram, 2022. "Multi-AGV Flexible Manufacturing Cell Scheduling Considering Charging," Mathematics, MDPI, vol. 10(19), pages 1-15, September.
    16. Rossi, Andrea, 2014. "Flexible job shop scheduling with sequence-dependent setup and transportation times by ant colony with reinforced pheromone relationships," International Journal of Production Economics, Elsevier, vol. 153(C), pages 253-267.
    17. Xiangtong Qi, 2005. "A logistics scheduling model: Inventory cost reduction by batching," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(4), pages 312-320, June.
    18. Bürgy, Reinhard & Bülbül, Kerem, 2018. "The job shop scheduling problem with convex costs," European Journal of Operational Research, Elsevier, vol. 268(1), pages 82-100.
    19. 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.
    20. Le-Anh, T. & de Koster, M.B.M., 2004. "A Review Of Design And Control Of Automated Guided Vehicle Systems," ERIM Report Series Research in Management ERS;2004-030-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.

    More about this item

    Statistics

    Access and download statistics

    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:taf:tprsxx:v:54:y:2016:i:16:p:4773-4792. 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: Chris Longhurst (email available below). General contact details of provider: http://www.tandfonline.com/TPRS20 .

    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.