Изменения

<tex dpi = "200"> O \mid p_{i,j} = 1 \mid \sum w_{i} U_{i} </tex>

Дано <tex>m</tex> одинаковых станков, которые работают параллельно, и <tex>n</tex> работ, которые необходимо выполнить в произвольном порядке на всех станках. Любая работа на любом станке выполняется за единицу времени. Для каждой работы есть время окончания <tex>d_id_{i}</tex> {{---}} время, до которого она должна быть выполнена. Требуется минимизировать <tex>\sum w_{i} U_{i}</tex>, то есть суммарный вес всех просроченных работ.

==АлгоритмОписание алгоритма==Идея алгоритма состоит в томДля решения этой задачи, что на шаге мы должны найти множество <tex>kS</tex> строим оптимальное решение для первых работ, которые успеваем выполнить до дедлайна. Значит нам надо минимизировать: <tex>k\sum\limits_{ i \notin S } {w_{i}}</tex> работ . Будем решать эту задачу с помощью [[Динамическое_программирование|динамического программирования]] с наименьшими дедлайнамииспользованием утверждений из решения задачи [[Opij1di|<tex> O \mid p_{i, j} = 1, d_{i} \mid - </tex>]].

Пусть Рассмотрим работы отсортированы в порядке возрастания неубывания дедлайнов. Пусть мы уже рассмотрели первые : <tex>k</tex> работ, тогда множество <tex>S_k</tex> содержит только те работы, которые мы успеваем выполнить в порядке возрастания дедлайнов при оптимальном расписании. Рассмотрим работу <tex>k+d_{1</tex>. Если мы ее успеваем выполнить данную работу, до наступления дедлайна, то добавим в множество <tex>S_} \leqslant d_{k2}</tex> и получим множество <tex>S_\leqslant \ldots \leqslant d_{k+1n}</tex>. Если же Пусть мы нашли решение для работ <tex>k+1, 2, \ldots, i - 1</tex> работу мы не успеваем выполнить до дедлайна. Очевидно, то найдем в что <tex>S_k</tex> работу <tex>l</tex> c наименьшим весом <tex>w_S \subseteq \{l1, \ldots , i - 1\}</tex> и заменим ее на работу <tex>k+1</tex>.

Таким образомПусть <tex>h^S</tex> {{---}} вектор соответствующий множеству <tex>S</tex> из задачи [[Opij1di|<tex> O \mid p_{i, j} = 1, d_i \mid - </tex>]]. Тогда, рассмотрев все для добавления работы<tex>i</tex> в множество <tex>S</tex> должно выполняться неравенство: <tex>m \cdot (d_{i} - m) - ( k m - \sum \limits_{j = 1}^m {h^S(d_{i} - m + j)})+x(d_{i}) \geqslant m</tex>, мы получим где <tex>k = |S|</tex>S_и <tex>x(d_{ni})</tex> {{---}} количество периодов времени <tex>t</tex> со свойствами: <tex>d_{i} - m + 1 \leqslant t \leqslant d_{i}</tex> и <tex>h^S(t) < m</tex>. Чтобы проверить это неравенство, нам нужно посчитать <tex>m</tex> чисел <tex>h^S(t)</tex> — множество работ, которые мы успеваем выполнить до наступления их дедлайнов<tex>t=d_{i} - m + 1, причем вес просроченных работ будет наименьшим. От порядка выполнения просроченных работ ничего не зависит\ldots, поэтому расположить в расписании их можно произвольным образомd_{i}</tex>.Для этого определим переменные:

==Псевдокод==Предполагаем, что перед началом выполнения алгоритма выполняется, что <tex>k_{j} = \begin{cases} h^S(d_{i} - m + j) & j \in \leqslant d_{1, \ldots , m\} \leqslant d_\0 & j \notin \{21 , \ldots , m\} \leqslant ... \leqslant d_\end{ncases}</tex>. Все работы, дедлайн которых меньше <tex>m</tex>, мы в любом случае выполнить без штрафа не успеем, поэтому их изначально можно отнести к просроченным.

<tex>S</tex> l_j = \begin{cases}1 & j \in \{---1 , \ldots , m\}\text{; } множество непросроченных работ, <tex>Check</tex> k_{{---j}} функция, решающая задачу [[Opij1di|<tex> O m \\0 & \mid p_text{i,jotherwise} = 1, d_i \mid - \\end{cases} .</tex>]].

