Изменения

Упорядочим работы в порядке неубывания дедлайнов. Обозначим за <tex>k</tex> работу с максимальным <tex>p_i</tex>. <br> Будем делить имеющиеся у нас работы на множества <tex> I_1, I_2</tex> так, чтобы для любого <tex>j \geqslant k</tex> <tex>I_1 = \{1,\ldots, j\}\setminus\{k\}</tex>, <tex>I_2 = \{j+1,\ldots, n\}</tex>. Тогда в оптимальном расписании все работы из <tex>I_1</tex> окажутся до <tex>k</tex>, а работы из <tex>I_2</tex> будут расположены после <tex>k</tex>. Для работ из <tex> I_1</tex> оптимальное время начала выполнения <tex>t_1 = 0</tex>, для работ из <tex>I_2</tex> оптимальное начало <tex>t_2 = p = \sum\limits_{i=1}^j p_i</tex>. Таким образом, для любой <tex>j</tex> задача разбивается на две подзадачи. <br> 

{{Лемма|id=l1

Пусть <tex> \pi -</tex> {{---}} любая оптимальная последовательность работ для данных дедлайнов <tex>d_1, d_2,\ldots, d_n</tex>, <tex>C_j -</tex> {{---}} время завершения выполнения <tex>j</tex>-ой работы.  

Рассмотрим последовательность <tex>\pi'</tex> оптимальную для <tex>d'_j</tex>. Тогда <tex>C'_j - </tex> {{---}} время завершения работы <tex>j</tex> в данной последовательности. <br><tex>T( \pi) = T′(\pi) + \sum\limits_{i=1}^n A_j</tex>, <br><tex>T( \pi′) = T ′(\pi′) + \sum\limits_{i=1}^n B_j</tex>, <br>где, <br>

* если <tex>C_j</tex> <tex>\leqslant d_j</tex>, то <br><tex>C_j = \min\{d_j, C_j\} T( \leqslant d'_j \leqslant \max\{d_j, C_j\} pi) = d_j </tex>, из чего следует <tex> w_j\max\{0, C_j ~$-$~ d_j\} = w_j\max\{0, C_j ~$-$~ d'_j\} = 0. </tex> <br><tex>C_j \leqslant d'_j \leqslant d_j </tex>, и, учитывая <tex>C'_j \leqslant d'_j, T′(\enskip d'_j \leqslant C'_j \leqslant d_j</tex> и <tex>d_j \leqslant C'_j,</tex> получаем, что <tex>w_j pi) + \maxsum\limits_{0, C'_j ~$-$~ d_j\} i= w_j\max\{0, C'_j ~$-$~ d'_j\1} - w_j \max\{0, \min\{C'_j, d'_j\} ~$-$~ d_j\} </tex>. <br><tex>^n A_j = 0</tex>, <br><tex>B_j = w_j \max\{0, \min\{C'_j, d_j \} ~$-$~d'_j\} </tex>, <br>

* если <tex>T( \pi′) = T ′(\pi′) + \sum\limits_{i=1}^n B_j </tex>.  Рассмотрим 2 случая: # '''<tex>C_j</tex> <tex>\leqslant d_j</tex>. '''#:Тогда <tex>C_j = \min\{d_j, C_j\} \leqslant d'_j \leqslant \max\{d_j, C_j \geqslant } = d_j </tex>, из чего следует <tex> w_j\max\{0, C_j ~$-$~ d_j\} = w_j\max\{0, C_j ~$-$~ d'_j\} = 0.</tex> #:<tex>C_j \leqslant d'_j \leqslant d_j </tex>, и, учитывая <tex>C'_j \leqslant d'_j, d'_j C'_j \leqslant d_j</tex> и <tex>d_j \leqslant C'_j,</tex> получаем, что <tex>w_j \max\{0, C'_j ~$-$~ d_j\} = w_j\max\{0, C'_j ~$-$~ d'_j\} - w_j \max\{0, \min\{C'_j, d'_j\} ~$-$~ d_j\} </tex>. #:<tex>A_j = 0 </tex>, то #:<brtex>B_j = w_j \max\{0, \min\{C'_j, d_j \} ~$-$~d'_j\} </tex>;# '''<tex>C_j \geqslant d_j</tex>. '''#:Тогда <tex>d_j = \min\{d_j, C_j\} \leqslant d'_j \leqslant \max\{d_j, C_j\} = C_j </tex>, из чего следует <tex> w_j\max\{0, C_j ~$-$~ d_j\} = w_j\max\{0, C_j ~$-$~ d'_j\} + w_j(d'_j ~$-$~ d_j). </tex> <br>#:<tex>d_j \leqslant d'_j \leqslant C_j</tex> , получаем, что <tex>w_j \max\{0, C'_j ~$-$~ d_j\} = w_j\max\{0, C'_j ~$-$~ d'_j\} + w_j \max\{0, \min\{C'_j, d'_j\} ~$-$~ d_j\} </tex>. <br>#:<tex>A_j = w_j(d'_j, d_j), </tex><br>#:<tex>B_j = -w_j \max\{0, \min\{C'_j, d'_j\}~$-$~d'_j\}</tex>. <br>

{{Лемма|id=l2

Пусть <tex>\pi -</tex> {{---}} оптимальная последовательность. Если работа <tex>i</tex> идет после работы <tex>j</tex> в <tex> \pi</tex>, то <tex>d_i \leqslant d_j, p_i < p_j</tex>. Веса работ согласованы, поэтому <tex>w_j \leqslant w_i </tex>, и <tex>w_j\max\{0,T ~$-$~ d_j\} \leqslant w_i\max\{0,T ~$-$~ d_i\}</tex> выполняется для всех Т. Таким образом, если поместить работу <tex>j</tex> сразу после <tex>i</tex>, расписание останется оптимальным. <br> 

Обозначим за <tex>C'_k</tex> максимально возможное время завершения работы <tex>k</tex> в любой последовательности, которая оптимальна в соответствии с <tex>d_1, d_2,\ldots, d_n</tex>. Обозначим за <tex>\pi</tex> оптимальную последовательность, соответствующую <tex>d_1, d_2,\ldots, d_k ~$-$~ 1, d'_k = \max\{C'_k, d_k\}, d_k+1,\ldots, d_n</tex> и удовлетворяющую условиям Леммы 2[[#l1 | леммы]]. Обозначим за <tex>C_k</tex> время завершения работы <tex>k</tex> из <tex>\pi</tex>. <br> Согласно Лемме 1[[#l1 | лемме]], последовательность <tex>\pi</tex> оптимальна для исходных <tex>d_1, d_2,\ldots, d_n</tex>. Тогда по определению <tex>C'_k</tex>: <tex>C_k \leqslant C'_k \leqslant \max\{C'_k, d_k\}, \enskip </tex> <tex> d'_k = \max\{C'_k, d_k\}, \enskip </tex> <tex>C_k \leqslant C'_k \leqslant d'_k</tex>. Таким образом, работе <tex>k</tex> не может предшествовать работа <tex>j</tex> такая, что <tex>d_j</tex> > <tex>d'_k</tex>. Иначе работа j тоже была бы выполнена вовремя, что противоречит условиям Леммы 2[[#l2 | леммы]]. С другой стороны, работе <tex>k</tex> должны предшествовать все работы <tex>j \ne k</tex> такие, что <tex>d_j \leqslant d'_k</tex>, так как <tex>p_j > p_k</tex>. Если мы выберем в качеству работы <tex>j^*</tex> самую большую работу такую, что <tex>d_j ^* \leqslant d'_k,\enskip </tex> <tex>d'_k = \max\{C'_k, d_k\}</tex>, тогда <tex>j ^* \geqslant k</tex>, так как <tex>d_j ^* \leqslant d'_k</tex> и <tex>j^*</tex> обладает необходимыми свойствами.

Пускай все времена выполнения работ различны. Тогда все множества работ, используемые в качестве аргументов рекурсивного вызова функции можно представить в виде <tex>\langle i, j, k \rangle : \{ v \mid i \leqslant v \leqslant j \wedge p_v < p_k\}</tex>. , <tex> i, j, k \in \{1, 2, \ldots, n\}<br/tex>. У нас максимум <tex> p = \sum\limits_{i=1}^n p_i</tex> различных значений <tex>t</tex>. Значит, нам нужно вызвать мы вызовем <tex>\mathrm{sequence(t,I) \enskip }</tex> в худшем случае <tex>\mathcal{O}(n^3p)</tex> раз. Более того, для фиксированного <tex>k</tex> все значения <tex>\max\{p_v \mid v \in I_{ijk}\}</tex> для <tex>i, j = 1,\ldots, n,</tex> <tex>i < j</tex> могут быть сосчитаны за <tex>\mathcal{O}(n^2)</tex>. <br>