Article

Article title COMBINED APPROACH FOR SOLVING RESOURCE ALLOCATION PROBLEM
Authors Yu. A. Kravchenko, I. O. Kursitys
Section SECTION II. ARTIFICIAL INTELLIGENCEAND FUZZY SYSTEMS
Month, Year 07, 2017 @en
Index UDC 004.023
DOI
Abstract The paper is devoted to solving the computative resource allocation problem. In general, the resource allocation problem involves allocating the limited resource among processes in optimal way. Authors formulated the problem statement and its mathematical model. The resource alloca-tion problem is referred as NP-complete, thus, the usage of traditional mathematical means is impossible or limited in terms of solving this problem. The developed approach is based on simu-lation modeling usage and Petri Nets tools to allocate resources. Since allocated resources are considered as computative, time spent for all processes execution and all Petri Net transition per-formance is taken as the main optimization criterion. Thus, authors apply temporal Petri Nets to model the resource allocation problem. The combined approach for solving computative resource allocation problem involves simultaneous application of Petri Net tools to model the problem, and genetic algorithms, which have proved their success in solving NP-complete problems. To optimize the Petri Net model authors use well-known genetic algorithms and modified genetic operators of crossover and mutation. Authors developed software representing the resource allocation subsystem. The paper describes main function of the subsystem and shows developed module structure of it. To represent main information processes flowing in subsystem, two information models on the basis of the IDEF0 standard are built and analyzed. Authors carried out computational experiments based on test benchmarks, which proved the effectiveness of the developed approach.

Download PDF

