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

Cite: Захарова Ю.В. , Захаров А.О.
Приближённое решение задачи составления расписаний с учётом статической и динамической составляющих на расход энергии
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2026. №72. С.117-125. DOI: 10.17223/20710410/72/9

Dates:

Published print:	May 4, 2026
Published online:	May 4, 2026

Identifiers: No identifiers

Altmetrics: