A Method in Constructing a No-Waits and No-Interruptions Periodic Schedule for the Transport Robots of the Flexible Automatic Lines

Abstract

Mathematical simulation makes it possible to find optimal solutions to various manufacture problems. An important class of such problems includes scheduling, which involves allocating limited resources in production operations and is related to the discrete optimization problems. Particularly important is efficient scheduling of the expensive equipment, such as the flexible production lines widely used in the industries to improve productivity, flexibility, and safety in manufacture. Managing them raises a variety of complex scheduling issues. The paper considers a problem of constructing a periodic schedule for the flexible automated production line with multiple robots ensuring its no-waits and no-interruptions. The objective lies in finding a periodic schedule for the robots that minimizes the cycle time. Unlike studies that impose the artificial and simplified operating conditions for an automated line, the paper accounts for the real-world requirements, such as robots moving along a single path and avoiding collisions. It proposes a modification to the prohibited interval method in constructing schedules with several robots. The new model provides efficient schedules for the real-world manufacture systems. A numerical example is presented to demonstrate the new method

Please cite this article in English as:

Ptuskin A.S. A method in constructing a no-waits and no-interruptions periodic schedule for the transport robots of the flexible automatic lines. Herald of the Bauman Moscow State Technical University, Series Natural Sciences, 2025, no. 5 (122), pp. 24--40 (in Russ.). EDN: TYIGHH

References

[1] Abd K.K. Intelligent scheduling of robotic flexible assembly cells. Springer Theses. Cham, Springer, 2015. DOI: https://doi.org/10.1007/978-3-319-26296-3

[2] Levner E., Vishnevsky V. Recent advances in scheduling theory and applications in robotics and communications. In: Vishnevskiy V.M., Samouylov K.E., Kozyrev D.V. (eds). Distributed Computer and Communication Networks. DCCN 2021. Lecture Notes in Computer Science, vol. 13144. Cham, Springer, 2021, pp. 14--23. DOI: https://doi.org/10.1007/978-3-030-92507-9_2

[3] Pinedo M.L. Planning and scheduling in manufacturing and services. New York, NY, Springer, 2005. DOI: https://doi.org/10.1007/978-1-4419-0910-7

[4] Laajili E., Lamrous S., Manier M.-A., et al. An Adapted Variable Neighborhood Search based algorithm for the cyclic multi-hoist design and scheduling problem. Comput. Indust. Eng., 2021, vol. 157, art. 107225. DOI: https://doi.org/10.1016/j.cie.2021.107225

[5] Gultekin H., Coban B., Akhlaghi V.E. Cyclic scheduling of parts and robot moves in m-machine robotic cells. Comput. Oper. Res., 2018, vol. 90, pp. 161--172. DOI: https://doi.org/10.1016/j.cor.2017.09.018

[6] Clossen R.J., Malstrom E.M. Effective capacity planning for automated factories requires workable simulation tools and responsive shop floor control. Industrial Engineering, 1982, vol. 15, pp. 73--79.

[7] Garcia-Mata C.L., Marquez-Gutierrez P.R., Burtseva L. Rescheduling in industrial environments: emerging technologies and forthcoming trends. IJCOPI, 2015, vol. 6, no. 3, pp. 34--48.

[8] Pinedo M.L. Scheduling: theory, algorithms, and systems. Cham, Springer, 2022. DOI: https://doi.org/10.1007/978-3-031-05921-6

[9] Manier M.-A., Bloch C.A. Classification for hoist scheduling problems. Int. J. Flex. Manuf. Syst., 2003, vol. 15, no. 1, pp. 37--55. DOI: https://doi.org/10.1023/A:1023952906934

[10] Perez-Rodriguez R. Simulation optimization for the multihoist scheduling problem. Appl. Comput. Intell. Soft Comput., 2021, vol. 2021, no. 1. DOI: https://doi.org/10.1155/2021/6639769

