Минимизация максимального штрафа в случае прерывания работ

Для одного класса структурных множеств функций штрафа $\Psi=\{\psi_i\}_{i=1}^n$ с квазивыпуклыми вниз функциями $\psi_i$, заданными для множества работ $\xi=\{\xi_i\}_{i=1}^n$, приводится алгорифм решения задачи $n|1|\mathrm{preemp}|\max\psi$, имеющий порядок $0(np)$, где $n$ – число работ $\xi_i$, $p$ – суммарная длительность выполнения всех работ множества $\xi$. Библ. – 4 назв.