ИНТЕГРИРОВАННАЯ МОДЕЛЬ РЕШЕНИЯ ЗАДАЧИ ДИСПЕТЧЕРИЗАЦИИ ЗАЯВОК

  • А.Э. Саак Южный федеральный университет
  • Л.А. Гладков Южный федеральный университет
  • Н.В. Гладкова Южный федеральный университет
Ключевые слова: Диспетчирование очередей заявок, системы массового обслуживания, эволюционный поиск, нечеткое управление, Grid-компьютинг

Аннотация

Рассматривается задача диспетчеризации. Рассмотрена парадигма организации
распределенных вычислений на основе Grid-компьютинга. Приведена классификация систем
диспетчирования задач. Описаны различные подходы к решению задачи диспетчирования. При-
ведена модель задачи обслуживания заявок на основе принципов теории систем массового об-
служивания. Сформулирована постановка задачи на основе Grid-диспетчирования. Предложе-
но понятие ресурсного прямоугольника. Определена среда диспетчирования ресурсных прямо-
угольников. Предложена модель позволяющая формализовать заявку пользователя на обслужи-
вание понятием ресурсного (неэвклидова) прямоугольника. Вместо принципа оптимизации на
основе машинного поиска лучшего распределения массива ресурсных прямоугольников,
предложен эвристический принцип, что позволило снизить объем необходимых вычислений.
Предложенный эвристический алгоритм диспетчирования позволяет учитывать свойст-
ва массива и выполнять оценку качества решений. Построены модели среды спроса в форме единичных кубических граней. Модель кубических граней обобщена на эксперимент ку-
бических слоев. Приведено описание используемой модели спроса. Построена модель среды
предложений ресурсов в форме канонической пирамиды и введено понятие канонического
эксперимента спроса- предложения на модельные однородные ресурсные элементы. Введе-
но усечение эксперимента спроса- предложения. Предложена гибридная модель на основе
сочетания эволюционных принципов поиска и методов нечеткого управления. Для решения
задач диспетчеризации предложено использовать эволюционные алгоритмы. Разработана
модифицированная методика кодирования решений и новые модификации генетических
операторов для решения задач диспетчеризации. Представлена структурная схема алго-
ритма решения рассматриваемой задачи с учетом использования нечеткого логического
контроллера Выполнено компьютерное моделирование и приведены результаты вычисли-
тельных экспериментов. Выявлены особенности предложенного метода, сформулированы
его достоинства и недостатки.

Литература

1. Foster I., Kesselman C. The grid: blueprint for a new computing infrastructure. Morgan
Kaufmann Publishers Inc., USA, 1998.
2. Cafaro M., Aloisio G. (eds.). Grids, clouds and virtualization, Computer Communications and
Networks. Springer London, 2011.
3. Yaqin Liu, Chubo Liu, Jing Liu, Yikun Hu, Kenli Li, Keqin Li Mobility-Aware and Code-
Oriented Partitioning Computation Offloading in Multi-Access Edge Computing, Journal of Grid
Computing, 2022, Vol. 20, Article number 11. Available at: https://doi.org/10.1007/s10723-022-
09599-x.
4. Jacob B., Brown M., Fukui K., Trivedi N. Introduction to Grid Computing. ibm.com/redbooks
2005.
5. Kahanwal B., Singh T. The distributed computing paradigms: p2p, grid, cluster, cloud, and
jungle, International Journal of Latest Research in Science and Technology, 2012, Vol. 1,
Issue 2, pp. 183-187.
6. Magoulès F., Nguyen T., Yu L. Grid resource management: toward virtual and services compliant
grid computing, Numerical analysis and scientific computing. CRC Press, UK, 2009.
7. Zhozhikashvili V.V., Vishnevskiy V.M. Seti massovogo obsluzhivaniya. Teoriya i primenenie k
setyam EVM [Queuing networks. Theory and application to computer networks]. Moscow:
Radio i svyaz', 1998.
8. Pinedo M. Scheduling: Theory, Algorithms and Systems. 3nd ed. Springer Verlag, New York,
2008.
9. Conway R.M., Maxwell W.L., Miller L.W. Theory of Scheduling. 2nd ed. Dover Publications,
Mineola NY, 2004.
10. Yarushkina N.G. Osnovy teorii nechetkikh i gibridnykh system [Fundamentals of the theory of
fuzzy and hybrid systems]. Moscow: Finansy i statistika, 2004.
11. Batyrshin I.Z., Nedosekin A.O. i dr. Nechetkie gibridnye sistemy. Teoriya i praktika [Fuzzy
hybrid systems. Theory and practice]. Moscow: Fizmatlit, 2007.
12. Kar А.K. Bio Inspired Computing – A Review of Algorithms and Scope of Applications, Expert
Systems with Applications, 2016, Vol. 59, pp. 20-32.
13. Nature-Inspired Computation and Swarm Intelligence: Algorithms, Theory and Applications.
Academic Press, 2020. ISBN 978-0-12-819714-1. Available at: https://doi.org/10.1016/C2019-
0-00628-0.
14. Gross D., Shortle J.F., Thompson J.M., Harris C.M. Solutions Manual to Accompany Fundamentals
of Queueing Theory. 4th Edition. John Wiley & Sons Inc., 2008.
15. Bhat Narayan U. An Introduction to Queueing Theory: Modeling and Analysis in Applications
(Statistics for Industry and Technology). Birkhäuser, 2008.
16. Gladkov L.A., Gladkova N.V., Gromov S.A. Gibridnaya model' resheniya zadach operativnogo
proizvodstvennogo planirovaniya [Hybrid model for solving operational production planning
tasks], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2018,
No. 4 (165), pp. 102-114.
17. Li M., Baker M. The grid: core technologies. John Wiley & Sons Ltd, England, 2005.
18. Saak A.E. Polinomial'nye algoritmy raspredeleniya resursov v Grid-sistemakh na osnove
kvadratichnoy tipizatsii massivov zayavok [Polynomial algorithms of resource allocation in
Grid systems based on quadratic typing of arrays of applications], Informatsionnye tekhnologii
[Information Technologies], 2013, No. 7.
19. Gladkov L.A., Kureychik V.V., Kureychik V.M. Geneticheskie algoritmy [Kureychik V.M.
Genetic algorithms]. Moscow: Fizmatlit, 2010.
20. Emel'yanov V.V., Kureychik V.V., Kureychik V.M. Teoriya i praktika evolyutsionnogo
modelirovaniya [Theory and practice of evolutionary modeling]. Moscow: Fizmatlit, 2003.
21. Gladkov L.A., Gladkova N.V., Gromov S.A. Gibridnyy algoritm resheniya zadach operativnogo
planirovaniya proizvodstvennogo protsessa [Hybrid algorithm for solving problems of operational
planning of the production process], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya
SFedU. Engineering Sciences], 2017, No. 9 (194), pp. 112-123.
22. Herrera F., Lozano M. Fuzzy Adaptive Genetic Algorithms: design, taxonomy, and future
directions, J. Soft Computing, 2003, pp. 545-562.
23. Michael A., Takagi H. Dynamic control of genetic algorithms using fuzzy logic techniques,
Proceedings of the Fifth International Conference on Genetic Algorithms. Morgan Kaufmann,
1993, pp. 76-83
24. Lee M.A., Takagi H. Integrating design stages of fuzzy systems using genetic algorithms, Proceedings
of the 2nd IEEE International Conference on Fuzzy System, 1993, pp. 612-617.
Опубликован
2022-12-27
Выпуск
Раздел
РАЗДЕЛ II. МОДЕЛИРОВАНИЕ ПРОЦЕССОВ И СИСТЕМ