Изменения

* множество <tex>C</tex> {{---}} итерации обработки работ <tex>i = k + 1 \ldots n</tex>, которые в <tex>S^*</tex> запланированы на время <tex>k + m + t</tex>и раньшеТаким образом, мы имеем три непересекающихся множества, которые вместе с работой <tex>k</tex> покрывают все итерации всех работ.<br>Построим новое расписание <tex>S^*</tex>. Для начала расставим все работы из множества <tex>A \cup B</tex> так же, как они были запланированы в расписании <tex>S^*</tex>. Так как <tex>C_i \leqslant m + i - 1</tex> для <tex>i = 1 \ldots k - 1</tex>, ни одна итерация обработки в множестве <tex>B</tex> не поставлена раньше момента времени <tex>k + m + t</tex> и к моменту времени <tex>C_k = m + k + t</tex> выполнено <tex>k</tex> работ, то это значит, что между моментами времени <tex>0</tex> и <tex>k + m - 1</tex> на каждой машине есть <tex>m</tex> различных простоев, то есть моментов, когда на ней ничего не обрабатывается. Значит, мы всегда сможем поставить на эти простои итерации обработки работы <tex>k</tex>, даже если эти простои пересекаются. Таким образом, <tex>C_k \leqslant m + k - 1</tex>.