Изменения
→Алгоритм
{{Теорема
|statement=
Этот алгоритм строит оптимальное расписание.
|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>F' = \{\pi(r+1), \dots, \pi(n)\}</tex>;
* <tex>d_{\pi(1)} \leqslant \dots \leqslant d_{\pi(r)}</tex>;
* <tex>\{\pi(1), \dots, \pi(m)\} \subseteq \{1, \dots, k\}</tex>;
* <tex>\{\pi(m+1), \dots, \pi(r)\} \subseteq \{k+1, \dots, n\}</tex>;
* <tex>j \in \{\pi(1), \dots, \pi(m)\}</tex>;
Такое <tex>m</tex> всегда найдётся, т.к. <tex>d_1 \leqslant d_2 \leqslant \dots \leqslant d_n</tex>, а последнее будет следовать из того, что <tex>j \in S' \cap \{1, \dots, k\}</tex>. Из того, что <tex>\{\pi(1), \dots, \pi(m)\} \subseteq S'</tex> следует, что выполнятся все работы из <tex>\{\pi(1), \dots, \pi(m)\}</tex>. С другой стороны, при любом расписании не будет выполнена какая-то работа из <tex>\{1, \dots, k\}</tex>. Поэтому <tex>\{\pi(1), \dots, \pi(m)\} \subset \{1, \dots, k\}</tex>, при этом существует работа <tex>h \notin \{\pi(1), \dots, \pi(m)\}</tex>. Удалим работу <tex>j</tex> из <tex>\{\pi(1), \dots, \pi(m)\}</tex> и заменим на <tex>h</tex>. Если отсортируем получившееся множество, то все работы в нём выполнятся, т.к. <tex>\{\pi(1), \dots, \pi(m)\} \cup \{h\} \cap \{j\} \subseteq \{1, \dots, k\} \setminus \{j\}</tex>, а оно обладает таким свойством. Если добавим работы <tex>\pi(m+1), \dots, \pi(r)</tex> к множеству <tex>\{\pi(1), \dots, \pi(m)\} \cup \{h\} \cap \{j\}</tex> и отсортируем его по неубыванию дедлайнов, то все работы в нём выполнятся, т.к. из <tex>p_h \leqslant p_j</tex> следует, что
<tex>\sum_{i=1}^{m} p_{\pi(i)} - p_j + p_h \leqslant \sum_{i=1}^{m} p_{\pi(i)}</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> является оптимальным расписанием.
}}
