1precpmtnrifmax

Данная задача является обобщением [math]1 \mid prec \mid f_{max}[/math] и также использует правило Лаулера для построения оптимального расписания.

Алгоритм

Идея следующая: допустим, у нас есть блок работ, который можно выполнить без прерываний. Найдем работу [math]i[/math], которую выгодно выполнить последней. Разобъем оставшееся множество работ на блоки, решим задачу для этих блоков рекурсивно и вставим [math] i [/math] в промежутки между этими блоками, до них и после них, начиная с [math] r_i [/math].