Упорядочение структурного множества работ, минимизирующее суммарный штраф

Решается задача составления расписания, минимизирующего суммарный штраф. Задано множество работ $Z$. Условия предшествования отсутствуют. Каждая работа $\alpha\in Z$ состоит из $V_\alpha$ элементарных операций. Прерывания работы 2 допускаются. Прерывания элементарных операций не допускается. Штраф операции работы $\alpha$, выполняющейся в момент $t$, – $\alpha(t)$. Расписание оценивается штрафом, который является суммой штрафов всех элементарных операций всех работ множества $Z$. Предполагается, что множество $Z$ – структурное. Задача заключается в нахождении расписания с началом в заданном интервале $[T_1,T_2]$ с минимальным штрафом. Вводятся в рассмотрение структурные согласованные расписания. Класс структурных согласованных расписаний содержит решение задачи.
Предлагается алгорифм, решающий задачу со сложностью по наихудшему случаю $O(k\cdot(T_2-T_1+V))$, где $k$ – число работ в множестве $Z$, $V=\sum_{\alpha\in Z}V_\alpha$. Библ. – 5 назв., рис. 9.