S = Тогда можно заметить, что <tex>x(d_{i}) = \sum\varnothinglimits_{j = 1}^m {l_{j}}</tex> '''for''' i , так как <tex>l_{j} = 1 to n </tex> если <tex>1 \leqslant j \leqslant m</tex> и <tex>h^S = (d_{i} - m + j) < m</tex> или <tex> S d_{i} - m + 1 \cup leqslant d_{i} - m + j \leqslant d_{i\} </tex> '''if''' ''not'' Checkи <tex>h^S(sd_{i} - m + j) : найти такое <tex>km</tex>, что . Следовательно можно упростить исходное неравенство: <tex>w_m \cdot (d_{i} - m) - (k} = m - \min sum \limits_{ w_j = 1}^m {k_{j} }) + \sum \mid limits_{j = 1}^m {l_{j }} \in S\}geqslant m</tex> S = или <tex>S \setminus m \cdot (d_{i} - m - k)+ \sum\limits_{j = 1}^m {(k_{j} + l_{j})} \geqslant m</tex>.

Для динамического программирования определим <tex>f_{i} (k , k_{1} , \ldots , k_{m})</tex> {{---}} минимальное значение целевой функции для расписания работ <tex>i , i + 1 , \ldots , n</tex>, позволяющее выполнить работы из множества <tex>S</tex> без опоздания, где <tex>k =|S|, S \subseteq \{1, \ldots , i - 1\}</tex> и <tex>k_{j}=Доказательство корректностиh^S(d_{i} - m + j)</tex>, где <tex>j =1, \ldots , m</tex>, то есть <tex>f_{i} (k, k_{1}, \ldots , k_{m}) =\min \limits_{S: |S| = k, S \subseteq \{1, \ldots , i - 1 \}} (\sum \limits_{j = i}^n {w_{j} U_{j}})</tex>.

