577
правок
Изменения
→Асимптотика
=== Асимптотика ===
Алгоритм может работать за <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_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> оказался не максимальным.
