Изменения
*Новый конспект*
<tex dpi = "200" >1 \mid\mid \sum w_i T_i</tex>
{{Определение
|definition =
'''Опоздание''' (англ. ''Tardiness'', ''<tex>T_{j}</tex>'') <tex>T_j = \max\{0, C_j - d_j\}</tex>}}
{{Задача
|definition= Есть один станок и <tex>n</tex> работ. Для каждой работы заданы время выполнения <tex> p_i,</tex> дедлайн <tex>d_i</tex> и стоимость выполнения этой работы <tex>w_i \geqslant 0</tex>.
Необходимо минимизировать <tex>\sum w_i T_i</tex>.
}}
==Псевдополиномиальное решение==
===Описание алгоритма===
Будем делить имеющиеся у нас работы на множества <tex> I_1, I_2</tex> так, чтобы для любого <tex>j \geqslant k</tex> работы из <tex>I_1 = \{1,..., j\}\setminus\{k\}</tex> были расположены до <tex>k</tex>, а работы из <tex>I_2 = \{j+1,..., n\}</tex> были расположены после <tex>k</tex>. Оптимальное время начала выполнения всех работ из <tex> I_1 \enskip t_1 = 0</tex>, из <tex> I_2 \enskip t_2 = p = \sum\limits_{i=1}^j p_i</tex>. <br>
Алгоритм вычисляет оптимальное расписание для всех работ рекурсивно.
===Псевдокод===
Приведенный ниже алгоритм вычисляет оптимальную последовательность работ <tex>\pi</tex>для множества работ <tex>I = \{i_1, i_2, ..., i_r\}</tex> в начальный момент времени <tex>t</tex>.
'''function''' <tex> \mathrm{Sequence}(t, I)</tex>:
'''if''' <tex>I = \varnothing</tex>
<tex>\pi = \varnothing</tex>
'''else'''
find <tex>i_k : p_{i_k} = \max\{p_i \mid i \in I\}</tex>
<tex>f^* = \inf</tex>
'''for''' <tex>j = k</tex> '''to''' <tex>r</tex>
<tex>I_1 := \{i_v \mid 1 \leqslant v \leqslant j; v \ne k\};</tex>
<tex>t_1 := t; </tex>
<tex>\pi_1 := \mathrm{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}(t_2 , I_2 );</tex>
<tex>\pi:=\pi_1 \circ i_k \circ \pi2;</tex>
вычисляем значение <tex>f(\pi, t)</tex>
'''if''' <tex>f(\pi, t) < f^*</tex>
<tex>\pi^* := \pi; </tex>
<tex>f^* := f(\pi, t)</tex>
'''return''' <tex>\pi^*</tex>
===Доказательство корректности алгоритма===
{{Лемма
|statement=
Пусть <tex> \pi </tex> - любая оптимальная последовательность работ для данных дедлайнов <tex>d_1, d_2, ... , d_n</tex>, <tex>C_j</tex> - время завершения выполнения <tex>j</tex>-ой работы.
Рассмотрим <tex>d'_j</tex> такие, что <tex>\min\{d_j, C_j\} \leqslant d'_j \leqslant \max\{d_j, C_j\}. </tex>Тогда любая оптимальная последовательность работ для <tex> d_j</tex> будет оптимальна и для <tex>d'_j</tex>
|proof=
<tex>T( \pi) = T′(\pi) + \sum\limits_{i=1}^n A_j</tex>, <br>
<tex>T( \pi′) = T ′(\pi′) + <tex> \sum\limits_{i=1}^n B_j</tex>, <br>
где, если <tex>C_j</tex> <tex>\leqslant</tex> <tex>d_j</tex>, то <br>
<tex>A_j = 0</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>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>
Если <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>
}}
{{Лемма
|statement=
Пусть веса работ согласованы (из <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>.
|proof=
Пусть <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>i</tex> следует за работой <tex>j</tex>, где <tex> d_i \leqslant d_j </tex> и <tex>i, j</tex> выполнены до дедлайна, тогда, после перемещения <tex>j</tex> на позицию сразу после <tex>i</tex>, работа <tex>j</tex> все еще будет выполнена до дедлайна. Таким образом, общее значение минимизируемой функции не возрастет.
Будем повторять перестановки, пока оптимальное расписание не будет удовлетворять условиям леммы.
}}
{{Теорема
|statement= Пусть работы <tex>j_1, j_2, ..., j_n</tex> отстортированы в порядке неубывания дедлайнов, и веса согласованы. Обозначим за <tex>k</tex> работу с наибольшим <tex>p_i</tex>.
Тогда существует работа <tex>j^* \geqslant k</tex> такая, что в оптимальном расписании все работы <tex>v = 1, ..., j^*, v \ne k</tex> размещены до <tex>k</tex>, а оставшиеся работы размещены после <tex>k</tex>.
|proof=
Обозначим за <tex>C'_k</tex> максимально возможное время завершения работы <tex>k</tex> в любой последовательности, которая оптимальна в соответствии с <tex>d_1, d_2, ..., d_n</tex>. Обозначим за <tex>\pi</tex> оптимальную последовательность, соответствующую <tex>d_1, d_2, ..., d_k-1, d'_k = \max\{C'_k, d_k\}, d_k+1, ..., d_n</tex> и удовлетворяющую условиям Леммы 2. Обозначим за <tex>C_k</tex> время завершения работы <tex>k</tex> из <tex>\pi</tex>. <br>
Согласно Лемме 1, последовательность <tex>\pi</tex> оптимальна для исходных <tex>d_1, d_2, ..., d_n</tex>. Тогда по определению <tex>C'_k</tex>: <tex>C_k \leqslant C'_k \leqslant \max\{C'_k, d_k\} = 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 = \max\{C'_k, d_k\}</tex>, тогда <tex>j ^* \geqslant k</tex>, так как <tex>d_j ^* \leqslant d'_k</tex> и <tex>j^*</tex> обладает необходимыми свойствами.
}}
===Время работы===
Пускай все времена выполнения работ различны. Тогда все множества работ, используемые в качестве аргументов рекурсивного вызова функции можно представить в виде <tex>i, j, k := \{ v \mid i \leqslant v \leqslant j; 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}(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,..., n,</tex> <tex>i</tex> < <tex>j</tex> могут быть сосчитаны за <tex>\mathcal{O}(n^2)</tex>. <br>
Таким образом, мы получаем алгоритм, работающий за <tex>\mathcal{O}(n^3p)</tex> или <tex>\mathcal{O}(n^4p_{max})</tex>, где <tex>p_{max} = \max\limits_{i=1}^n p_i</tex>.
==См. также ==
* [[Классификация задач]]
* [[1sumwu|<tex>1 \mid\mid \sum w_i U_i</tex>]]
== Источники информации ==
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 95 - 98
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]
{{Определение
|definition =
'''Опоздание''' (англ. ''Tardiness'', ''<tex>T_{j}</tex>'') <tex>T_j = \max\{0, C_j - d_j\}</tex>}}
{{Задача
|definition= Есть один станок и <tex>n</tex> работ. Для каждой работы заданы время выполнения <tex> p_i,</tex> дедлайн <tex>d_i</tex> и стоимость выполнения этой работы <tex>w_i \geqslant 0</tex>.
Необходимо минимизировать <tex>\sum w_i T_i</tex>.
}}
==Псевдополиномиальное решение==
===Описание алгоритма===
Будем делить имеющиеся у нас работы на множества <tex> I_1, I_2</tex> так, чтобы для любого <tex>j \geqslant k</tex> работы из <tex>I_1 = \{1,..., j\}\setminus\{k\}</tex> были расположены до <tex>k</tex>, а работы из <tex>I_2 = \{j+1,..., n\}</tex> были расположены после <tex>k</tex>. Оптимальное время начала выполнения всех работ из <tex> I_1 \enskip t_1 = 0</tex>, из <tex> I_2 \enskip t_2 = p = \sum\limits_{i=1}^j p_i</tex>. <br>
Алгоритм вычисляет оптимальное расписание для всех работ рекурсивно.
===Псевдокод===
Приведенный ниже алгоритм вычисляет оптимальную последовательность работ <tex>\pi</tex>для множества работ <tex>I = \{i_1, i_2, ..., i_r\}</tex> в начальный момент времени <tex>t</tex>.
'''function''' <tex> \mathrm{Sequence}(t, I)</tex>:
'''if''' <tex>I = \varnothing</tex>
<tex>\pi = \varnothing</tex>
'''else'''
find <tex>i_k : p_{i_k} = \max\{p_i \mid i \in I\}</tex>
<tex>f^* = \inf</tex>
'''for''' <tex>j = k</tex> '''to''' <tex>r</tex>
<tex>I_1 := \{i_v \mid 1 \leqslant v \leqslant j; v \ne k\};</tex>
<tex>t_1 := t; </tex>
<tex>\pi_1 := \mathrm{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}(t_2 , I_2 );</tex>
<tex>\pi:=\pi_1 \circ i_k \circ \pi2;</tex>
вычисляем значение <tex>f(\pi, t)</tex>
'''if''' <tex>f(\pi, t) < f^*</tex>
<tex>\pi^* := \pi; </tex>
<tex>f^* := f(\pi, t)</tex>
'''return''' <tex>\pi^*</tex>
===Доказательство корректности алгоритма===
{{Лемма
|statement=
Пусть <tex> \pi </tex> - любая оптимальная последовательность работ для данных дедлайнов <tex>d_1, d_2, ... , d_n</tex>, <tex>C_j</tex> - время завершения выполнения <tex>j</tex>-ой работы.
Рассмотрим <tex>d'_j</tex> такие, что <tex>\min\{d_j, C_j\} \leqslant d'_j \leqslant \max\{d_j, C_j\}. </tex>Тогда любая оптимальная последовательность работ для <tex> d_j</tex> будет оптимальна и для <tex>d'_j</tex>
|proof=
<tex>T( \pi) = T′(\pi) + \sum\limits_{i=1}^n A_j</tex>, <br>
<tex>T( \pi′) = T ′(\pi′) + <tex> \sum\limits_{i=1}^n B_j</tex>, <br>
где, если <tex>C_j</tex> <tex>\leqslant</tex> <tex>d_j</tex>, то <br>
<tex>A_j = 0</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>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>
Если <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>
}}
{{Лемма
|statement=
Пусть веса работ согласованы (из <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>.
|proof=
Пусть <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>i</tex> следует за работой <tex>j</tex>, где <tex> d_i \leqslant d_j </tex> и <tex>i, j</tex> выполнены до дедлайна, тогда, после перемещения <tex>j</tex> на позицию сразу после <tex>i</tex>, работа <tex>j</tex> все еще будет выполнена до дедлайна. Таким образом, общее значение минимизируемой функции не возрастет.
Будем повторять перестановки, пока оптимальное расписание не будет удовлетворять условиям леммы.
}}
{{Теорема
|statement= Пусть работы <tex>j_1, j_2, ..., j_n</tex> отстортированы в порядке неубывания дедлайнов, и веса согласованы. Обозначим за <tex>k</tex> работу с наибольшим <tex>p_i</tex>.
Тогда существует работа <tex>j^* \geqslant k</tex> такая, что в оптимальном расписании все работы <tex>v = 1, ..., j^*, v \ne k</tex> размещены до <tex>k</tex>, а оставшиеся работы размещены после <tex>k</tex>.
|proof=
Обозначим за <tex>C'_k</tex> максимально возможное время завершения работы <tex>k</tex> в любой последовательности, которая оптимальна в соответствии с <tex>d_1, d_2, ..., d_n</tex>. Обозначим за <tex>\pi</tex> оптимальную последовательность, соответствующую <tex>d_1, d_2, ..., d_k-1, d'_k = \max\{C'_k, d_k\}, d_k+1, ..., d_n</tex> и удовлетворяющую условиям Леммы 2. Обозначим за <tex>C_k</tex> время завершения работы <tex>k</tex> из <tex>\pi</tex>. <br>
Согласно Лемме 1, последовательность <tex>\pi</tex> оптимальна для исходных <tex>d_1, d_2, ..., d_n</tex>. Тогда по определению <tex>C'_k</tex>: <tex>C_k \leqslant C'_k \leqslant \max\{C'_k, d_k\} = 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 = \max\{C'_k, d_k\}</tex>, тогда <tex>j ^* \geqslant k</tex>, так как <tex>d_j ^* \leqslant d'_k</tex> и <tex>j^*</tex> обладает необходимыми свойствами.
}}
===Время работы===
Пускай все времена выполнения работ различны. Тогда все множества работ, используемые в качестве аргументов рекурсивного вызова функции можно представить в виде <tex>i, j, k := \{ v \mid i \leqslant v \leqslant j; 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}(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,..., n,</tex> <tex>i</tex> < <tex>j</tex> могут быть сосчитаны за <tex>\mathcal{O}(n^2)</tex>. <br>
Таким образом, мы получаем алгоритм, работающий за <tex>\mathcal{O}(n^3p)</tex> или <tex>\mathcal{O}(n^4p_{max})</tex>, где <tex>p_{max} = \max\limits_{i=1}^n p_i</tex>.
==См. также ==
* [[Классификация задач]]
* [[1sumwu|<tex>1 \mid\mid \sum w_i U_i</tex>]]
== Источники информации ==
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 95 - 98
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]
