Correcting Multiprocessor Schedules in Real Time
https://doi.org/10.25682/NIISI.2025.1.0006
Abstract
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.
References
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.
Review
For citations:
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
Views:
12
Email this article 