Изменения

Рассмотрим такое расписание <tex>S^*</tex>, которое как можно дольше совпадает с расписанием S, построенным алгоритмом. Пусть <tex> t~-</tex> первый момент времени, когда в расписании <tex>S</tex> начинает выполняться работа <tex>i</tex>, а в расписании <tex>S^*</tex> работа <tex>j</tex> (причем <tex> i \ne j </tex>). Мы знаем, что <tex> r_i, r_j \leqslant t </tex>, а значит <tex> d_i \leqslant d_j </tex> (поскольку при построении мы выбираем минимальное доступное <tex> d_k </tex>). Пусть <tex> i_1, i_2, ..., i_l~-</tex> все работы, которые находятся в расписании <tex>S^*</tex> между работами <tex>j</tex> и <tex>i</tex> и являются наследниками работы <tex>j</tex>. Кроме того, предположим, что эти работы упорядочены по времени начала выполнения. Теперь, если мы поставим работу <tex>i_l</tex> вместо <tex>i, i_{l-1}</tex> вместо <tex>i_{l}, ..., j</tex> вместо <tex>i_1, i</tex> вместо <tex>j</tex>, то мы снова получим возможное оптимальное расписание <tex> S' </tex>. так как <tex> d_i \leqslant d_j \leqslant d_v </tex>, где <tex> v \in {i_1, i_2, ... i_l} </tex>. Последнее неравенство имеет место быть, поскольку все работы <tex>i_v</tex> являются наследниками работы <tex>j</tex>.

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Теория расписаний]]