Изменения
Нет описания правки
{{Утверждение #2
|statement= Если существует расписание без опоздание, то приведенный выше алгоритм найдет такое расписание.
|proof= Пусть <tex>x(1), x(2),...,x(n)</tex>~{{---}} расписание, построенное этим алгоритмом, где <tex>x(i)</tex>~{{--- }} время
начала обработки <tex>i</tex>-ой детали. Пусть в этом расписании существует работа, опаздывающая по обычным дедлайнам. Согласно
утверждению 1, в этом расписании также существует работа, опаздывающая по "вынужденным" дедлайнам. Пусть <tex>i</tex> {{---}} такая работа с минимальным временем начала, то есть, удолетворяющая следующему условию: <tex>d'_i < x(i) + 1</tex>. Следуя алгоритму, в каждый момент времени
<tex>t</tex>, такой что <tex>t < x(i)</tex>, хотя бы одна работа с номером <tex>j</tex>, такая что <tex>d'_j \le d'_i</tex> должна
быть выполнена, так как, иначе, по алгоритму, вместо <tex>i</tex> на этом шаге была бы выбрана работа <tex>j</tex>, имеющая меньшее <tex>d'</tex> и, по построению модифицированных дедлайнов, независимая от <tex>i</tex>.
Рассмотрим два случая.
'''Первый случай''': в какой-то момент времени только одна работа с номером <tex>k</tex>, такая что <tex>d'_k \le d'_i</tex> выполнена.
Выберем максимальное время <tex>t</tex>, такое что <tex>t < x(i)</tex>, обладающее таким свойством. Тогда для всех работ c номером
<tex>j</tex>, которые выполнялись в момент времени с <tex>t+1</tex> до <tex>x(i)</tex> выполняется <tex>d'_j \le d'_i</tex>, кроме того, ни один станок не простаивал в течении этого периода. Все работы <tex>j</tex>, выполненные в период <tex>[t+1; x(i)]</tex>, а также, работа <tex>i</tex>, должны быть зависимы от <tex>k</tex>, потому что, иначе, только <tex>j</tex> должна быть выполнена до момента времени <tex>t+1</tex>. Так как было опоздание, <tex>\left\lceil \frac{g'(k, d'_i)}{2} \right\rceil \ge \left\rceil\frac{2(x(i) - t) - 1}{2} \right\rceil = x(i) - t</tex> Из определения вынужденных дедлайнов, <tex>d'_k \le d'_i - \left\lceil \frac{g(k, d'_i)}2 \right\rceil</tex><tex>\le d'_i - x(i) + t < x(i) + 1 - x(i) + t = t + 1</tex> Значит, работа <tex>k</tex> тоже опоздала, что противоречит минимальности выбора <tex>x(i)</tex>.
}}