[11] Bagchi T.P., Gupta J.N.D., Sriskandarajah C. A review of TSP based approaches for flowshop scheduling. Eur. J. Oper. Res., 2006, vol. 169, iss. 3, pp. 816--854. DOI: https://doi.org/10.1016/j.ejor.2004.06.040

[12] Lamothe, J., Correge M., Delmas J. Hoist scheduling problem in a real time context. In: 11th International Conference on Analysis and Optimization of Systems Discrete Event Systems. Lecture Notes in Control and Information Sciences, vol. 199. Berlin, Heidelberg, Springer, 1994, pp. 586--592. DOI: https://doi.org/10.1007/BFb0033591

[13] Lamothe, J., Correge M., Delmas J. Hoist scheduling problem in a real time context. In: 11th International Conference on Analysis and Optimization of Systems Discrete Event Systems. Lecture Notes in Control and Information Sciences, vol. 199. Berlin, Heidelberg, Springer, 1994, pp. 586--592. DOI: https://doi.org/10.1007/BFb0033591

[14] Ramin D., Fraizzoli D., Ballarino A., et al. Dynamic hoist scheduling for multi-recipe and multi-stage production lines: a logical framework. SSRN, 2022. DOI: https://doi.org/10.2139/ssrn.4105670

[15] Levner E., Kats V., Levit V.E. An improved algorithm for cyclic flowshop scheduling in a robotic cell. Eur. J. Oper. Res., 1997, vol. 97, iss. 3, pp. 500--508. DOI: https://doi.org/10.1016/S0377-2217(96)00272-X

[16] Kats V., Levner E. Cyclic flowshop scheduling with operators and robots: Vyacheslav Tanaev’s vision and lasting contributions. J. Sched., 2012, vol. 15, no. 4, pp. 419--425. DOI: https://doi.org/10.1007/s10951-010-0221-x

[17] Tanaev B.C. On the problem of scheduling a production line with one operator. Inzhenerno-fizicheskiy zhurnal, 1964, no. 3, pp. 111--114 (in Russ.).

[18] Karzanov A.V., Lifshits E.M. On the minimal number of operators in serving a uniform linear process. Autom. Remote Control, 1978, vol. 39, no. 3, pp. 445--450.

[19] Livshits E.M., Mikhayletskiy Z.N. On the optimal multi-operator cyclic process of servicing a flow line. Upravlyayushchie sistemy i mashiny, 1980, no. 3, pp. 187--190 (in Russ.).

[20] Kats V., Levner E. Cyclic scheduling in a robotic production line. J. Sched., 2002, vol. 5, no. 1, pp. 23--41. DOI: https://doi.org/10.1002/jos.92

[21] Leung J.M.Y., Zhang G., Yang X., et al. Optimal cyclic multi-hoist scheduling: a mixed integer programming approach. Oper. Res., 2004, vol. 52, no. 6, pp. 965--976. DOI: https://doi.org//10.1287/opre.1040.0144

[22] Levner E., Meyzin L., Ptuskin A. Periodic scheduling of a transporting robot under incomplete input data: a fuzzy approach. Fuzzy Sets Syst., 1998, vol. 98, iss. 3, pp. 255--266. DOI: https://doi.org/10.1016/S0165-0114(96)00387-9

[23] Ptuskin A.S. No-wait periodic scheduling of non-identical parts in flexible manufacturing lines with fuzzy processing times. Int. Workshop on Intelligent Scheduling of Robots and Flexible Manufacturing Systems. Center for Technological Education Holon, 1995, pp. 210--222.

[24] Ptuskin A., Levner E., Kats V. Cyclic multi-hoist scheduling with fuzzy processing times in flexible manufacturing lines. Appl. Soft Comput., 2024, vol. 165, art. 112014. DOI: https://doi.org/10.1016/j.asoc.2024.112014

[25] Kleyner G.B. Economic and mathematical modeling and economic theory. Ekonomika i matematicheskie metody [Economics and Mathematical Methods], 2001, vol. 37, no. 3, pp. 111--126. EDN: VUPJQD