Аннотация:Рассматривается задача составления допустимого расписания с прерываниями при заданных сложностях (или объемах) работ, директивных интервалах и производительностях процессоров. Разработаны эвристические алгоритмы для случая, когда издержки на обработку прерываний и переключений не учитываются. Алгоритмы основаны на обобщении известного однопроцессорного алгоритма относительной срочности. Вычислительная сложность предложенных алгоритмов значительно меньше сложности точного потокового алгоритма, что подтверждается также машинными экспериментами (выигрыш во времени составляет до нескольких тысяч раз). При этом процент некорректной работы алгоритмов незначительный (от 1 до 20 % в зависимости от параметров задачи).