Аннотация:Рассматривается задача составления допустимого расписания с прерываниями в многопроцессорной системе в случае, когда заданы директивные интервалы, а длительности выполнения работ линейно зависят от количества выделенного им дополнительного ресурса. Разработан псевдополиномиальный алгоритм, основанный на сведении исходной задачи к задаче о потоке минимальной стоимости.