Currently, managing computing resources in modern distributed computing systems is the relevant problem. As a result of infrastructure capability evolution, distributed computing can be organized in dynamic, heterogeneous and geographically distributed computing environments, examples of which are “fog” and “edge” ones. The dynamics of both load and topology imply the need to change the system configuration, namely, assigning user tasks to computing devices with the allocation of the necessary resources. The latter raises the issue of increasing the efficiency of the scheduler (broker), which facilitates management of network resources within the allocated fragment. Algorithmic and software schedulers are based on models and methods of scheduling theory and implement either simple heuristics, mathematical programming methods or metaheuristics. However, an analysis of publicly available problem statements has shown that, firstly, they are special cases and implement certain situations of computing resource distribution, and secondly, they do not fully reflect the properties of heterogeneity, geographical distribution and dynamics of computing environments. As part of this study, a general model of computing resource allocation problem is proposed with consideration to the listed properties, and a solution method using the subject ontology of metaheuristic methods is proposed. The feasibility of constructing and applying an ontology is shown using the example of analyzing the effectiveness of genetic algorithms depending on the values of the computing resource allocation problem parameters which is being solved.
1. Pinedo M.L. Planning and Scheduling in Manufacturing and Services. 2nd ed. New York, NY: Springer; 2014. 536 p.
2. Han X., Iwama K., Ye D., Zhang G. Strip packing vs. Bin packing. В сборнике: Third International Conference on Algorithmic Aspects in Information and Management (AAIM’07), 6–8 July 2007, Portland, Oregon, USA. Heidelberg: Springer; 2007. p. 358–367.
3. Burcea M., Wong P.W.H., Yung F.C.C. Online Multi-dimensional Dynamic Bin Packing of Unit-Fraction Items. In: CIAC 2013: 8th International Conference on Algorithms and Complexity, 22–24 May 2013, Barcelona, Spain. Heidelberg: Springer; 2013. p. 85–96.
4. Toporkov V.V. Modely rspredelennih vychisleniy. Moscow, FIZMATLIT; 2004. 320 p. (In Russ.).
5. Shaji George A., Hovan George A.S., Baskar T. Edge computing and the future of cloud computing: a survey of industry perspectives and predictions. Partners Universal International Research Journal (PUIRJ). 2023;2(2):19–44. DOI: 10.5281/zenodo.8020101.
6. Shaji George A., Hovan George A.S., Baskar T. Unshackled by servers: embracing the serverless revolution in modern computing. Partners Universal International Research Journal (PUIRJ). 2023;2(2):229–240. DOI: 10.5281/zenodo.8051052.
7. Brando V., Lovell J., King E., Boadle D., Scott R., Schroeder T. The potential of autonomous ship-borne hyperspectral radiometers for the validation of ocean color radiometry data. Remote Sensing. 2016;8(2). URL: https://www.mdpi.com/2072-4292/8/2/150. DOI: 10.3390/rs8020150 (accessed on 19.12.2023).
8. Liang Z., Zhong P., Zhang C., Yang W., Xiong W., Yang S., et al. A genetic algorithm-based approach for flexible job shop rescheduling problem with machine failure interference. Eksploatacja i Niezawodność – Maintenance and Reliability. 2023;25(4). URL: https://ein.org.pl/A-genetic-algorithm-based-approach-for-flexible-job-shop-rescheduling-problem-with,171784,0,2.html. DOI: 10.17531/ein/171784 (accessed on 19.12.2023).
9. Espinaco F., Henning G.P. Industrial rescheduling approaches: where are we and what is missing? In: ICPR Americas 2022: International Conference on Production Research – Americas 2022, 23–25 November 2022, Curitiba, Brazil. Cham: Springer; 2023. p. 461–467.
10. Nair B., Bhanu S.M.S. A reinforcement learning algorithm for rescheduling preempted tasks in fog nodes. Journal of Scheduling. 2022;25(5):547–565. DOI: 10.1007/s10951-022-00725-x.
11. Konvej R.V., Maksvell V.L., Miller L.V. Teoriya raspisaniy. Moscow, Nauka; 1975. 359 p. (In Russ.).
12. Khan A., Lonkar A., Maiti A., Sharma A., Wiese A. Tight approximation algorithms for two dimensional Guillotine strip packing. arXiv. 2022.
13. Henrik I.C., Arindam K., Pokutta S., Tetali P. Approximation and online algorithms for multidimensional bin packing: A survey. Computer Science Review. 2017;24:63–79. DOI: 10.1016/j.cosrev.2016.12.001.
14. Seiden S.S., Woeginger G.J. The two-dimensional cutting stock problem revisited. Mathematical Programming. 2005;102(3):519–530. DOI: 10.1007/s10107-004-0548-1.
15. Dow E.M. Decomposed multi-objective bin-packing for virtual machine consolidation. PeerJ Computer Science. 2016;2(e47):e47. DOI: 10.7717/peerj-cs.47.
16. Telenyk S., Zharikov E., Rolik O. Consolidation of virtual machines using stochastic local search. In: CSIT 2017: The International Conference on Computer Science and Information Technologies, 5–8 September 2017. Cham: Springer; 2018. p. 523–537.
17. Augustine J., Banerjee S., Irani S. Strip packing with precedence constraints and strip packing with release times. Theoretical Computer Science. 2009;410(38–40):3792–3803. DOI: 10.1016/j.tcs.2009.05.024.
18. Deppert M.A., Jansen K., Khan A., Rau M., Tutas M. Peak demand minimization via sliced strip packing. Algorithmica. 2023;85(12):3649–3679. DOI: 10.1007/s00453-023-01152-w.
19. Bódis A., Csirik J. The variable-width strip packing problem. Central European Journal of Operations Research. 2022;30(4):1337–1351. DOI: 10.1007/s10100-021-00772-3.
20. 20. Barskiy A.B. Parallel'nye informatsionnye tekhnologii. Moscow, BINOM. Laboratoriya znaniy; 2007. 502 p. (In Russ.).
21. Singh R.M., Awasthi L.K., Sikka G. Techniques for task scheduling in cloud and fog environment: A survey. In: Second International Conference on Futuristic Trends in Networks and Computing Technologies (FTNCT-2019), 22–23 November 2019, Chandigarh, India. Singapore: Springer; 2020. p. 673–685.
22. Nguyen B.M., Binh H.T.T., Anh T.T., Son D.B. Evolutionary algorithms to optimize task scheduling problem for the IoT based bag-of-tasks application in cloud–fog computing Environment. Applied Sciences. 2019;9(9). URL: https://www.mdpi.com/2076-3417/9/9/1730. DOI: 10.3390/app9091730 (accessed on 19.12.2023).
23. Natesan G., Chokkalingam A. Task scheduling in heterogeneous cloud environment using mean grey wolf optimization algorithm. ICT Express. 2019;5(2):110–114. DOI: 10.1016/j.icte.2018.07.002.
24. Narendrababu Reddy G., Phani Kumar S. Modified ant colony optimization algorithm for task scheduling in cloud computing systems. In: SCI2018: 2nd International Conference on Smart Computing and Informatics, 27–28 January 2018, Vijayawada, India. Singapore: Springer; 2019. p. 357–365.
