Планирование вычислений многопроцессорной системы в режиме реального времени

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

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

Полный текст

Доступ закрыт

Об авторах

М. Г. Фуругян

ФИЦ ИУ РАН

Автор, ответственный за переписку.
Email: rtsccas@yandex.ru
Россия, Москва

Список литературы

  1. Танаев В. С., Гордон В. С., Шафранский Я. М. Теория расписаний. Одностадийные системы. М.: Наука, 1984.
  2. Brucker P. Scheduling Algorithms. Heidelberg: Springer, 2007.
  3. Лазарев А. А. Теория расписаний. Оценка абсолютной погрешности и схема приближенного решения задач теории расписаний. М.: МФТИ, 2008.
  4. Горский М. А., Мищенко А. В., Нестерович Л. Г., Халиков М. А. Некоторые модификации целочисленных оптимизационных задач с учетом неопределенности и риска // Изв. РАН. ТиСУ. 2022. № 5. С. 106—117.
  5. Мищенко А. В., Кошелев П. С. Оптимизация управления работами логистического проекта в условиях неопределенности // Изв. РАН. ТиСУ. 2021. № 4. С. 123—134.
  6. Глонина А. Б., Балашов В. В. О корректности моделирования модульных вычислительных систем реального времени с помощью сетей временных автоматов // Моделирование и анализ информационных систем. 2018. Т. 25. № 2. С. 174—192.
  7. Глонина А. Б. Обобщенная модель функционирования модульных вычислительных систем реального времени для проверки допустимости конфигураций таких систем // Вестн. ЮУрГУ. Сер. Вычисл. математика и информатика. 2017. Т. 6. № 4. С. 43—59.
  8. Глонина А. Б. Инструментальная система проверки выполнения ограничений реального времени для конфигураций модульных вычислительных систем // Вестн. МГУ. Сер. 15. Вычисл. математика и кибернетика. 2020. № 3. С. 16—29.
  9. Алифанов Д. В., Лебедев В. Н., Цурков В. И. Оптимизация расписаний с логическими условиями предшествования // Изв. РАН. ТиСУ. 2009. № 6. С. 88—93.
  10. Миронов А. А., Цурков В. И. Минимакс в моделях транспортного типа с интегральными ограничениями // Изв. РАН. ТиСУ. 2003. № 4. С. 69—81.
  11. Миронов А. А., Цурков В. И. Минимакс при нелинейных транспортных ограничениях // ДАН. 2001. Т. 381. № 3. С. 305—308.
  12. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. М.: Мир, 1984.
  13. Давыдов Э. Г. Исследование операций. М.: Высш. шк., 1990.
  14. Фуругян М. Г. Планирование вычислений в многопроцессорных системах с несколькими типами дополнительных ресурсов и произвольными процессорами // Вестн. МГУ. Сер. 15. Вычисл. математика и кибернетика. 1917. № 3. С. 38—45.
  15. Yao X., Almatooq N., Askin R. G., Gruber G. Capacity Planning and Production Scheduling Integration: Improving Operational Efficiency Via Detailed Modelling // Intern. J. Production Research. Published Online. 2022. V. 60. No. 1.
  16. Missbauer H., Uzsoy R. Order Release in Production Planning and Control Systems: Challenges and Opportunities // Intern. J. Production Research. 2022. V. 60. No. 1.
  17. Wang Y., Geunes J., Nie X. Optimising Inventory Placement in a Two-echelon Distribution System with Fulfillment-time-dependent Demand // Intern. J. Production Research. 2022. V. 60. No. 1.
  18. Gorman M.F., Conway D. G. ATtutorial of Integrating Duality and Branch and Bound in Earliness-tardiness Scheduling with Idle Insertion Time Problems // Intern. J. Production Research. 2018. V. 56. No. 1-2.
  19. Graves S. C. How to Think About Planned Lead Times // Intern. J. Production Research. 2022. V. 60. No. 1.
  20. Thomasson O., Battarra M., Erdoğan G., Laporte G. Scheduling Twin Robots in a Palletising Problem // Intern. J. Production Research. 2018. V. 56. No. 1-2.
  21. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. М.: Вильямс, 2005.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать
2. Рисунок. Потоковая сеть G для поиска допустимого расписания

Скачать (27KB)
Метаданные

© Российская академия наук, 2024