Конструктивные алгоритмы для задачи составления расписаний на двух процессорах с критерием максимального временного смещения при учете распараллеливания и расхода энергии

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