Keywords Resource allocation; CALS; simulation; Petri nets; genetic algorithm.
References 1. Belousov S.M. Matematicheskaya model' mnogopotochnoy sistemy massovogo obsluzhivaniya, upravlyaemoy planirovshchikom resursov [A mathematical model of a multi-threaded Queuing system, scheduler-managed resources], Vestnik Novosibirskogo gosudarstvennogo universiteta. Seriya: informatsionnye tekhnologii [Vestnik of Novosibirsk State University. Series: Information Technologies], 2006, Vol. 4, No. 1, pp. 14-26.
2. Prilutskiy M.Kh., Nefedov D.S., Popov D.V. Raspredelenie resursov v diskretno upravlyaemykh sistemakh [Resource allocation in discrete controlled systems], Elektronnyy zhurnal “Issledovano v Rossii” [Electronic journal “Investigated in Russia”], 2002, No. 5,
pp. 322-337.
3. Prilutskiy M.Kh., Vyakhirev D.V. Mnogostadiynye zadachi al'ternativnogo raspredeleniya resursov [Multistage tasks alternative allocation of resources], Vestnik Nizhegorodskogo gosudarstvennogo universiteta. Matematicheskoe modelirovanie i optimal'noe upravlenie [Vestnik of Nizhny Novgorod state University. Mathematical modeling and optimal control], 2002, Issue 25 (1), pp. 36-43.
4. Yury Kravchenko, Ilona Kursitys, Dmitry Zaporozhets. Resource allocation system based on simulation modeling in computer-aided design system. In Conference proceedings, 2016 6th International Conference Cloud System and Data Engineering (Confluence). – 14-15 January 2016, Amity University Uttar Pradesh, Noida, India, pp. 395-400.
5. Kravchenko Yu.A. CALS- i CASE-tekhnologii: uchebno-metodicheskoe posobie [CALS - and CASE-technology: a teaching manual]. Taganrog, 2010, 142 p.
6. Kravchenko Yu.A. Cals-imitatsionnye modeli v upravlenii dannymi SAPR [Cals-simulation models in the management of CAD data], Izvestiya TRTU [Izvestiya TSURE], 2006, No. 8 (63), pp. 143-146.
7. Eddous M., Stensfild R. Metody prinyatiya resheniy [Decision-making methods]: translation from English, under the editorship of corresponding member of RAS I.I. Eliseevoy. Moscow: Audit, YuNITI, 1997, 590 p.
8. Kureychik V.M., Kureychik V.V. Evolyutsionnye, sinergeticheskie i gomeostaticheskie strategii v iskusstvennom intellekte: sostoyanie i perspektivy [Evolutionary, synergetic and homeostatic strategies in artificial intelligence: state and prospects], Novosti iskusstvennogo intellekta [Ar-tificial Intelligence News], 2000, No. 3, pp. 39-67.
9. Kravchenko Yu.A., Kursitys I.O. Razrabotka modeli zadachi raspredeleniya resursov v protsessakh SAPR i struktury podsistemy ee resheniya [Development of a model resource al-location problems in the processes of CAD and the structure of the subsystem of its solution], Trudy Kongressa po intellektual'nym sistemam i informatsionnym tekhnologiyam «IS&IT’15» [Proceedings of Congress on intelligent systems and information technologies "IS&IT'15"]. Scientific publication in 4 vol. Vol. 3. Moscow: Fizmatlit, 2015.
10. Bova V.V., Kureychik V.V. Integrirovannaya podsistema gibridnogo i kombinirovannogo poiska v zadachakh proektirovaniya i upravleniya [Integrated subsystem of the hybrid and combined search in problems of design and managemen], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2010, No. 12 (113), pp. 37-43.
11. Zaporozhets D.Yu., Kureychik V.V. Gibridnyy algoritm resheniya zadach transportnogo tipa
[A hybrid algorithm for solving problems of transport type], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2013, No. 7 (144), pp. 80-85.
12. Kureichik, V.V., Kravchenko, Y.A., Bova, V.V. Decision support systems for knowledge man-agement, Advances in Intelligent Systems and Computing, 2015, Vol. 349, pp. 123-130.
13. Gladkov L.A., Kureychik V.M., Kureychik V.V. Geneticheskie algoritmy [Genetic algorithms]. Moscow: Fizmatlit, 2006, 320 p.
14. Zaporozhets D.U., Zaruba D.V. and Kureichik V.V. Representation of solutions in genetic VLSI placement algorithms, IEEE East-West Design & Test Symposium – (EWDTS’2014) Kiev, Ukraine, 2014, pp. 1-4.
15. Podlazova A.V. Geneticheskie algoritmy na primerakh zadachi raskroya [Genetic algorithms on the instances of the problem of cutting], Problemy upravleniya [Problems of Management], 2008, No. 2, pp. 57-62.
16. Kureychik V.V., Rodzin S.I. O pravilakh predstavleniya resheniy v evolyutsionnykh algoritmakh [About the rules for the submission of solutions in evolutionary algorithms], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2010, No. 7 (108), pp. 13-21.
17. Zaporozhets D.Yu., Kudaev A.Yu., Lezhebokov A.A. Mnogourovnevyy algoritm resheniya zadachi parametricheskoy optimizatsii na osnove bioinspirirovannykh evristik [A multilevel algorithm for solving the problem of parametric optimization based on bio-inspired heuristics], Izvestiya Kabardino-Balkarskogo nauchnogo tsentra RAN [Izvestiya of Kabardino-Balkar sci-entific centre of the RAS], 2013, No. 4 (54), pp. 21-28.
18. Kureychik V.M. Osobennosti postroeniya sistem podderzhki prinyatiya resheniy [Features of construction of systems of support of acceptance of decisions], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2012, No. 7 (132), pp. 92-98.
19. Kureychik V.M., Kazharov A.A. Ispol'zovanie shablonnykh resheniy v murav'inykh algoritmakh [The use of standard solutions in ant colony optimization algorithms], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2013, No. 7 (144), pp. 11-17.
20. Gladkov L.A., Kravchenko Y.A., Kureichik V.V. Evolutionary Algorithm for Extremal Subsets Comprehension in Graphs, World Applied Sciences Journal, 2013, No. 27 (9), pp. 1212-1217.

Comments are closed.