procyberВестник кибернетикиProceedings in Cybernetics1999-7604Бюджетное учреждение высшего образования Ханты-Мансийского автономного округа – Югры «Сургутский государственный университет»10.35266/1999-7604-2023-3-82-98procyber-548Research ArticleФИЗИКО-МАТЕМАТИЧЕСКИЕ НАУКИPhysics and MathematicsМНОГОКРИТЕРИАЛЬНОЕ ПЛАНИРОВАНИЕ РАБОТЫ ЦЕНТРА УПРАВЛЕНИЯ ПОЛЕТОМ КОСМИЧЕСКИХ АППАРАТОВ НА ДИНАМИЧЕСКОЙ МОДЕЛИ С ТУПИКОВЫМИ УПРАВЛЕНИЯМИMULTI-CRITERIAL SCHEDULING OF A SPACECRAFT CONTROL CENTER’S OPERATION ON A DYNAMIC MODEL WITH DEAD-END CONTROLShttps://orcid.org/0000-0002-3643-1609КорнеенкоВиктор ПавловичKorneenkoViktor P.

кандидат технических наук, доцент

 

Candidate of Sciences (Engineering), Docent

vkorn@ipu.ru

vkorn@ipu.ruИнститут проблем управления им. В. А. Трапезникова Российской академии наук, МоскваРоссияV. A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences, MoscowRussian Federation2023171120232238298Copyright © Корнеенко В.П., 20232023Корнеенко В.П.Korneenko V.P.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.vestcyber.ru/jour/article/view/548

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

The article is devoted to the solution of a problem of multi-criterial scheduling for execution of calculations of a large number of time-consuming computational tasks being solved simultaneously when implementing the time-sharing mode for their solutions in software and hardware’s multiprocessor computing systems by the spacecraft control center. A dynamic recurrent model with dead-end controls is used to implement the schedule of organizing software command information with control sectors. The criteria for selecting an efficient option of a daily schedule for the control sectors’ operation are determined, with the schedule being presented as time intervals of access to the computing system’s resources. Compared to the traditional algorithms of discrete optimization, the method of dead-ends control is more efficient in calculation in the frame-work of a dynamic model. An example of calculations conducted by the dead-end controls algorithm for the operational program, which is used on board of the spacecraft during a communication session, is given.

