|
Abstract:
The paper presents the new algorithm for solving one problem from the scheduling theory. The method is based on the principle of graph coloring and allows simultaneous processing of several details in one workplace. The problems of scheduling theory are briefly analyzed and the place of the given problem is determined within the general classification of problems. The scheduling algorithm and the program on the basis of it have been developed to solve this problem for various optimality criteria. Two versions of the program have been implemented. The first one follows directly the data structures and the sequence of actions of the graph coloring method. In the second version, the structures of the linear representation of the graph are used, as well as multi-step operations are introduced, which made it possible to increase the efficiency of the scheduling algorithm. The time characteristics of the program execution on a different number of details for two versions of the program are given. The prospects for the development of the program and the scope of its application are discussed and could be rather wide, from agribusiness, such as optimizing the production of meat products, to manufacturing enterprises with a significant range of product line.
Keywords:
graph theory; scheduling theory; graph coloring; scheduling algorithm.
Стр. 123-132.
DOI 10.14357/20718632230112 References
1. Kochkarov, R. Multicriteria Optimization Problem on Prefractal Graph. Mathematics 2022, 10, 930. Https://doi.org/10.3390/math10060930. 2. Kochkarov, R. Research of NP-Complete Problems in the Class of Prefractal Graphs. Mathematics 2021, 9, 2764. Https://doi.org/10.3390/math9212764. 3. Dogadina, E.P.; Smirnov, M.V.; Osipov, A.V.; Suvorov, S.V. Evaluation of the forms of education of high school students using a hybrid model based on various optimization methods and a neural network. Informatics 2021, 8, 46. 4. Osipov, A.; Filimonov, A.; Suvorov S. Applying Machine Learning Techniques to Identify Damaged Potatoes. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). In Proceedings of the LNCS, 20th International Conference on Artificial Intelligence and Soft Computing, ICAISC 2021, Virtual, Online, 21-23 June 2021 DOI 10.1007/978-3-030-87986-0_17. 5. Pavlyutin, M.; Samoyavcheva, M.; Kochkarov, R.; Pleshakova, E.; Korchagin, S.; Gataullin, T.; Nikitin, P.; Hidirova, M. COVID-19 Spread Forecasting, Mathematical Methods vs. Machine Learning, Moscow Case. Mathematics 2022, 10, 195. Https://doi.org/10.3390/math10020195 6. Soloviev, V. Fintech Ecosystem in Russia. In Proceedings of the 2018 11th International Conference; Management of Large-Scale System Development, MLSD, Moscow, Russia, 1–3 October 2018. 10.13187/mlsd.2018.855180810. 7. Ivanyuk, V. Formulating the concept of an investment strategy adaptable to changes in the market situation. Economies 2021, 9, 95. 10.3390/economies9030095 8. Andriyanov, N.; Khasanshin, I.; Utkin, D.; Gataullin, T.; Ignar, S.; Shumaev, V.; Soloviev, V. Intelligent System for Estimation of the Spatial Position of Apples Based on yolov3 and Real Sense Depth Camera D415. Symmetry 2022, 14, 148. 9. Andriyanov, N.A., Dementiev, V.E., Tashlinskiy, A.G. Detection of objects in the images: from likelihood relationships toward scalable and efficient neural networks. Computer Optics 2022, Vol. 46(1). DOI: 10.18287/2412-6179-CO-922. 10. Wu, Kan; Shen, Yichi .A unified view on planning, scheduling and dispatching for a factory. Advanced Engineering Informatics 2020, 46, 101188. 10.1016/j.aei.2020.101188. 11. Zhou, Tong; Tang, Dunbing; Zhu, Haihua; Zhang, Zequn. Multi-agent reinforcement learning for online scheduling in smart factories. Robotics and Computer-Integrated Manufacturing 2021, 72, 102202. 10.1016/j.rcim.2021.102202. 12. Luo, Qiang; Deng, Qianwang; Gong, Guiliang; Zhang, Like; Han, Wenwu; Li, Kexin. An efficient memetic algorithm for distributed flexible job shop scheduling problem with transfers. Expert Systems with Applications 2020, 160, 113721. 10.1016/j.eswa.2020.113721. 13. Li, Haoran; Li, Xinyu; Gao, Liang. A discrete artificial bee colony algorithm for the distributed heterogeneous no-wait flowshop scheduling problem. Applied Soft Computing 2021, 100, 106946. 10.1016/j.asoc.2020.106946. 14. Zhou, Bin; Bao, Jinsong; Li, Jie; Lu, Yuqian; Liu, Tianyuan; Zhang, Qiwan. A novel knowledge graph-based optimization approach for resource allocation in discrete manufacturing workshops. Robotics and ComputerIntegrated Manufacturing 2021, 71, 102160. 10.1016/j.rcim.2021.102160. 15. Lu, Houjun; Wang, Sai. A study on multi-ASC scheduling method of automated container terminals based on graph theory. Computers & Industrial Engineering 2019, 129, 404-416. 10.1016/j.cie.2019.01.050. 16. Garey, M.R.; Johnson, D.S.; Sethi, Ravi. The Complexity of Flowshop and Jobshop Scheduling. Mathematics of Operations Research 1976, 1, 2, 117-129. 17. The Scheduling Zoo. Available online: http://wwwdesir.lip6.fr/~durrc/query/ (accessed 25 November 2021) 18. Korovin, D.I. Logical principles in organization of production. Ivanovo State University: Ivanovo, 2006. 19. Shaw, A. The Logical Design of Operating System. PRENTICE-HALL, INC. ENGLEWOOD CLIFFS: N.J. 1974. 20. Liu, Q.; Shao, X.; Yang, J.-P.; Zhang, J.-S. Multiscale modeling and collaborative manufacturing for steelmaking plants. Chinese Journal of Engineering 2021, 43 (12), 1698-1712. 21. Wang,B.; Liu, F.; Lin, W.; Ma, Z.; Xu, D. Energyefficient collaborative optimization for VM scheduling in cloud computing. Computer Networks 2021, 201, № 108565. 22. Unsal, O. An extended formulation of moldable task scheduling problem and its application to quay crane assignments. Expert Systems with Applications 2021, 185, № 115617. 23. Lin, Y.; Miao, S.; Yang, W.; Yin, B.; Tu, Q.; Ye, C. Dayahead optimal scheduling strategy of virtual power plant for environment with multiple uncertainties. Electric Power Automation Equipment 2021, 41 (12), 143-150. 24. Zheng, X.; Liang, S.; Xiong, X. A hardware/software partitioning method based on graph convolution network. Design Automation for Embedded Systems 2021, 25 (4), 325-351. 25. Huang, Y.: Xu, H.; Gao, H.: Ma, X.; Hussein, W. SSUR: An Approach to Optimizing Virtual Machine Allocation Strategy Based on User Requirements for Cloud Data Center. IEEE Transactions on Green Communications and Networking 2021, 5(2), 670-681. DOI: 10.1109/TGCN.2021.3067374. 26. Ma, X.; Xu, H.; Gao, H.; Bian M. Real-time Multiple-Workflow Scheduling in Cloud Environments. IEEE Transactions on Network and Service Management( TNSM) 2021, 18(4), 4002-4018. DOI: 10.1109/TNSM.2021.3125395.
|
