Изменения
Нет описания правки
Приведенный выше алгоритм строит оптимальное расписание.
|proof=
Разделим множество работ <tex>P</tex> на два: <tex>S</tex> - — множество работ, которые успеют выполниться и <tex>F</tex> - — работы, которые не успеют выполниться.Пусть <tex>j</tex> - — первая работа, которая была удалена из <tex>S</tex>. Докажем, что существует оптимальное расписание <tex>P = (S, T)</tex>, в котором <tex>j \in F</tex>. Обозначим через <tex>k</tex> ту работу, которая была последней добавлена в <tex>S</tex>. Тогда <tex>p_j = \max\limits_{i = 1 \dots k} p_i</tex>. При этом в последовательности работ <tex>1, 2, \dots, j-1 j+1, dots, k</tex> не будет ни одной невыполненной работы, поскольку в последовательности <tex>1, 2, \dots, k-1</tex> все работы выполняются вовремя и <tex>p_k \leqslant p_j</tex>. Заменим <tex>j</tex> на <tex>k</tex> и отсортируем все работы.
Теперь рассмотрим оптимальное расписание <tex>P' = (S', F')</tex>, где <tex>j \in S'</tex>. В нём существует последовательность <tex>\pi</tex>: <tex>\pi(1), \dots, \pi(m), \dots, \pi(r), \pi(r+1), \dots, \pi(n)</tex>, такая, что
Таким образом, мы получили оптимальное расписание <tex>P = (S, F)</tex>, в котором <tex>j \in F</tex>.
Теперь докажем теорему индукцией по числу работ. Очевидно, при <tex>n = 1</tex> она выполняется. Предположим, что алгоритм верен для <tex>n - 1</tex> работы. Пусть <tex>P = (S, T)</tex> - — расписание, построенное алгоритмом, а <tex>P' = (S', T')</tex> - — оптимальное расписание с <tex>j \in F'</tex>. Тогда, по отимальности, <tex>|S| \leqslant |S'|</tex>.
Если применить алгоритм ко множеству <tex>\{1, \dots, j-1, j+1, \dots, n\}</tex>, то получим оптимальное расписание для <tex>(S, F\setminus \{j\})</tex>. Т.к. для задачи с меньшим числом станков им будет являться <tex>(S', F' \setminus \{j\})</tex>, то <tex>|S'| \leqslant |S|</tex>, и, следовательно, <tex>|S| = |S'|</tex> и <tex>P</tex> является оптимальным расписанием.
}}
