Изменения

Заметим, что если <tex>d_i < m</tex>, то очевидно, что <tex>C_i > d_i</tex>, следовательно, расписания не существует. Поэтому будем полагать, что <tex>m \leqslant d_i</tex> для <tex>i = 1 \ldots n</tex>. Определим <brtex>T = \max\limits_{i \in [1, n]}d_i</tex> {{---}} количество временных интервалов <tex>[t - 1, t]</tex>, где <tex>t = 1 \ldots T</tex>. Будем обозначать <tex>[t - 1, t]</tex> как <tex>t</tex>. Для каждого из них мы можем назначить не более <tex>m</tex> работ (по одной на каждый станок). Для каждой работы <tex>i</tex> будем назначать времена обработки на каждой из машин следующим образом: на машине <tex>m</tex> работа займет временной интервал <tex>d_i</tex>, на машине <tex>(m - 1)</tex> {{---}} интервал <tex>(d_i - 1)</tex> и так далее, на машине <tex>1</tex> работа займет временной интервал <tex>d_i - m + 1</tex>. В случае коллизий, то есть если найдется временной интервал <tex>k > 1</tex>, содержащий <tex>m + 1</tex> работу, возьмем минимальный такой <tex>k</tex> и перенесем лишнюю работу из него на ту же машину, но на один временной интервал левее. Будем повторять этот процесс, пока необходимо (и пока <tex>k > 1</tex>). Таким образом, только первый временной интервал может содержать более <tex>m</tex> работ. Причем это может произойти тогда и только тогда, когда задача не имеет решения, то есть не существует расписания, при котором все работы будут выполнены вовремя.=== Псевдокод ===Определим <tex>h(t)</tex> {{---}} количество работ во временном интервале <tex>t</tex>.  '''void''' checkExistenceOfSchedule('''int'''* <tex>d</tex>): <tex>T = \max\{d_i \mid i = 1 \ldots n\}</tex> '''for''' <tex>t = 1</tex> '''to''' <tex>T</tex> <tex>h(t) = 0</tex> '''for''' <tex>i = 1</tex> '''to''' <tex>n</tex> '''for''' <tex>j = d_i</tex> '''to''' <tex>d_i - m + 1</tex> <tex>h(j) = h(j) + 1</tex> '''while''' <tex>\exists k > 1</tex> '''and''' <tex>h(k) = m + 1</tex> '''find''' <tex>\min\{k_0 \mid h(k_0) = m + 1\}</tex> <tex>h(k_0 - 1) = h(k_0 - 1) + 1</tex> <tex>h(k_0) = m</tex> '''if''' <tex>h(1) \leqslant m</tex> '''return''' true '''else''' '''return''' false=== Асимптотика ===== Доказательство корректности =={{Теорема|statement=Для множества работ с дедлайнами tex>d_1, d_2, \ldots d_n</tex> задача имеет решение тогда и только тогда, когда <tex>h(1) \leqslant m</tex>.|proof=}}