Изменения

Упорядочим работы в порядке неубывания дедлайнов. Обозначим за <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 = \{j+1,..., n\}</tex> были будут расположены после <tex>k</tex>. Оптимальное Для работ из <tex> I_1</tex> оптимальное время начала выполнения всех работ из <tex> I_1 \enskip t_1 = 0</tex>, для работ из <tex> I_2 \enskip </tex> оптимальное начало <tex>t_2 = p = \sum\limits_{i=1}^j p_i</tex>. Таким образом, для любой <tex>j</tex> задача разбивается на 2 подзадачи. <br>

Приведенный ниже алгоритм вычисляет оптимальную последовательность работ <tex>\pi</tex>для множества работ <tex>I = \{i_1, i_2, ...\ldots, i_r\}</tex> в начальный момент времени <tex>t</tex>.

'''function''' <tex> \mathrm{Sequence}sequence(t: '''int''', I: '''int[]''')</tex>:'''int[]'''

'''return''' <tex>\pi = \varnothing</tex> '''else''' find <tex>i_k : p_{i_k} = \max\{p_i \mid i \in I\}</tex> <tex>f^* = \infinfty</tex> '''for''' <tex>j = k</tex> '''to''' <tex>r</tex> <tex>I_1 := \{i_v \mid 1 \leqslant v \leqslant j; \wedge v \ne k\};</tex> <tex>t_1 := t; </tex> <tex>\pi_1 := \mathrm{Sequence} sequence (t_1 , I_1 );</tex> <tex>I_2 := \{i_v \mid j < v \leqslant r\};</tex> <tex>t_2 := t + \sum\limits_{v=1}^j p_{i_v};</tex> <tex>\pi_2 := \mathrm{Sequence}sequence(t_2 , I_2 );</tex> <tex>\pi:=\pi_1 \circ cup \{i_k \circ } \cup \pi2;</tex> вычисляем значение <tex>f(\pi, t)</tex> '''if''' <tex>f(\pi, t) < f^*</tex> <tex>\pi^* := \pi; </tex> <tex>f^* := f(\pi, t)</tex>

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

<tex>T( \pi′) = T ′(\pi′) + <tex> \sum\limits_{i=1}^n B_j</tex>, <br>где, <br> * если <tex>C_j</tex> <tex>\leqslantd_j</tex>, то <br><tex>C_j = \min\{d_j, C_j\} \leqslant d'_j \leqslant \max\{d_j, C_j\} = 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, \enskip d'_j \leqslant 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>. <br>

<tex>B_j = w_j \max\{0, \min\{C'_j, d_j \} ~$- $~d'_j\} </tex>, <br> * если <tex>C_j \geqslant d_j</tex>, то <br><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>B_j = -w_j \max\{0, \min\{C'_j, d'_j\} ~$- $~d'_j\}</tex>. <br>Если <tex> C_j \leqslant d_j, C_j = \min\{d_j, C_j\} \leqslant d'_j \leqslant \max\{d_j, C_j\} = 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 \geqslant d_j, 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> C_j \leqslant d_j</tex>, тогда <tex>C_j \leqslant d'_j \leqslant d_j </tex>, и, учитывая <tex>C'_j \leqslant d'_j, d'_j \leqslant C'_j \leqslant d_j и 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> d_j \leqslant C_j</tex>, тогда <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 \geqslant B_j</tex> при любом j, значит <tex>\sum\limits_{i=1}^n A_j \geqslant \sum\limits_{i=1}^n B_j</tex>. Кроме того, <tex>T(\pi) \geqslant T(\pi')</tex>, так как <tex>\pi'</tex> минимизирует <tex>T'</tex>. <tex>T(\pi) \geqslant T(\pi')</tex> и <tex>\pi'</tex> оптимально для <tex>d_i. </tex>.

Пусть веса работ согласованы (из <tex>p_i < p_j</tex> следует <tex>w_i \geqslant w_j</tex>). Тогда существует оптимальная последовательность <tex> \pi </tex>, в которой работа <tex>i</tex> предшествует работе <tex>j</tex>, если <tex> d_i \leqslant d_j</tex> и <tex> p_i </tex>< <tex>p_j</tex>, и все работы, выполненные до дедлайна, упорядочены в неубывающем порядке <tex>d_i</tex>.

Пусть <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>

|statement= Пусть работы <tex>j_1, j_2, ...\ldots, j_n</tex> отстортированы в порядке неубывания дедлайнов, и веса согласованы. Обозначим за <tex>k</tex> работу с наибольшим <tex>p_i</tex>.Тогда существует работа <tex>j^* \geqslant k</tex> такая, что в оптимальном расписании все работы <tex>v = 1, ...\ldots, j^*, v \ne k</tex> размещены до <tex>k</tex>, а оставшиеся работы размещены после <tex>k</tex>.

Обозначим за <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. Обозначим за <tex>C_k</tex> время завершения работы <tex>k</tex> из <tex>\pi</tex>. <br>Согласно Лемме 1, последовательность <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 d'_k = \max\{C'_k, d_k\}, \enskip 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. С другой стороны, работе <tex>k</tex> должны предшествовать все работы <tex>j \ne k</tex> такие, что <tex>d_j \leqslant d'_k</tex>, так как<tex>p_j</tex> > <tex>p_k</tex>. Если мы выберем в качеству работы <tex>j^*</tex> самую большую работу такую, что <tex>d_j ^* \leqslant d'_k,\enskip 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</tex> < <tex>p_k\}</tex>, то есть могут быть полностью заданы тройкой чисел <tex>\langle i, j, k \rangle</tex>. <br>У нас максимум <tex> p = \sum\limits_{i=1}^n p_i</tex> различных значений <tex>t</tex>. Значит, нам нужно вызвать <tex>\mathrm{Sequence}sequence(t,I) \enskip \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</tex> < <tex>j</tex> могут быть сосчитаны за <tex>\mathcal{O}(n^2)</tex>. <br>