F2Cmax

2013-06-11T09:58:59Z

94.25.229.60: /* Доказательство корректности алгоритма */

<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;">Эта статья находится в разработке!</div>
<includeonly>[[Категория: В разработке]]</includeonly>

== Постановка задачи ==
Рассмотрим задачу:
<ol>
<li>Дано <tex>n</tex> работ и <tex>2</tex> станка.</li>
<li>Для каждой работы известно её время выполнения на каждом станке.</li>
<li>Каждую работу необходимо выполнить сначала на первом станке, а потом на втором.</li>
</ol>
Требуется минимизировать время окончания всех работ.

== Описание алгоритма ==
Пусть <tex>p_{i1}</tex> {{---}} время выполнения <tex>i</tex>-ой работы на первом станке, а <tex>p_{i2}</tex> {{---}} на втором.<br/>
<ol>
<li>Будем в ходе нашего алгоритма строить два списка <tex> L </tex> и <tex> R </tex>. Изначально оба списка пусты. И будем поддерживать множество еще не распределенных по спискам <tex> L </tex> и <tex> R </tex> работ <tex>X = \{i \mid i = 1, \dots, n\}</tex> </li>
<li> Пока множество <tex> X </tex> непусто будем распределять работы по спискам следующим образом:
<ul>
<li> Находим такие индексы <tex> i </tex> и <tex> j </tex>, что <tex>p_{ij} = \min \{ p_{ij} \mid i \in X; j = 1, 2\}</tex> </li>
<li>Если минимум достигается на первом станке (иными словами <tex> j = 1 </tex>), то поставим работу <tex> i </tex> в конец листа <tex> L </tex>, иначе ставим в начало листа <tex> R </tex> </li>
<li>Удаляем работу <tex> i </tex> из множества <tex> X </tex> </li>
</ul>
</li>
<li> Рассмотрим лист <tex> T = L \circ R</tex>. Утверждается, что этот лист является оптимальной перестановкой работ как на первом, так и на втором станке. Далее расставляем подряд работы на первом станке согласно перестановке, после чего ставим в том же порядке работы на втором стане, при этом избегая одновременного выполнения одной и той же работы. </li>

</ol>

==Доказательство корректности алгоритма==
TODO Доказательство равенства перестановок на первом и втором станках

Докажем, что полученный нашим алгоритмом лист является отпимальной перестановкой работ.
{{Лемма
|id=lemma1
|about=1
|statement= Если для каких работ <tex> i </tex> и <tex> j </tex> из листа <tex> T </tex> верно неравенство <tex> \min(p_{i1}, p_{j2}) < \min(p_{j1}, p_{i2}) </tex>, то работа <tex> i </tex> встречается в листе <tex> T </tex> раньше, чем <tex> j </tex>
|proof=
Пусть <tex> p_{i1} < p_{j2} </tex>. Случай <tex> p_{i1} > p_{j2} </tex> рассматривается аналогично.

То есть имеем, что <tex> p_{i1} < \min(p_{j1}, p_{i2}) </tex>. Так как <tex> p_{i1} < \min(p_{j1}, p_{i2}) \leq p_{i2} </tex>, то работа <tex> i \in L </tex>. Работа <tex> j </tex> либо стоит в <tex> R </tex>, либо она стоит в <tex> L </tex> и при этом <tex> p_{i1} < p_{j1} </tex>. Заметим, что в обоих случаях она расположена позже (в силу нашего построения), чем работа <tex> i </tex>, то лемма доказана.

}}