многокритериальный выборплан работы центра управления полетомдинамическая модельтупиковые управлениярежим разделения времениmulti-criteria selectionspacecraft control center’s operation plandynamic modeldead-end controlstime-sharing modeReferencesНагибин С. Я., Почукаев В. Н., Ухлинов Л. М. Структура и принципы построения математического обеспечения Центра управления полетами космических аппаратов // Вестник Российского общества информатики и вычислительной техники. 1995. Вып. 5. C. 66–72.Nagibin S. Ya., Pochukaev V. N., Ukhlinov L. M. Struktura i printsipy postroeniia matematicheskogo obespecheniia Tsentra upravleniia poletami kosmicheskikh apparatov. Vestnik Rossiiskogo obshchestva informatiki i vychislitelnoi tekhniki. 1995(5):66–72. (In Russian).Мануйлов Ю. С., Калинин В. Н. Управление космическими аппаратами и средствами наземного комплекса управления. СПб. : ВКА им. А. Ф. Можайского, 2010. 609 с.Manuilov Yu. S., Kalinin V. N. Upravlenie kosmicheskimi apparatami i sredstvami nazemnogo kompleksa upravleniia. St. Petersburg: Mozhaisky Military Aerospace Academy; 2010. 609 p. (In Russian).Калинин В. Н. Математическая модель информационного взаимодействия космического аппарата с поверхностью земли // Труды СПИИРАН. 2014. № 3. С. 33–56.Kalinin V. N. Mathematical model of informational interaction of the spacecraft with a surface of the Earth. SPIIRAS Proceedings. 2014;(3):33–56. (In Russian).Мануйлов Ю. С., Москвин Б. В., Павлов Д. А. Модель планирования распределенной обработки информации в различных звеньях автоматизированных систем управления космическими аппаратами // Труды ВКА им. А. Ф. Можайского. 2014. № 642. C. 32–35.Manuilov Yu. S., Moskvin B. V., Pavlov D. A. Model planirovaniia raspredelennoi obrabotki informatsii v razlichnykh zveniakh avtomatizirovannykh sistem upravleniia kosmicheskimi apparatami. Proceedings of the Mozhaisky Military Space Academy. 2014;(642):32–35. (In Russian).Командровский В. Г. О планировании работ в вычислительной системе // Автоматика и телемеханика. 2005. Вып. 12. С. 65–74.Komandrovsky V. G. Job scheduling for a computing system. Avtomatika i telemekhanika. 2005;(12):65–74. (In Russian).Голубев И. А. Планирование задач в распределённых вычислительных системах на основе метаданных : дис. … канд. техн. наук. СПб. : Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им. В. И. Ульянова (Ленина), 2014. 135 с.Golubev I. A. Planirovenie zadach v raspredelennykh vychislitelnykh sistemakh na osnove metadannykh. Cand. Sci. (Engineering) Thesis. St. Petersburg: Saint Petersburg Electrotechnical University; 2014. 135 p. (In Russian).Brobcrg J. А. Effective task assignment strategies for distributed systems under highly variable workloads. Dr. (Philosophy) Thesis. Melbourne, Victoria, Australia: RMIT University; 2006. 208 p.Brobcrg J. А. Effective task assignment strategies for distributed systems under highly variable workloads. Dr. (Philosophy) Thesis. Melbourne, Victoria, Australia: RMIT University; 2006. 208 p.Клейнрок Л. Вычислительные системы с очередями / пер. с англ. под ред. Б. С. Цыбакова. М. : Мир, 1979. 600 с.Kleinrock L. Queuing systems. Vol. 2. Computer applications. Tsybakov B. S., editor. Moscow: Mir; 1979. 600 p. (In Russian).Баканов В. М. Многомашинные комплексы и многопроцессорные системы. М. : МГУПИ, 2014. 126 с.Bakanov V. M. Mnogomashinnye kompleksy i mnogoprotsessornye sistemy. Moscow: Moscow State University of Instrument Engineering and Computer Science; 2014. 126 p. (In Russian).Колпин М. А., Москвин Б. В. Подход к оптимизации технологии оперативного планирования применения средств наземного автоматизированного комплекса управления космическими аппаратами // i-methods. 2015. Т. 7, № 3. С. 10–14.Kolpin M. A., Moskvin B. V. The approach to technology optimization of operational planning of the use of landing automated complex spaceship control. i-methods. 2015;7(3):10–14. (In Russian).Минаков Е. П., Привалов А. Е., Бугайченко П. Ю. Модель оценивания эффективности управления многоспутниковыми орбитальными системами // Труды МАИ. 2022. № 125. С. 1–26.Minakov E. P., Privalov A. E., Bugaichenko P. Yu. A model for evaluating the control efficiency of multisatellite orbital systems. Trudy MAI. 2022;(125):1–26. (In Russian).Аничкин А. С., Семенов В. А. Современные модели и методы теории расписаний // Труды Института программирования РАН. 2014. Т. 26, № 3. С. 5–50.Anichkin A. S., Semenov V. A. A survey of emerging models and methods of scheduling. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2014;26(3):5‒50. (In Russian).Лазарев А. А. Теория расписаний. Методы и алгоритмы : моногр. М. : ИПУ РАН, 2019. 408 с.Lazarev A. A. Teoriia raspisanii. Metody i algoritmy. Monograph. Moscow: V. A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences; 2019. 408 p. (In Russian).Зимин И. Н., Иванилов Ю. П. Решение задач сетевого планирования сведением их к задачам оптимального управления // Журнал вычислительной математики и математической физики. 1971. Т. 11, № 3. C. 632–641.Zimin I. N., Ivanilov Yu. P. Solution of network planning problems by reducing them to optimal control problems. Zhurnal vychislitelnoi matematiki i matematicheskoi fiziki. 1971;11(3):632–641. (In Russian).Калинин В. Н., Соколов Б. В. Динамическая модель и алгоритм оптимального планирования комплекса работ с запретами на прерывание // Автоматика и телемеханика. 1987. Вып. 1. С. 106–114.Kalinin V. N., Sokolov B. V. A dynamic model and an optimal scheduling algorithm for a set of activities with bans on interrupts. Avtomatika i telemekhanika. 1987;(1):106–114. (In Russian).Ivanov D., Dolgui A., Sokolov B. et al. A dynamic model and an algorithm for short-term supply chain scheduling in the smart factory industry 4.0. International Journal of Production Research. 2016;54(2):386–402.Ivanov D., Dolgui A., Sokolov B. et al. A dynamic model and an algorithm for short-term supply chain scheduling in the smart factory industry 4.0. International Journal of Production Research. 2016;54(2):386–402.Richter K. Dynamic tasks of discrete optimization. Berlin, Boston: De Gruyter; 1982. 114 p.Richter K. Dynamic tasks of discrete optimization. Berlin, Boston: De Gruyter; 1982. 114 p. (In German).Корнеенко В. П. Методы оптимизации. М. : Высш. шк., 2007. 663 с.Korneenko V. P. Metody optimizatsii. Moscow: Vyssh. shk.; 2007. 663 p. (In Russian).Korneenko V. P. An efficient algorithm of dead-end controls for solving combinatorial optimization problems. Automation and Remote Control. 2021;82:1692–1705.Korneenko V. P. An efficient algorithm of dead-end controls for solving combinatorial optimization problems. Automation and Remote Control. 2021;82:1692–1705.Яблонский С. В. Введение в дискретную математику. М. : Наука, 1986. 384 c.Yablonsky S. V. Vvedenie v diskretnuiu matematiku. Moscow: Nauka; 1986. 384 p. (In Russian).Бендат Дж., Пирсол А. Прикладной анализ случайных данных / пер. с англ. В. Е. Привальского, А. И. Кочубинского ; под ред. И. Н. Коваленко. М. : Мир, 1989. 540 с.Bendat J. S., Piersol A. G. Random data: Analysis and measurement procedures. Privalsky V. E., Kochubinsky A. I., translators; I. N. Kovalenko, editor. Moscow: Mir; 1989. 540 p. (In Russian).Климов Г. П., Ляху А. К., Матвеев В. Ф. Математические модели систем с разделением времени. Кишинев : Штиинца, 1983. 110 с.Klimov G. P., Lyakhu A. K., Matveev V. F. Matematichekie modeli sistem s razdeleniem vremeni. Kishinev: Shtiintsa; 1983. 110 p. (In Russian).Беллман Р. Динамическое программирование / пер. с англ. И. М. Андреевой, А. А. Корбута, И. В. Романовского, И. Н. Соколовой ; под ред. Н. Н. Воробьева. М. : Изд-во иностр. лит., 1960. 400 с.Bellman R. Dynamic programming. Andreeva I. M., Korbut A. A., Romanovsky I. V., Sokolova I. N., translators; N. N. Vorobyev, editor. Moscow: Izd-vo inostr. lit.; 1960. 400 p. (In Russian).Сигал И. Х., Иванова А. П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы. М. : Физматлит, 2002. 240 с.Sigal I. Kh., Ivanova A. P. Vvedenie v prikladnoe diskretnoe programmirovanie: modeli i vychislitelnye algoritmy. Moscow: Fizmatlit; 2002. 240 p. (In Russian).Pisinger D. A minimal algorithm for the 0-1 Knapsack Problem. Operations Research. 1997;46(5):758–767.Pisinger D. A minimal algorithm for the 0-1 Knapsack Problem. Operations Research. 1997;46(5):758–767.Конвей Р. Б., Максвелл В. Л., Миллер Л. В. Теория расписаний / пер. с англ. В. А. Кокотушкина, Д. Г. Михалева ; под ред. Г. П. Башарина. М. : Наука, 1975. 359 с.Conway R. W., Maxwell W. L., Miller L. W. Theory of scheduling. Kokotushkin V. A., Mikhalev D. G., translators; Basharin G. P., editor. Moscow: Nauka; 1975. 359 p. (In Russian).Корнеенко В. П. Метод локального агрегирования данных объектов с многоуровневой структурой в порядковых шкалах // Управление развитием крупномасштабных систем (MLSD-2021) : труды 14-й Междунар. конф., 27‒29 сентября 2021 г., г. Москва. М. : ИПУ РАН, 2021. С. 485–493.Korneenko V. P. Metod lokalnogo agregirovaniia dannykh obektov s mnogourovnevoi strukturoi v poriadkovykh shkalakh. In: Proceedings of the Fourteenth International Conference “Management of Large-Scale System Development (MLSD-2021)”, September 27‒29, 2021, Moscow. Moscow: V. A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences; 2021. p. 485–493. (In Russian).Корнеенко В. П. Метод аппроксимационной матрицы формирования весов объектов в многокритериальных задачах выбора // Вестник кибернетики. 2021. № 1. С. 51–62.Korneenko V. P. Approximation matrix method for weights formation of objects in multicriteria problems. Proceedings in Cybernetics. 2021;(1):51‒62. (In Russian).

The authors declare that there are no conflicts of interest present.