Изменения

Перейти к: навигация, поиск

Opij1SumTi

6866 байт добавлено, 23:04, 8 июня 2016
Асимптотика
=== Псевдокод ===
Определим ''вектор частот'' <tex>h([t)]</tex> {{---}} количество работ во временном интервале <tex>t</tex>. Работы отсортированы в порядке <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>.  '''function''' scheduler(): '''int''' <tex>h[m + n - 1]</tex> '''vector<int>''' <tex>s[n]</tex> '''fill'''(<tex>h,\ 0</tex>) '''fill'''(<tex>s,\ \varnothing</tex>) '''for''' <tex>i = 1</tex> '''to''' <tex>n</tex> '''if''' <tex>d_i < m + i - 1</tex> вычислим <tex>z</tex> {{---}} количество временных интервалов <tex>t = 1 \ldots d_i</tex>, таких, что <tex>h[t] < m</tex> '''if''' <tex>z \geqslant m</tex> <tex>T_i = d_i</tex> '''else''' <tex>T_i = d_i + m - z</tex> '''else''' <tex>T_i = m + i - 1</tex> вычислим <tex>m</tex> периодов <tex>1 \leqslant t_1 < t_2 < \ldots < t_m \leqslant T_i </tex> с минимальными значениями <tex>h[t_j]</tex> '''for''' <tex>j = 1</tex> '''to''' <tex>m</tex> <tex>s[i] = s[i] \cup \{t_j - 1\}</tex> <font color=green>// ставим работу <tex>i</tex> на время <tex>[t_j - 1, t_j]</tex></font> <tex>h[t_j] = h[t_j] + 1</tex> '''return''' <tex>s</tex>
'''for''' <tex>t = 1</tex> '''to''' <tex>m + n - 1</tex>
<tex>h(t) = 0</tex>
'''for''' <tex>i = 1</tex> '''to''' <tex>n</tex>
'''if''' <tex>d_i < m + i - 1</tex>
вычислим <tex>z</tex> {{---}} количество временных интервалов <tex>t = 1 \ldots d_i</tex>, таких, что <tex>h(t) < m</tex>
'''if''' <tex>z \geqslant m</tex>
<tex>T_i = d_i</tex>
'''else'''
<tex>T_i = d_i + m - z</tex>
'''else'''
<tex>T_i = m + i - 1</tex>
вычислим <tex>m</tex> периодов <tex>1 \leqslant t_1 < t_2 < \ldots < t_m \leqslant T_i </tex> с минимальными значениями <tex>h(t_j)</tex>
'''for''' <tex>j = 1</tex> '''to''' <tex>m</tex>
ставим работу <tex>i</tex> на время <tex>[t_j - 1, t_j]</tex>
<tex>h(t_j) = h(t_j) + 1</tex>
=== Асимптотика ===
Алгоритм может работать за <tex>O(nm)</tex>. Чтобы получить алгоритм с такой сложностью, мы распределяем работы так, чтобы после каждого шага <tex>i</tex> сохранялся инвариант <tex>l_1 \geqslant l_2 \geqslant \ldots \geqslant l_m </tex> при <tex>l_1 \geqslant T_i</tex>, где <tex>l_j</tex> такое, что на станке <tex>M_j</tex> все временные промежутки <tex>1 \ldots l_j</tex> заняты.
На первом шаге алгоритма <tex> l_1 = l_2 = \ldots = l_m = 0 </tex>. Предположим, что инвариант сохранился после шага <tex> i - 1 </tex>. Тогда <tex> T_{i-1} \leqslant T_i </tex> и, для сохранения инварианта, распределим работу в следующем порядке:<br>
<center><tex>l_1 + 1 \ldots T_i</tex> на станке <tex> M_1 </tex>,<br>
<tex>l_2 + 1 \ldots l_1</tex> на станке <tex> M_2 </tex>,<br>
<tex> \vdots </tex><br>
<tex>l_m + 1 \ldots l_{m-1}</tex> на станке <tex> M_1 </tex>.
</center>
Таким образом, мы получаем распределение одной работы по <tex>m</tex> станкам для <tex>n</tex> работ. Итоговая асимптотика {{---}} <tex>O(nm)</tex>.
== Доказательство корректности ==
{{Теорема
|statement=Алгоритм строит оптимальное расписание для задачи <tex> O \mid p_{i,j} = 1 \mid \sum T_{i} </tex>
|proof= Воспользуемся для доказательства леммой и теоремой из предыдущего пункта. Из них мы знаем, что существует оптимальное расписание, для которого выполняются свойства <tex>C_1 \leqslant C_2 \leqslant \ldots \leqslant C_n</tex> и <tex>C_i \leqslant m + i - 1</tex> для любого <tex>i = 1 \ldots n</tex>, где <tex>m</tex> {{---}} число станков. Пусть <tex>B</tex> {{---}} оптимальное расписание, которое удовлетворяет свойству, по которому работы <tex>1 \ldots k - 1 </tex> поставлены в те же временные промежутки, в которых они оказались следуя нашему расписанию <tex>A</tex>. Более того, предположим, что <tex>B</tex> было выбрано так, что <tex>k</tex> максимально.
Пусть <tex>C_k > T_k</tex>. С того момента, как работа <tex>k</tex> поставлена в расписании <tex>A</tex> перед <tex>T_k</tex>, определим временной промежуток <tex>t \leqslant T_k </tex> в месте, где работа <tex>k</tex> не выполняется в <tex>B</tex>. Тогда в самом расписании <tex>B</tex> этот промежуток либо так же пустой, либо он занят работой <tex>r > k</tex>.
* Если он пустой, мы перемещаем операцию <tex>k</tex>, которая была распределена в промежуток <tex>C_k</tex>, в этот промежуток.
* Если работа <tex>r</tex> стоит во время <tex>t</tex>, но не во время <tex>C_k</tex>, то мы меняем между собой операции работ <tex>k</tex> и <tex>r</tex>.
* Если работа <tex>r</tex> поставлена во время <tex>t</tex> и <tex>C_k</tex>, то либо тут есть пустое место в <tex>C_r + 1</tex>, либо там должна быть работа, назовем ее <tex>v</tex>, которая поставлена на время <tex>C_r + 1</tex>, но не поставлена в <tex>C_k</tex>.
Работа <tex>v</tex> точно там есть, потому что <tex>r</tex> и <tex>k</tex> поставлены на время <tex>C_k</tex>, но не поставлены на время <tex>C_r + 1</tex>. Если свободный промежуток есть, тогда переставим работу <tex>r</tex> со времени <tex>t</tex> на время <tex>C_r + 1</tex> и работу <tex>k</tex> со времени <tex>C_k</tex> на <tex>t</tex>. Иначе мы можем переместить работу <tex>r</tex> с времени <tex>t</tex> на время <tex>C_r + 1</tex>, <tex>k</tex> c <tex>C_k</tex> на <tex>t</tex>, и <tex>v</tex> с <tex>C_r + 1</tex> на <tex>C_k</tex>. Тогда <tex>C_k</tex> должно уменьшиться как минимум на один, а <tex>C_r</tex> увеличится не больше, чем на один.
Если мы продолжим так действовать, мы получим оптимальное расписание <tex>B'</tex> с <tex>C_k \leqslant T_k</tex>, в котором работы <tex>1 \ldots k-1</tex> расположены так же, как в расписании <tex>A</tex>.
Пусть <tex>h</tex> {{---}} вектор частот для части расписания из работ от <tex>1</tex> до <tex>k - 1</tex>. Предположим, что <tex>h(t') < h(t)</tex> и работа <tex>k</tex> выполняется во временной промежуток <tex>t</tex>, но не выполняется в <tex>t'</tex> в расписании <tex>B'</tex>. Если в <tex>B'</tex> станок простаивает во время <tex>t'</tex>, мы можем переместить работу <tex>k</tex> из <tex>t</tex> в <tex>t'</tex>. Иначе работа <tex>r > k</tex> находится в расписании в промежутке <tex>t'</tex>, но ее нет в <tex>t</tex>. Мы можем передвинуть <tex>r</tex> в <tex>t</tex> и <tex>k</tex> в <tex>t'</tex> без увеличения целевой функции, потому что <tex>C_k \leqslant C_r</tex>. Продолжая действовать таким образом, мы достигнем оптимального расписания, в котором работы <tex>1 \ldots k</tex> расположены таким же образом, как и в <tex>A</tex>. Мы получили противоречие, так как выбранный <tex>k</tex> оказался не максимальным.
}}
== См. также ==
577
правок

Навигация