{{Лемма
|id=lemma2
|about=2
|statement= Пусть имеет случайное расписание, в котором работа <tex> j </tex> идет сразу же после работы <tex> i </tex>. Тогда если <tex> \min(p_{j1}, p_{i2}) \leq \min(p_{i1}, p_{j2}) </tex>, то можем поменять местами эти работы без ухудшение целевой функций.
|proof=
Пусть <tex> w_{ij} </tex> {{---}} время, прошедшее с начала выполнения работы <tex> i </tex> на первом станке до окончания работы <tex> j </tex> на втором станке.

...

Таким образом, <tex> w_{ij} = \max (p_{i1} + p_{j1} + p_{j2}, p_{i1} + p_{i2} + p_{j2}, delta + p_{i2} + p_{j2}) </tex>. Иначе говоря <tex> w_{ij} = \max (p_{i1} + \max(p_{j1}, p_{i2}) + p_{j2}, delta + p_{i2} + p_{j2}) </tex>.

Аналогично имеем, что <tex> w_{ji} = \max (p_{j1} + \max(p_{i1}, p_{j2}) + p_{i2}, delta + p_{i2} + p_{j2}) </tex>

Так как <tex> \min(a, b) = - \max(-a, -b)</tex>, то из условию леммы имеем <tex> \max(-p_{i1}, -p_{j2}) \leq \max(-p_{j1}, -p_{i2}) </tex>, то добавим <tex> p_{i1} + p_{i2} + p_{j1} + p_{j2} </tex> к обеим частям. То получим, что <tex> p_{j1} + \max(p_{i1}, p_{j2}) + p_{i2} \leq p_{i1} + \max(p_{j1}, p_{i2}) + p_{j2} </tex>, то есть <tex> w_{ji} \leq w_{ij} </tex>, то при смене местами работ <tex> i </tex> и <tex> j </tex> ответ не ухудшается.

}}

{{
Теорема|statement=
Построенная перестановка <tex> T </tex> является оптимальной.

|proof=
Рассмотрим случайную перестановку <tex> S </tex>. Пусть перестановки <tex> T </tex> и <tex> S </tex> имеют общий префикс длины <tex> l-1 </tex>. Пусть <tex> i = T_{l} </tex> и <tex> j = S_{l} </tex>. Рассмотрим множество работ <tex>M = \{T_{r} \mid r = l, \dots, n\}</tex>. Заметим, что для любой работы <tex> k \in M </tex> верно, что <tex> \min(p_{k1}, p_{i2}) \geq \min(p_{i1}, p_{k2}) </tex>, так как если было бы верно обратное, то есть <tex> \min(p_{k1}, p_{i2}) < \min(p_{i1}, p_{k2}) </tex>, то по Лемме 1 было бы верно, что <tex> k </tex> идет раньше <tex> i </tex>, что неверно.

Очевидно, что в перестановке <tex> S </tex> работа <tex> i </tex> будет стоять после <tex> j </tex> (иначе общий префикс был бы короче), то заметим, что в этой перестановке для работы <tex> i </tex> и для предыдущей работы <tex> w </tex> верно <tex> \min(p_{w1}, p_{i2}) \geq \min(p_{i1}, p_{w2}) </tex> (так как <tex> w \in M </tex>), то по Лемме 2 можем поменять местами работы <tex> i </tex> и <tex> w </tex> без ухудшения ответа. То такими операциями сможем дойти до пары работ <tex> i </tex> и <tex> j </tex>, которые при смене увеличат общий префикс перестановок <tex> S </tex> и <tex> T </tex>.

Таким образом любая перестановка сводится к нашей без ухудшения ответа такими операциями, что подтверждает оптимальность перестановки <tex> T </tex>

}}

==Псевдокод==
<tex>L \leftarrow \varnothing </tex>
<tex>R \leftarrow \varnothing </tex>
<tex>X \leftarrow \{1, \dots, n\}</tex>
while <tex> X \neq \varnothing</tex>
Найти <tex> i </tex> и <tex> j </tex>, где <tex>p_{ij} = \min \{ p_{ij} \mid i \in X; j = 1, 2\}</tex>
if j = 1
<tex>L \leftarrow L \circ i </tex>
else
<tex>R \leftarrow i \circ R </tex>
<tex>X \leftarrow X \setminus \{i\} </tex>
<tex>T \leftarrow L \circ R</tex>

Расставляем работы на первом станке согласно перестановке <tex> T </tex>

Расставляем работы на втором станке согласно перестановке <tex> T </tex>
и времени начала соответсвующей работы на первом станке.

==Сложность алгоритма==
Заметим, что на каждом шаге алгоритма мы выбираем минимум из оставшихся элементов за <tex>O(\log n)</tex> (либо предварительной сортировкой, либо любой структурой данных, поддеживающей нахождение минимума и удаление за <tex>O(\log n)</tex>). И делаем мы это <tex> n </tex> раз, следовательно алгоритм работает за <tex>O(n\log n)</tex>.

==Источники==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 175 стр. {{---}} ISBN 978-3-540-69515-8

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]

Викиконспекты - Вклад участника [ru]

F2Cmax