{{Утверждение|statement=Алгоритм строит корректное расписание.|proof=Если мы успеваем выполнить очередную работу, то, очевидно, от ее добавления, расписание не может стать некорректным. В противном случае мы пытаемся заменить одну работу из множества <tex> S </tex> на текущую. Но это так же не может сделать наше расписание некорректным. Это следует из того, что мы рассматриваем работы в порядке неуменьшениях их дедлайнов. Пусть мы заменяем работу <tex> k </tex> на работу <tex> i </tex>. Но <tex> p = d_{ki + 1} \leqslant - d_{i} </tex>, следовательно, если мы успевали выполнить работу <tex> k </tex>, то успеем выполнить и работу тогда определим рекуррентное выражение для <tex> f_{i </tex>.}} {{Теорема|statement=Построенное данным алгоритмом расписание оптимально.|proof=Пусть <tex> S^* </tex> множество непросроченных работ в оптимальном расписании. Также пусть <tex> l </tex> {{---}} первая работа из множества <tex> S </tex>(k, которая не входит в <tex> S^* </tex>, а <tex> k </tex> k_{{---1}} первая работа из <tex> S^* </tex>, не содержащаяся в <tex> S </tex>. Мы можем предполагать существование этих работ, потому что <tex> S^* </tex> не может содержать <tex> S </tex> как подмножество, иначе это противоречило бы построению <tex> S </tex>. С другой стороны, если <tex> S^* \subseteq S </tex>ldots , то <tex> S k_m)</tex> должно быть тоже оптимальным, и правильность алгоритма доказана. Для доказательства покажем, что мы можем заменить работу <tex> k </tex> на работу <tex> l </tex> в оптимальном расписании, не увеличивая минимизируемую функцию. Рассмотрим два случая:

*<tex> l < f_{i} (k </tex>, k_{1}, \ldots , k_{m}) = \begin{cases}Так как работа <tex> f_{i + 1} (k </tex> не содержится в <tex> S </tex>, то либо она не была добавлена при ее рассмотренииk_{1 + p}, либо была заменена работойk_{2 + p}, рассмотренной позднее. В любом случае это означает\ldots, что <tex> k_{m + p}) + w_{ki} , & m \leqslant w_cdot (d_{li} </tex>. Так же по определению <tex> - m - k )+ \sum \limits_{j = 1}^m {(k_{j} + l_{j})} </tex> все работы <tex> i m \text{ } (1)\\\in S^* : min(f_{i < + 1} (k </tex> должны содержаться и в <tex> S </tex>. Но тогда заменив в оптимальном расписании <tex> k </tex> на <tex> l </tex>, мы сохраним корректность расписания и не увеличим минимизируемую функцию.*<tex> k < l </tex>Так как мы рассматриваем работы в порядке неубывания их дедлайновk_{1 + p}, тоk_{2 + p}, следовательно\ldots , <tex> d_k_{m + p}) + w_{i} ; f_{i + 1} (k+ 1, k_{1 + p} + l_{1 + p}, k_{2 + p} + l_{2 + p} , \leqslant d_ldots , k_{m + p} + l_{lm + p} </tex>)), и замена работы <tex> & m \cdot (d_i - m - k </tex> на <tex> l </tex> в оптимальном расписании <tex> S) + \sum \limits_{j = 1}^* </tex> не может сделать его некорректным. Тогда для доказательства нам осталось показать, что <tex> w_m {(k_{j} + l_{j})} \geqslant m \text{k} (2)\\\leqslant w_end{lcases} </tex>.

Пусть c начальным условием: <tex> k_f_{i_{0n + 1}} = (k </tex> {{---}} работа, замененная работой <tex> i_{0} </tex> в процессе построения <tex> S </tex>, и пусть <tex> k_{i_{1}}, ...\ldots , k_{i_{r}m} ) = 0 </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>"\ldots , где <tex> m < v </tex>, если <tex> k_{i_{v}} \leqslant i_{m} </tex>. В таком случае получаем= 0, 1, что <tex> w_{k_{i_{v}}} \geqslant w_{k_{i_{m}}}</tex>ldots , потому что в противном случае работа <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} i</tex> такая, что в множество <tex> j_{v + 1} S</tex> подавляет и поэтому <tex> j_f_{vi} </tex> для всех <tex> v = 0(k,k_{1} \ldots , ..., s - 1 </tex> и <tex> j_k_{s - 1m} < l \leqslant j_) = f_{si + 1} </tex>(k, то получаем, что <tex> w_k_{l1 + p} \geqslant w_{, k_{j_{s}}2 + p} , \geqslant ... \geqslant w_{ldots, k_{j_{0m + p}}} = ) + w_{ki} </tex>, что доказывает оптимальность расписания <tex> S </tex>.

ПокажемЕсли выполняется неравенство <tex>(2)</tex>, что отсутствие такой подпоследовательности приведет нас к противоречиютогда мы может добавить работу <tex>i</tex> в множество <tex>S</tex> или не добавлять. Если мы добавим работу <tex>i</tex>, то <tex>f_{i} (k, k_{1}, \ldots , k_{m}) = f_{i + 1}(k + 1, k_{1 + p} + l_{1 + p}, k_{2 + p}+l_{2 + p}, \ldots , k_{m + p}+l_{m + p}) \text{ } (3)</tex>. Если мы не добавим работу <tex>i</tex>, то по аналогии с первым случаем <tex>f_{i} (k, k_{1}, \ldots , k_{m}) = f_{i + 1} (k, k_{1 + p},k_{2 + p}, \ldots, k_{m + p}) +w_{i} \text{ } (4)</tex>. Так как <tex>f_{i} (k, k_{1}, \ldots , k_{m}) = \min(\sum \limits_{j = i}^n {w_{j} U_{j}})</tex>, то нам надо взять минимум из чего будет следовать ее существованиезначений <tex>(3)</tex> и <tex>(4)</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_f_{t1} </tex> и из факта(0, что <tex> i_{t} < l </tex>0, получаем\ldots , что после добавления во множество <tex> S </tex> работы <tex> i_{t} </tex>, ни одна из работ, рассмотренных ранее, не будет удалена из <tex> S </tex>, а так же все эти работы содержатся и в оптимальном расписании <tex> S^* </tex>, поскольку <tex> i_t < l 0)</tex>.

==Пример работы==Пусть <tex> S_t m = 2</tex> это множество и <tex> S n = 3</tex> после замены . {| class="wikitable" style="width:5cm" border=1|+|-align="center" bgcolor=#EEEEFF! номер работы <tex> k_{i_t|| дедлайн || вес|-align="center" bgcolor=#FFFFFF| 1 || 2 || 7 |-align="center" bgcolor=#FFFFFF| 2 || 2 || 6 |-align="center" bgcolor=#FFFFFF| 3 || 2 || 5 |} Для такой задачи получится таблица для функции </tex> на <tex> i_t f</tex>. Если :{| class="wikitable" style="width:20cm" border=1|+|-aling="center" bgcolor=#EEEEFF! <tex> k_{i_t} > k </tex>, то в оптимальном расписании || <tex> S^* k_1</tex> мы можем заменить работу || <tex> k k_2</tex> на || <tex> k_f_{i_t4} (k, k_1, k_2)</tex>, поскольку || <tex> d_f_{k_{i_t3}} \geqslant d_k (k, k_1, k_2)</tex>. Но так как <tex> S_t \subset S^* </tex>, то все работы из множества || <tex> S_t \cup \f_{k_{i_t2}\} </tex> могут быть выполнены до их дедлайнов(k, k_1, что противоречит построению <tex> S k_2)</tex>. Следовательно, || <tex> k_f_{i_t1} < (k </tex>. Тогда аналогично предыдущему случаю получаем, что все работы из множества <tex> S_t \cup \{k\} k_1, k_2)</tex> могут быть выполнены вовремя. Кроме того, все работы из <tex> \{ j \in S_t |-align="center" bgcolor=#FFFFFF| 0 || 0 || 0 || 0 || 0 || 0 || 5|-align="center" bgcolor=#FFFFFF| 0 || 0 || 1 || 0 || 0 || 0 || 0|-align="center" bgcolor=#FFFFFF| 0 || 0 || 2 || 0 || 0 || 0 || 0|-align="center" bgcolor=#FFFFFF| 0 || 1 || 0 || 0 || 0 || 0 || 0|-align="center" bgcolor=#FFFFFF| 0 || 1 || 1 || 0 || 0 || 0 || 0|-align="center" bgcolor=#FFFFFF| 0 || 1 || 2 || 0 || 0 || 0 || 0|-align="center" bgcolor=#FFFFFF| 0 || 2 || 0 || 0 || 0 || 0 || 0|-align="center" bgcolor=#FFFFFF| 0 || 2 || 1 || 0 || 0 || 0 || 0|-align="center" bgcolor=#FFFFFF| 0 || 2 || 2 || 0 || 0 || 0 || 0|-align="center" bgcolor=#FFFFFF| 1 || 0 || 0 || 0 || 5 || 11 || 7|-align="center" bgcolor=#FFFFFF| 1 || 0 || 1 || 0 || 5 || 11 || 7|-align="center" bgcolor=#FFFFFF| 1 || 0 || 2 || 0 || 5 || 0 || 0|-align="center" bgcolor=#FFFFFF| 1 || 1 || 0 || 0 || 5 || 11 || 7|-align="center" bgcolor=#FFFFFF| 1 || 1 || 1 || 0 || 0 || 5 || 7|-align="center" bgcolor=#FFFFFF| 1 || 1 || 2 || 0 || 0 || 0 || 0|-align="center" bgcolor=#FFFFFF| 1 || 2 || 0 || 0 || 5 || 0 || 0|-align="center" bgcolor=#FFFFFF| 1 || 2 || 1 || 0 || 0 || 0 || 0|-align="center" bgcolor=#FFFFFF| 1 || 2 || 2 || 0 || 0 || 0 || 0|-align="center" bgcolor=#FFFFFF| 2 || 0 || 0 || 0 || 5 || 0 || 0|-align="center" bgcolor=#FFFFFF| 2 || 0 || 1 || 0 || 5 || 0 || 0|-align="center" bgcolor=#FFFFFF| 2 || 0 || 2 || 0 || 5 || 0 || 0|-align="center" bgcolor=#FFFFFF| 2 || 1 || 0 || 0 || 5 || 0 || 0|-align="center" bgcolor=#FFFFFF| 2 || 1 || 1 || 0 || 5 || 0 || 0|-align="center" bgcolor=#FFFFFF| 2 || 1 || 2 || 0 || 5 || 0 || 0|-align="center" bgcolor=#FFFFFF| 2 || 2 || 0 || 0 || 5 || 0 || 0|-align="center" bgcolor=#FFFFFF| 2 || 2 || 1 || 0 || 5 || 0 || 0|-align="center" bgcolor=#FFFFFF| 2 || 2 || 2 || 0 || 5 || 0 || 0| j < k \} \cup \{k_{i_t}\} Действительно, в </tex> так же могут быть выполнены вовремяf_1 (0, что следует из построения <tex> S_t 0, 0)</tex>. Но тогда получается, что все работы и из множества записано <tex> S_t \cup \{k_{i_t}\} 5</tex> так же могут быть выполнены вовремя, что опять приводит нас к противоречию с построением <tex> S </tex>является минимальным значением целевой функции.}}

Время Для определения времени работы зависит от тогоалгоритма надо заметить, что <tex>i = 0, на сколько быстро мы будем добавлять\ldots , находить и удалять работы из множества n</tex>S, <tex> k = 0, \ldots , n</tex>. В качестве и <tex>Sk_j = 0, \ldots m</tex> можно использовать [[Двоичная куча | двоичную кучу]] или [[Красно-черное дерево | красно-черное дерево]] и тогда все нужные нам операции будут выполняться за где <tex>O(j = 1, \log n)ldots , m</tex>. Тогда время алгоритма будет Из рекуррентной формулы очевидно, что для подсчета одного значения <tex>O(n*f_{i} (k, k_{1}, \log n + T(Check))ldots , k_{m})</tex>. Так как нужно <tex>T(Check)=O(nmm)</tex>времени. Значит, то время алгоритма алгоритм работает за <tex>O(n^2*m^{m + 1})</tex>.

* [[Opij1di|<tex> O \mid p_{i,j} = 1, d_i \mid - </tex>]]* [[Opi1sumu|<tex>O \mid p_{iji, j} = 1 \mid \sum U_i</tex>]]* [[1pi1sumwu|<tex>1 \mid p_{i} = 1 \mid \sum w_{i}U_{i}</tex>]]