Изменения

В псевдокоде используются переменные:*<tex> s </tex> {{---}} множество непросроченных работ, *<tex> t </tex> {{---}} текущее время.

 :Так как работа <tex> k </tex> не содержится в <tex> S </tex>, то либо она не была добавлена при ее рассмотрении, либо была заменена работой, рассмотренной позднее. В любом случае это означает, что <tex> w_{k} \leqslant w_{l} </tex>. Так же по определению <tex> k </tex> все работы <tex> i \in S^* : i < k </tex> должны содержаться и в <tex> S </tex>. Но тогда заменив в оптимальном расписании <tex> k </tex> на <tex> l </tex>, мы сохраним корректность расписания и не увеличим минимизируемую функцию. 

:Так как мы рассматриваем работы в порядке неубывания их дедлайнов, то, следовательно, <tex> d_{k} \leqslant d_{l} </tex>, и замена работы <tex> k </tex> на <tex> l </tex> в оптимальном расписании <tex> S^* </tex> не может сделать его некорректным. Тогда для доказательства нам осталось показать, что <tex> w_{k} \leqslant w_{l} </tex>. :Пусть <tex> k_{i_{0}} = k </tex> {{---}} работа, замененная работой <tex> i_{0} </tex> в процессе построения <tex> S </tex>, и пусть <tex> k_{i_{1}}, ..., k_{i_{r}} </tex> {{---}} последовательность работ, которые были исключены из <tex> S </tex> после замены <tex> k </tex>, причем работа <tex> k_{i_{v}} </tex> была заменена работой <tex> i_{v} </tex>. <tex> i_{0} < i_{1} < ... < i_{r} </tex>. Будем говорить, что "работа <tex> i_{v} </tex> подавляет <tex> i_{m} </tex>", где <tex> m < v </tex>, если <tex> k_{i_{v}} \leqslant i_{m} </tex>. В таком случае получаем, что <tex> w_{k_{i_{v}}} \geqslant w_{k_{i_{m}}}</tex>, потому что в противном случае работа <tex> k_{i_{v}} </tex> была бы исключена из <tex> S </tex> раньше чем <tex> k_{i_{m}} </tex>.

:Если в последовательности <tex> i_{0} < i_{1} < ... < i_{r} </tex> существует подпоследовательность <tex> j_{0} = i_{0} < j_{1} < ... < j_{s} </tex> такая, что <tex> j_{v + 1} </tex> подавляет <tex> j_{v} </tex> для всех <tex> v = 0,1, ..., s - 1 </tex> и <tex> j_{s - 1} < l \leqslant j_{s} </tex>, то получаем, что <tex> w_{l} \geqslant w_{k_{j_{s}}} \geqslant ... \geqslant w_{k_{j_{0}}} = w_{k} </tex>, что доказывает оптимальность расписания <tex> S </tex>.

:Покажем, что отсутствие такой подпоследовательности приведет нас к противоречию, из чего будет следовать ее существование.

:Предположим, что такой подпоследовательности не существует. Тогда найдем наименьшее <tex> t </tex> такое, что не существует работы <tex> i_{v} : v > t </tex>, которая бы подавляла работу <tex> i_{t} </tex>, и <tex> i_{t} </tex> было бы меньше <tex> l </tex>. По определению <tex> l </tex> и <tex> i_{t} </tex> и из факта, что <tex> i_{t} < l </tex>, получаем, что после добавления во множество <tex> S </tex> работы <tex> i_{t} </tex>, ни одна из работ, рассмотренных ранее, не будет удалена из <tex> S </tex>, а так же все эти работы содержатся и в оптимальном расписании <tex> S^* </tex>, поскольку <tex> i_t < l </tex>.

:Пусть <tex> S_t </tex> это множество <tex> S </tex> после замены работы <tex> k_{i_t} </tex> на <tex> i_t </tex>. Если <tex> k_{i_t} > k </tex>, то в оптимальном расписании <tex> S^* </tex> мы можем заменить работу <tex> k </tex> на <tex> k_{i_t} </tex>, поскольку <tex> d_{k_{i_t}} \geqslant d_k </tex>. Но так как <tex> S_t \subset S^* </tex>, то все работы из множества <tex> S_t \cup \{k_{i_t}\} </tex> могут быть выполнены до их дедлайнов, что противоречит построению <tex> S </tex>. Следовательно, <tex> k_{i_t} < k </tex>. Тогда аналогично предыдущему случаю получаем, что все работы из множества <tex> S_t \cup \{k\} </tex> могут быть выполнены вовремя. Кроме того, все работы из <tex> \{ j \in S_t | j < k \} \cup \{k_{i_t}\} </tex> так же могут быть выполнены вовремя, что следует из построения <tex> S_t </tex>. Но тогда получается, что все работы и из множества <tex> S_t \cup \{k_{i_t}\} </tex> так же могут быть выполнены вовремя, что опять приводит нас к противоречию с построением <tex> S </tex>.