Коррекция многопроцессорных расписаний в режиме реального времени
https://doi.org/10.25682/NIISI.2025.1.0006
Аннотация
Рассматривается задача планирования вычислений в многопроцессорных системах при периодически поступающих запросах на выполнение комплекса работ с нефиксированными длительностями. Используется неоднородный набор ресурсов – возобновляемых и невозобновляемых. Рассмотрены случаи, когда работы допускают прерывания и переключения с одного процессора на другой, а также когда работы непрерываемые. Разработаны алгоритмы, в которых при обработке каждого запроса корректируется расписание, построенное при обработке предыдущего запроса. Алгоритмы основаны на сетевом моделировании и поиске максимального потока и потока минимальной стоимости.
Список литературы
1. А.Б. Глонина, В.В. Балашов. О корректности моделирования модульных вычислительных систем реального времени с помощью сетей временных автоматов // Моделирование и анализ информационных систем. (2018), Т. 25, № 2, 174 – 192.
2. А.Б. Глонина. Инструментальная система проверки выполнения ограничений реального времени для конфигураций модульных вычислительных систем // Вестник МГУ. Сер. 15. Вычисл. математика и кибернетика. (2020), № 3, 16 – 29.
3. А.В. Мищенко, П.С. Кошелев. Оптимизация управления работами логистического проекта в условиях неопределенности // Известия РАН. Теория и системы управления. (2021), № 4, 123 – 134.
4. М.А. Горский, А.В. Мищенко, Л.Г. Нестерович, М.А. Халиков. Некоторые модификации целочисленных оптимизационных задач с учетом неопределенности и риска // Известия РАН. Теория и системы управления. (2022), № 5, 106 – 117.
5. В.А. Костенко, А.С. Смирнов. Потоковые алгоритмы планирования вычислений в интегрированной модульной авионике // Изв. РАН. ТиСУ. (2019), № 3, 77 – 86.
6. В.В. Балашов, В.А. Костенко, И.А. Федоренко, Ц. Гао, Ч.М. Сун, Ц. Сун. Алгоритм имитации отжига для построения списочных расписаний с ограничениями на количество межпроцессорных передач данных // Автоматика и телемеханика. (2023), № 8, 138 – 152.
7. Д.А. Кононов, М.Г. Фуругян. Распределение неоднородного комплекса ресурсов при региональном планировании в условиях неопределенности // Труды XV межд. конф. “Управление развитием крупномасштабных систем (MLSD'2022)”. – Москва, ИПУ РАН. – 26 – 28 сент. (2022) 952 – 958.
8. Е.О. Косоруков, М.Г. Фуругян. Некоторые алгоритмы распределения ресурсов в многопроцессорных системах // Вестник МГУ. Сер. 15. Вычисл. математика и кибернетика. (2009), № 4, 34 – 37.
9. Э. Майника. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981, 325 с.
10. Танаев В.С., Гордон В.С., Шафранский Я.М. Теория расписаний. Одностадийные системы. М.: Наука, 1984, 383 с.
11. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы. Построение и анализ. М.: Вильямс, 2005,1296 с.
12. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982, 416 с.
13. Фуругян М.Г. Некоторые алгоритмы решения минимаксной задачи составления многопроцессорного расписания // Изв. РАН, ТиСУ. (2014), №2, с. 50 - 56.
Рецензия
Для цитирования:
Фуругян М.Г. Коррекция многопроцессорных расписаний в режиме реального времени. Труды НИИСИ. 2025;15(1):48-51. https://doi.org/10.25682/NIISI.2025.1.0006
For citation:
Furugyan M.G. Correcting Multiprocessor Schedules in Real Time. SRISA Proceedings. 2025;15(1):48-51. (In Russ.) https://doi.org/10.25682/NIISI.2025.1.0006
Просмотров:
11
Послать статью по эл. почте 