Изменения

Рассмотрим оптимальное расписание <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>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>.<br>Теперь назначим машины для операций из множества <tex>C</tex>. До момента времени <tex>k + m + t</tex> сейчас распланировано ровно <tex>k</tex> работ, так как по определению работы из множества <tex>B</tex> запланированы на время строго большее <tex>k + m + t</tex>. Значит, между моментами времени <tex>0</tex> и <tex>k + m + t</tex> есть <tex>k + m + t - k = m + t</tex> различных простоев на каждой машине. Исходя из определения множества <tex>C</tex> и того, что к моменту <tex>k + m + t</tex> распланировано <tex>km</tex> итераций обработок, приходим к неравенству <tex>|C| \leqslant (k + m + t)m - km = (m + t)m</tex>. Значит, мы можем распланировать итерации из множества <tex>C</tex> не позднее момента <tex>k + m + t</tex>. Таим образом, мы снова построили расписание для задачи open shop, которое так же является оптимальным, так как для множеств <tex>A</tex> и <tex>B</tex> все осталось как в оптимальном расписании <tex>S^*</tex>, работу <tex>k</tex> мы научились выполнять быстрее, а для множества <tex>C</tex> ответ был не ухудшен. Любая работа <tex>j</tex>, итерации обработки которой принадлежат множеству <tex>C</tex>, имела время окончания <tex>C_j \geqslant m + k + t</tex>. Однако это противоречит тому, что мы выбрали максимальное <tex>k</tex>.