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

Scheduling robotic cells with fixed processing times or time windows: Classification, solution approaches, polynomial algorithms and complexity

Author

Listed:
  • Feng, Jianguang
  • Che, Ada
  • Chu, Chengbin
  • Levner, Eugene
  • Kats, Vladimir

Abstract

Robotic cell scheduling has received considerable attention from researchers. Several existing review papers have presented then-existing studies on robotic cell scheduling and related fields from different perspectives. Since the latest review, numerous new results have emerged, contributing significant advancements in recent years. Furthermore, certain features of these problems have not been appropriately addressed. This paper aims to provide an up-to-date review and present our particular perspectives to address recent publications on scheduling robotic cells with fixed processing times or time windows. First, we identify various characteristics of robotic cell scheduling and explain their impact on the structure and complexity. Based on these characteristics, the related robotic cell scheduling studies are classified and compared in various dimensions. Second, we present complexity results, along with both exact and approximation solution techniques, for the robotic cell scheduling problem with time windows or fixed processing times. These results are presented in tabular forms to visually reveal the relationships between different problem configurations and their respective solution approaches. Finally, we discern emerging trends in the realm of robotic cell scheduling research, subsequently indicating prospective directions for future investigations.

Suggested Citation

  • Feng, Jianguang & Che, Ada & Chu, Chengbin & Levner, Eugene & Kats, Vladimir, 2024. "Scheduling robotic cells with fixed processing times or time windows: Classification, solution approaches, polynomial algorithms and complexity," European Journal of Operational Research, Elsevier, vol. 319(2), pages 468-483.
    • Handle: RePEc:eee:ejores:v:319:y:2024:i:2:p:468-483
    DOI: 10.1016/j.ejor.2024.01.041
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221724000821
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2024.01.041?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. Daniel Riera & Neil Yorke-Smith, 2002. "An Improved Hybrid Model for the Generic Hoist Scheduling Problem," Annals of Operations Research, Springer, vol. 115(1), pages 173-191, September.
    2. Weidong Lei & Ada Che & Chengbin Chu, 2014. "Optimal cyclic scheduling of a robotic flowshop with multiple part types and flexible processing times," European Journal of Industrial Engineering, Inderscience Enterprises Ltd, vol. 8(2), pages 143-167.
    3. SubaI, Corinne & Baptiste, Pierre & Niel, Eric, 2006. "Scheduling issues for environmentally responsible manufacturing: The case of hoist scheduling in an electroplating line," International Journal of Production Economics, Elsevier, vol. 99(1-2), pages 74-87, February.
    4. Sun, T. C. & Lai, K. K. & Lam, Kokin & So, K. P., 1994. "A study of heuristics for bidirectional multi-hoist production scheduling systems," International Journal of Production Economics, Elsevier, vol. 33(1-3), pages 207-214, January.
    5. Zhili Zhou & Ling Li, 2009. "A solution for cyclic scheduling of multi-hoists without overlapping," Annals of Operations Research, Springer, vol. 168(1), pages 5-21, April.
    6. Che, Ada & Feng, Jianguang & Chen, Haoxun & Chu, Chengbin, 2015. "Robust optimization for the cyclic hoist scheduling problem," European Journal of Operational Research, Elsevier, vol. 240(3), pages 627-636.
    7. 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.
    8. Adnen El Amraoui & Marie-Ange Manier & Abdellah El Moudni & Mohamed Benrejeb, 2012. "Resolution of the two-part cyclic hoist scheduling problem with bounded processing times in complex lines' configuration," European Journal of Industrial Engineering, Inderscience Enterprises Ltd, vol. 6(4), pages 454-473.
    9. 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.
    10. Lei Lei & Tzyh-Jong Wang, 1991. "The Minimum Common-Cycle Algorithm for Cyclic Scheduling of Two Material Handling Hoists with Time Window Constraints," Management Science, INFORMS, vol. 37(12), pages 1629-1639, December.
    11. Vladimir Kats & Eugene Levner, 1997. "Minimizing the number of robots to meet a given cyclic schedule," Annals of Operations Research, Springer, vol. 69(0), pages 209-226, January.
    12. 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.
    13. 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.
    14. Armstrong, Ronald & Lei, Lei & Gu, Shanhong, 1994. "A bounding scheme for deriving the minimal cycle time of a single-transporter N-stage process with time-window constraints," European Journal of Operational Research, Elsevier, vol. 78(1), pages 130-140, October.
    15. Paul, Henrik J. & Bierwirth, Christian & Kopfer, Herbert, 2007. "A heuristic scheduling procedure for multi-item hoist production lines," International Journal of Production Economics, Elsevier, vol. 105(1), pages 54-69, January.
    16. Y. Crama & V. Kats & J. van de Klundert & E. Levner, 2000. "Cyclic scheduling in robotic flowshops," Annals of Operations Research, Springer, vol. 96(1), pages 97-124, November.
    17. Janny M. Y. Leung & Guoqing Zhang & Xiaoguang Yang & Raymond Mak & Kokin Lam, 2004. "Optimal Cyclic Multi-Hoist Scheduling: A Mixed Integer Programming Approach," Operations Research, INFORMS, vol. 52(6), pages 965-976, December.
    18. Yun Jiang & Jiyin Liu, 2014. "A new model and an efficient branch-and-bound solution for cyclic multi-hoist scheduling," IISE Transactions, Taylor & Francis Journals, vol. 46(3), pages 249-262.
    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. Chauvet, Fabrice & Levner, Eugene & Meyzin, Leonid K. & Proth, Jean-Marie, 2000. "On-line scheduling in a surface treatment system," European Journal of Operational Research, Elsevier, vol. 120(2), pages 382-392, January.
    21. 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.
    22. Alcaide, David & Chu, Chengbin & Kats, Vladimir & Levner, Eugene & Sierksma, Gerard, 2007. "Cyclic multiple-robot scheduling with time-window constraints using a critical path approach," European Journal of Operational Research, Elsevier, vol. 177(1), pages 147-162, February.
    23. 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.
    24. Agnetis, A., 2000. "Scheduling no-wait robotic cells with two and three machines," European Journal of Operational Research, Elsevier, vol. 123(2), pages 303-314, June.
    25. Cheng-Chung Cheng & Stephen Smith, 1997. "Applying constraint satisfaction techniques to job shop scheduling," Annals of Operations Research, Springer, vol. 70(0), pages 327-357, April.
    26. Jiyin Liu & Yun Jiang, 2005. "An Efficient Optimal Solution to the Two-Hoist No-Wait Cyclic Scheduling Problem," Operations Research, INFORMS, vol. 53(2), pages 313-327, April.
    27. Levner, Eugene & Kats, Vladimir & Levit, Vadim E., 1997. "An improved algorithm for cyclic flowshop scheduling in a robotic cell," European Journal of Operational Research, Elsevier, vol. 97(3), pages 500-508, March.
    28. Kats, Vladimir & Lei, Lei & Levner, Eugene, 2008. "Minimizing the cycle time of multiple-product processing networks with a fixed operation sequence, setups, and time-window constraints," European Journal of Operational Research, Elsevier, vol. 187(3), pages 1196-1211, June.
    29. R. Rodosek & M.G. Wallace & M.T. Hajian, 1999. "A new approach to integrating mixed integer programming and constraint logicprogramming," Annals of Operations Research, Springer, vol. 86(0), pages 63-87, January.
    30. Chung-Yee Lee & Lei Lei & Michael Pinedo, 1997. "Current trends in deterministic scheduling," Annals of Operations Research, Springer, vol. 70(0), pages 1-41, April.
    Full references (including those not matched with items on IDEAS)

    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. 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.
    2. 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.
    3. Che, Ada & Feng, Jianguang & Chen, Haoxun & Chu, Chengbin, 2015. "Robust optimization for the cyclic hoist scheduling problem," European Journal of Operational Research, Elsevier, vol. 240(3), pages 627-636.
    4. Janny M. Y. Leung & Guoqing Zhang & Xiaoguang Yang & Raymond Mak & Kokin Lam, 2004. "Optimal Cyclic Multi-Hoist Scheduling: A Mixed Integer Programming Approach," Operations Research, INFORMS, vol. 52(6), pages 965-976, December.
    5. 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.
    6. 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).
    7. 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.
    8. Milind Dawande & Michael Pinedo & Chelliah Sriskandarajah, 2009. "Multiple Part-Type Production in Robotic Cells: Equivalence of Two Real-World Models," Manufacturing & Service Operations Management, INFORMS, vol. 11(2), pages 210-228, February.
    9. Neil Geismar, H. & Dawande, Milind & Sriskandarajah, Chelliah, 2005. "Approximation algorithms for k-unit cyclic solutions in robotic cells," European Journal of Operational Research, Elsevier, vol. 162(2), pages 291-309, April.
    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. Paul, Henrik J. & Bierwirth, Christian & Kopfer, Herbert, 2007. "A heuristic scheduling procedure for multi-item hoist production lines," International Journal of Production Economics, Elsevier, vol. 105(1), pages 54-69, January.
    12. Jiyin Liu & Yun Jiang, 2005. "An Efficient Optimal Solution to the Two-Hoist No-Wait Cyclic Scheduling Problem," Operations Research, INFORMS, vol. 53(2), pages 313-327, April.
    13. 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.
    14. 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.
    15. Drobouchevitch, Inna G. & Neil Geismar, H. & Sriskandarajah, Chelliah, 2010. "Throughput optimization in robotic cells with input and output machine buffers: A comparative study of two key models," European Journal of Operational Research, Elsevier, vol. 206(3), pages 623-633, November.
    16. Hanen, Claire & Hanzalek, Zdenek, 2020. "Grouping tasks to save energy in a cyclic scheduling problem: A complexity study," European Journal of Operational Research, Elsevier, vol. 284(2), pages 445-459.
    17. Drobouchevitch, Inna G. & Sethi, Suresh P. & Sriskandarajah, Chelliah, 2006. "Scheduling dual gripper robotic cell: One-unit cycles," European Journal of Operational Research, Elsevier, vol. 171(2), pages 598-631, June.
    18. Tharanga Rajapakshe & Milind Dawande & Chelliah Sriskandarajah, 2011. "Quantifying the Impact of Layout on Productivity: An Analysis from Robotic-Cell Manufacturing," Operations Research, INFORMS, vol. 59(2), pages 440-454, April.
    19. Chelliah Sriskandarajah & Inna Drobouchevitch & Suresh P. Sethi & Ramaswamy Chandrasekaran, 2004. "Scheduling Multiple Parts in a Robotic Cell Served by a Dual-Gripper Robot," Operations Research, INFORMS, vol. 52(1), pages 65-82, February.
    20. Bagchi, Tapan P. & Gupta, Jatinder N.D. & Sriskandarajah, Chelliah, 2006. "A review of TSP based approaches for flowshop scheduling," European Journal of Operational Research, Elsevier, vol. 169(3), pages 816-854, March.

    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:319:y:2024:i:2:p:468-483. 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.