IDEAS home Printed from https://ideas.repec.org/a/eee/jomega/v115y2023ics0305048322001773.html
   My bibliography  Save this article

Scheduling of Multi-Robot Job Shop Systems in Dynamic Environments: Mixed-Integer Linear Programming and Constraint Programming Approaches

Author

Listed:
  • Fatemi-Anaraki, Soroush
  • Tavakkoli-Moghaddam, Reza
  • Foumani, Mehdi
  • Vahedi-Nouri, Behdin

Abstract

This paper investigates a dynamic scheduling problem within a job shop robotic cell, wherein multiple robotic arms are responsible for material handling in a U-shaped arrangement. Each robotic arm has access to specific workstations based on their distance in the cell layout. Therefore, a part may need to be exchanged between several robots according to its process plan. For this purpose, intermediate buffers are positioned between each pair of consecutive robots. Due to the dynamic nature of the problem, new jobs arrive at unpredictable times, which in turn necessitates rescheduling taking the system’s current state into account. To tackle this problem, firstly, a Mixed-Integer Linear Programming (MILP) model is devised. Secondly, three distinct Speed-up Constraints (SCs) derived from the problem’s inherent characteristics are designed and implemented to accelerate the MILP model’s solving procedure. Afterward, the problem is formulated using Constraint Programming (CP) approach. The performance of the CP model and the MILP model in presence of all possible combinations of the SCs are evaluated and compared through solving various random instances. Next, an analysis is performed on the buffers’ pick-up criterion and how it is affected by the problem’s size. Besides, the impact of changes in the robots’ speed on the productivity of the cell is assessed. Finally, the extent to which the rescheduling priority affects the output of the model is studied.

