Изменения

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