Обобщение задачи составления многопроцессорного расписания с прерываниями
Аннотация
Рассматривается задача составления многопроцессорного расписания для комплекса работ, допускающих прерывания и переключения с одного процессора на другой. Предполагается, что обработка прерываний и переключений требует временных издержек. Это условие переводит задачу из класса полиномиально разрешимых в класс NP-трудных. Разработан алгоритм, основанный на методике В.С. Танаева составления многопроцессорного расписания без учета затрат на прерывания и переключения. Методика включает в себя процедуру упаковки для случая, когда работы имеют общий директивный срок, а также процедуру сведения исходной задачи к потоковой для случая произвольных директивных интервалов. При этом используется также известный псевдополиномиальный алгоритм составления допустимого многопроцессорного расписания для непрерываемых работ с общим директивным сроком.
Список литературы
1. Танаев В.С., Гордон В.С., Шафранский Я.М. Теория расписаний. Одностадийные системы. М.: Наука, 1984, 383 с.
2. Brucker P. Scheduling Algorithms. Heidelberg: Springer, 2007, 378 с.
3. Лазарев А.А. Теория расписаний. Методы и алгоритмы. –М.: ИПУ РАН, 2019,407 с.
4. А.В. Мищенко, П.С. Кошелев. Оптимизация управления работами логистического проекта в условиях неопределенности // Известия РАН. Теория и системы управления. (2021), № 4, 123-134.
5. М.А. Горский, А.В. Мищенко, Л.Г. Нестерович, М.А. Халиков. Некоторые модификации целочисленных оптимизационных задач с учетом неопределенности и риска // Известия РАН. Теория и системы управления. (2022), № 5, 106-117.
6. А.Б. Глонина, В.В. Балашов. О корректности моделирования модульных вычислительных систем реального времени с помощью сетей временных автоматов // Моделирование и анализ информационных систем. (2018), Т. 25, № 2, 174 – 192.
7. А.Б. Глонина. Инструментальная система проверки выполнения ограничений реального времени для конфигураций модульных вычислительных систем // Вестн. МГУ. Сер. 15. Вычисл. математика и кибернетика. (2020), № 3, 16 – 29.
8. М.Г. Фуругян. Планирование вычислений в многопроцессорных АСУ реального времени с дополнительным ресурсом //Автоматика и телемеханика. (2015), №3, 144 – 150.
9. М.Г. Фуругян. Составление расписаний в многопроцессорных системах с несколькими дополнительными ресурсами // Известия РАН. Теория и системы управления. (2017), № 2, 57 – 66.
10. М.Г. Фуругян. Некоторые алгоритмы решения минимаксной задачи составления многопроцессорного расписания // Известия РАН. Теория и системы управления. (2014), №2, 50 - 56.
11. М.Г. Фуругян. Составление расписаний в многопроцессорной системе с учетом затрат на прерывания // В Сб. Математическое и компьютерное моделирование сложных систем: теоретические и прикладные аспекты. Труды НИИСИ РАН. Т. 6, № 2, 57 – 61.
Рецензия
Для цитирования:
Фуругян М.Г. Обобщение задачи составления многопроцессорного расписания с прерываниями. Труды НИИСИ. 2024;14(2):10-14.
For citation:
Furugyan M. Generalization of the Problem of Creating a Multiprocessor Schedule with Interrupts. SRISA Proceedings. 2024;14(2):10-14. (In Russ.)
Просмотров:
14
Послать статью по эл. почте 