trudyniisiТруды НИИСИSRISA Proceedings2225-73493033-6422НИЦ «КУРЧАТОВСКИЙ ИНСТИТУТ» - НИИСИ10.25682/NIISI.2025.1.0006trudyniisi-6Research ArticleМАТЕМАТИЧЕСКОЕ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ, КОМПЛЕКСОВ И КОМПЬЮТЕРНЫХ СЕТЕЙMATHEMATICAL AND SOFTWARE SUPPORT FOR COMPUTING SYSTEMS, COMPLEXES AND COMPUTER NETWORKSКоррекция многопроцессорных расписаний в режиме реального времениCorrecting Multiprocessor Schedules in Real TimeФуругянМ. Г.FurugyanM. G.

Москва

rtsccas@yandex.ruФИЦ ИУ РАНRussian Federation202529092025151МАТЕМАТИЧЕСКОЕ И КОМПЬЮТЕРНОЕ МОДЕЛИРОВАНИЕ СЛОЖНЫХ СИСТЕМ: ТЕОРЕТИЧЕСКИЕ И ПРИКЛАДНЫЕ АСПЕКТЫ4851Copyright © Фуругян М.Г., 20252025Фуругян М.Г.Furugyan M.G.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.t-niisi.ru/jour/article/view/6

Рассматривается задача планирования вычислений в многопроцессорных системах при периодически поступающих запросах на выполнение комплекса работ с нефиксированными длительностями. Используется неоднородный набор ресурсов – возобновляемых и невозобновляемых. Рассмотрены случаи, когда работы допускают прерывания и переключения с одного процессора на другой, а также когда работы непрерываемые. Разработаны алгоритмы, в которых при обработке каждого запроса корректируется расписание, построенное при обработке предыдущего запроса. Алгоритмы основаны на сетевом моделировании и поиске максимального потока и потока минимальной стоимости.

The task of planning computing in multiprocessor systems is considered in periodically incoming requests to perform a set of work with non-fixed durations. A heterogeneous set of resources is used - renewable and non-renewable. There are cases when work allow interruptions and switching from one processor to another, as well as when the work is uninterrupted. Algorithms have been developed in which, when processing each request, the schedule built during the processing of the previous request is adjusted. Algorithms are based on network modeling and searching for the maximum flow and flow of the minimum cost.

многопроцессорная системадирективный интервалдопустимое расписаниепотоковая сетьмаксимальный потокпоток минимальной стоимостиmultiprocessor systemdirective intervalfeasible scheduleflow networkmaximum flowminimum cost flowReferencesА.Б. Глонина, В.В. Балашов. О корректности моделирования модульных вычислительных систем реального времени с помощью сетей временных автоматов // Моделирование и анализ информационных систем. (2018), Т. 25, № 2, 174 – 192.А.Б. Глонина, В.В. Балашов. О корректности моделирования модульных вычислительных систем реального времени с помощью сетей временных автоматов // Моделирование и анализ информационных систем. (2018), Т. 25, № 2, 174 – 192.А.Б. Глонина. Инструментальная система проверки выполнения ограничений реального времени для конфигураций модульных вычислительных систем // Вестник МГУ. Сер. 15. Вычисл. математика и кибернетика. (2020), № 3, 16 – 29.А.Б. Глонина. Инструментальная система проверки выполнения ограничений реального времени для конфигураций модульных вычислительных систем // Вестник МГУ. Сер. 15. Вычисл. математика и кибернетика. (2020), № 3, 16 – 29.А.В. Мищенко, П.С. Кошелев. Оптимизация управления работами логистического проекта в условиях неопределенности // Известия РАН. Теория и системы управления. (2021), № 4, 123 – 134.А.В. Мищенко, П.С. Кошелев. Оптимизация управления работами логистического проекта в условиях неопределенности // Известия РАН. Теория и системы управления. (2021), № 4, 123 – 134.М.А. Горский, А.В. Мищенко, Л.Г. Нестерович, М.А. Халиков. Некоторые модификации целочисленных оптимизационных задач с учетом неопределенности и риска // Известия РАН. Теория и системы управления. (2022), № 5, 106 – 117.М.А. Горский, А.В. Мищенко, Л.Г. Нестерович, М.А. Халиков. Некоторые модификации целочисленных оптимизационных задач с учетом неопределенности и риска // Известия РАН. Теория и системы управления. (2022), № 5, 106 – 117.В.А. Костенко, А.С. Смирнов. Потоковые алгоритмы планирования вычислений в интегрированной модульной авионике // Изв. РАН. ТиСУ. (2019), № 3, 77 – 86.В.А. Костенко, А.С. Смирнов. Потоковые алгоритмы планирования вычислений в интегрированной модульной авионике // Изв. РАН. ТиСУ. (2019), № 3, 77 – 86.В.В. Балашов, В.А. Костенко, И.А. Федоренко, Ц. Гао, Ч.М. Сун, Ц. Сун. Алгоритм имитации отжига для построения списочных расписаний с ограничениями на количество межпроцессорных передач данных // Автоматика и телемеханика. (2023), № 8, 138 – 152.В.В. Балашов, В.А. Костенко, И.А. Федоренко, Ц. Гао, Ч.М. Сун, Ц. Сун. Алгоритм имитации отжига для построения списочных расписаний с ограничениями на количество межпроцессорных передач данных // Автоматика и телемеханика. (2023), № 8, 138 – 152.Д.А. Кононов, М.Г. Фуругян. Распределение неоднородного комплекса ресурсов при региональном планировании в условиях неопределенности // Труды XV межд. конф. “Управление развитием крупномасштабных систем (MLSD'2022)”. – Москва, ИПУ РАН. – 26 – 28 сент. (2022) 952 – 958.Д.А. Кононов, М.Г. Фуругян. Распределение неоднородного комплекса ресурсов при региональном планировании в условиях неопределенности // Труды XV межд. конф. “Управление развитием крупномасштабных систем (MLSD'2022)”. – Москва, ИПУ РАН. – 26 – 28 сент. (2022) 952 – 958.Е.О. Косоруков, М.Г. Фуругян. Некоторые алгоритмы распределения ресурсов в многопроцессорных системах // Вестник МГУ. Сер. 15. Вычисл. математика и кибернетика. (2009), № 4, 34 – 37.Е.О. Косоруков, М.Г. Фуругян. Некоторые алгоритмы распределения ресурсов в многопроцессорных системах // Вестник МГУ. Сер. 15. Вычисл. математика и кибернетика. (2009), № 4, 34 – 37.Э. Майника. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981, 325 с.Э. Майника. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981, 325 с.Танаев В.С., Гордон В.С., Шафранский Я.М. Теория расписаний. Одностадийные системы. М.: Наука, 1984, 383 с.Танаев В.С., Гордон В.С., Шафранский Я.М. Теория расписаний. Одностадийные системы. М.: Наука, 1984, 383 с.Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы. Построение и анализ. М.: Вильямс, 2005,1296 с.Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы. Построение и анализ. М.: Вильямс, 2005,1296 с.Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982, 416 с.Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982, 416 с.Фуругян М.Г. Некоторые алгоритмы решения минимаксной задачи составления многопроцессорного расписания // Изв. РАН, ТиСУ. (2014), №2, с. 50 - 56.Фуругян М.Г. Некоторые алгоритмы решения минимаксной задачи составления многопроцессорного расписания // Изв. РАН, ТиСУ. (2014), №2, с. 50 - 56.

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