Suggested Citation

  • Fatemi-Anaraki, Soroush & Tavakkoli-Moghaddam, Reza & Foumani, Mehdi & Vahedi-Nouri, Behdin, 2023. "Scheduling of Multi-Robot Job Shop Systems in Dynamic Environments: Mixed-Integer Linear Programming and Constraint Programming Approaches," Omega, Elsevier, vol. 115(C).
    • Handle: RePEc:eee:jomega:v:115:y:2023:i:c:s0305048322001773
    DOI: 10.1016/j.omega.2022.102770
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0305048322001773
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.omega.2022.102770?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. David Applegate & William Cook, 1991. "A Computational Study of the Job-Shop Scheduling Problem," INFORMS Journal on Computing, INFORMS, vol. 3(2), pages 149-156, May.
    2. Andy Ham, 2021. "Transfer-robot task scheduling in job shop," International Journal of Production Research, Taylor & Francis Journals, vol. 59(3), pages 813-823, February.
    3. Ulrich Dorndorf & Erwin Pesch & Toàn Phan-Huy, 2002. "Constraint Propagation and Problem Decomposition: A Preprocessing Procedure for the Job Shop Problem," Annals of Operations Research, Springer, vol. 115(1), pages 125-145, September.
    4. Che, Ada & Kats, Vladimir & Levner, Eugene, 2017. "An efficient bicriteria algorithm for stable robotic flow shop scheduling," European Journal of Operational Research, Elsevier, vol. 260(3), pages 964-971.
    5. Bukchin, Yossi & Raviv, Tal, 2018. "Constraint programming for solving various assembly line balancing problems," Omega, Elsevier, vol. 78(C), pages 57-68.
    6. Watanabe, Keijiro & Inada, Shuhei, 2020. "Search algorithm of the assembly sequence of products by using past learning results," International Journal of Production Economics, Elsevier, vol. 226(C).
    7. Hashemi-Petroodi, S. Ehsan & Thevenin, Simon & Kovalev, Sergey & Dolgui, Alexandre, 2022. "Model-dependent task assignment in multi-manned mixed-model assembly lines with walking workers," Omega, Elsevier, vol. 113(C).
    8. Nicholas G. Hall & Chelliah Sriskandarajah, 1996. "A Survey of Machine Scheduling Problems with Blocking and No-Wait in Process," Operations Research, INFORMS, vol. 44(3), pages 510-525, June.
    9. Milind W. Dawande & H. Neil Geismar & Suresh P. Sethi & Chelliah Sriskandarajah, 2007. "Throughput Optimization in Robotic Cells," International Series in Operations Research and Management Science, Springer, number 978-0-387-70988-8, December.
    10. Dae-Kyu Kim & Hyun-Jung Kim & Tae-Eog Lee, 2017. "Optimal scheduling for sequentially connected cluster tools with dual-armed robots and a single input and output module," International Journal of Production Research, Taylor & Francis Journals, vol. 55(11), pages 3092-3109, June.
    11. Che, Ada & Chu, Chengbin, 2009. "Multi-degree cyclic scheduling of a no-wait robotic cell with multiple robots," European Journal of Operational Research, Elsevier, vol. 199(1), pages 77-88, November.
    12. Polyakovskiy, Sergey & M’Hallah, Rym, 2021. "Just-in-time two-dimensional bin packing," Omega, Elsevier, vol. 102(C).
    13. Carlier, Jacques & Haouari, Mohamed & Kharbeche, Mohamed & Moukrim, Aziz, 2010. "An optimization-based heuristic for the robotic cell problem," European Journal of Operational Research, Elsevier, vol. 202(3), pages 636-645, May.
    14. Gecili, Hakan & Parikh, Pratik J., 2022. "Joint shelf design and shelf space allocation problem for retailers," Omega, Elsevier, vol. 111(C).
    15. Yujun Yang & Ye Chen & Chuanze Long, 2016. "Flexible robotic manufacturing cell scheduling problem with multiple robots," International Journal of Production Research, Taylor & Francis Journals, vol. 54(22), pages 6768-6781, November.
    16. Lanza, Giacomo & Passacantando, Mauro & Scutellà, Maria Grazia, 2022. "Assigning and sequencing storage locations under a two level storage policy: Optimization model and matheuristic approaches," Omega, Elsevier, vol. 108(C).
    17. Andy Ham, 2020. "Transfer-robot task scheduling in flexible job shop," Journal of Intelligent Manufacturing, Springer, vol. 31(7), pages 1783-1793, October.
    18. Shabtay, Dvir & Arviv, Kfir & Stern, Helman & Edan, Yael, 2014. "A combined robot selection and scheduling problem for flow-shops with no-wait restrictions," Omega, Elsevier, vol. 43(C), pages 96-107.
    19. Che, Ada & Chabrol, Michelle & Gourgand, Michel & Wang, Yuan, 2012. "Scheduling multiple robots in a no-wait re-entrant robotic flowshop," International Journal of Production Economics, Elsevier, vol. 135(1), pages 199-208.
    20. Bock, Felix & Bruhn, Henning, 2021. "Case study on scheduling cyclic conveyor belts," Omega, Elsevier, vol. 102(C).
    21. 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.
    22. Enayaty-Ahangar, Forough & Rainwater, Chase E. & Sharkey, Thomas C., 2019. "A Logic-based Decomposition Approach for Multi-Period Network Interdiction Models," Omega, Elsevier, vol. 87(C), pages 71-85.
    23. Delorme, Maxence & Santini, Alberto, 2022. "Energy-efficient automated vertical farms," Omega, Elsevier, vol. 109(C).
    24. Russell, Robert, 2013. "A constraint programming approach to designing a newspaper distribution system," International Journal of Production Economics, Elsevier, vol. 145(1), pages 132-138.
    25. Che, Ada & Chu, Chengbin & Levner, Eugene, 2003. "A polynomial algorithm for 2-degree cyclic robot scheduling," European Journal of Operational Research, Elsevier, vol. 145(1), pages 31-44, February.
    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. Zhu, Xuedong & Son, Junbo & Zhang, Xi & Wu, Jianguo, 2023. "Constraint programming and logic-based Benders decomposition for the integrated process planning and scheduling problem," Omega, Elsevier, vol. 117(C).
    2. Hosseini, Amir & Otto, Alena & Pesch, Erwin, 2024. "Scheduling in manufacturing with transportation: Classification and solution techniques," European Journal of Operational Research, Elsevier, vol. 315(3), pages 821-843.

    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. Hosseini, Amir & Otto, Alena & Pesch, Erwin, 2024. "Scheduling in manufacturing with transportation: Classification and solution techniques," European Journal of Operational Research, Elsevier, vol. 315(3), pages 821-843.
    2. Allahverdi, Ali, 2016. "A survey of scheduling problems with no-wait in process," European Journal of Operational Research, Elsevier, vol. 255(3), pages 665-686.
    3. Zhu, Xuedong & Son, Junbo & Zhang, Xi & Wu, Jianguo, 2023. "Constraint programming and logic-based Benders decomposition for the integrated process planning and scheduling problem," Omega, Elsevier, vol. 117(C).
    4. Bahman Naderi & Rubén Ruiz & Vahid Roshanaei, 2023. "Mixed-Integer Programming vs. Constraint Programming for Shop Scheduling Problems: New Results and Outlook," INFORMS Journal on Computing, INFORMS, vol. 35(4), pages 817-843, July.
    5. Pisut Pongchairerks, 2019. "A Two-Level Metaheuristic Algorithm for the Job-Shop Scheduling Problem," Complexity, Hindawi, vol. 2019, pages 1-11, March.
    6. Müller, David & Müller, Marcus G. & Kress, Dominik & Pesch, Erwin, 2022. "An algorithm selection approach for the flexible job shop scheduling problem: Choosing constraint programming solvers through machine learning," European Journal of Operational Research, Elsevier, vol. 302(3), pages 874-891.
    7. Carlos Mencía & María Sierra & Ramiro Varela, 2013. "Depth-first heuristic search for the job shop scheduling problem," Annals of Operations Research, Springer, vol. 206(1), pages 265-296, July.
    8. Marco Pranzo & Dario Pacciarelli, 2016. "An iterated greedy metaheuristic for the blocking job shop scheduling problem," Journal of Heuristics, Springer, vol. 22(4), pages 587-611, August.
    9. Shabtay, Dvir & Arviv, Kfir & Stern, Helman & Edan, Yael, 2014. "A combined robot selection and scheduling problem for flow-shops with no-wait restrictions," Omega, Elsevier, vol. 43(C), pages 96-107.
    10. Xin Li & Richard Y. K. Fung, 2016. "Optimal K-unit cycle scheduling of two-cluster tools with residency constraints and general robot moving times," Journal of Scheduling, Springer, vol. 19(2), pages 165-176, April.
    11. Vipul Jain & Ignacio E. Grossmann, 2001. "Algorithms for Hybrid MILP/CP Models for a Class of Optimization Problems," INFORMS Journal on Computing, INFORMS, vol. 13(4), pages 258-276, November.
    12. Lin, Shih-Wei & Ying, Kuo-Ching, 2016. "Optimization of makespan for no-wait flowshop scheduling problems using efficient matheuristics," Omega, Elsevier, vol. 64(C), pages 115-125.
    13. Michael Pinedo & Marcos Singer, 1999. "A shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop," Naval Research Logistics (NRL), John Wiley & Sons, vol. 46(1), pages 1-17, February.
    14. F. Guerriero, 2008. "Hybrid Rollout Approaches for the Job Shop Scheduling Problem," Journal of Optimization Theory and Applications, Springer, vol. 139(2), pages 419-438, November.
    15. Guo, Penghui & Zhu, Jianjun, 2023. "Capacity reservation for humanitarian relief: A logic-based Benders decomposition method with subgradient cut," European Journal of Operational Research, Elsevier, vol. 311(3), pages 942-970.
    16. Kats, Vladimir & Levner, Eugene, 2018. "On the existence of dominating 6-cyclic schedules in four-machine robotic cells," European Journal of Operational Research, Elsevier, vol. 268(2), pages 755-759.
    17. Kats, Vladimir & Levner, Eugene, 2011. "A faster algorithm for 2-cyclic robotic scheduling with a fixed robot route and interval processing times," European Journal of Operational Research, Elsevier, vol. 209(1), pages 51-56, February.
    18. Francis Sourd & Wim Nuijten, 2000. "Multiple-Machine Lower Bounds for Shop-Scheduling Problems," INFORMS Journal on Computing, INFORMS, vol. 12(4), pages 341-352, November.
    19. Yabo Luo, 2017. "Nested optimization method combining complex method and ant colony optimization to solve JSSP with complex associated processes," Journal of Intelligent Manufacturing, Springer, vol. 28(8), pages 1801-1815, December.
    20. Carlier, Jacques & Haouari, Mohamed & Kharbeche, Mohamed & Moukrim, Aziz, 2010. "An optimization-based heuristic for the robotic cell problem," European Journal of Operational Research, Elsevier, vol. 202(3), pages 636-645, May.

    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:jomega:v:115:y:2023:i:c:s0305048322001773. 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/wps/find/journaldescription.cws_home/375/description#description .

    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.