Об оптимальных расписаниях с прерываниями для независимых работ в системе обслуживания с приборами

Рассматривается задача составления оптимальных расписаний с прерываниями для системы обслуживания с $N$ идентичными параллельными приборами. На обслуживание поступают $K$ работ, каждая из которых состоит из $V_1$, однородных независимых операций и имеет нижний и верхний директивные сроки $d_i$ и $D_i$. Для операций, составляющих работы, рассматриваются линейные вне интервала $[d_i,D_i]$ функции штрафа. Решается задача о нахождении расписания с минимальным суммарным штрафом с началом в заданном интервале $[t_1,t_2]$.
Доказано, что для произвольного множества работ $Z$ функция штрафа оптимальных расписаний $F_Z(t)$ , где $t$ – начало расписания, имеет единственный минимум при $t\in(-\infty,\infty)$.
Предлагается алгорифм построения оптимального расписания, требующий $C\cdot K(\max_i\{D_i\}-\min_i\{d_i\}+\sum_1^kV_i)$ операций ЭВМ. Библ. 3 назв.