129
правок
Изменения
м
грамотность
<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>
|proof=
[[Файл:f2cmax_first_fixed.png|400px|thumb|right|Рис. 1]]
Предположим обратное, что не существует оптимального расписания с одиннаковыми одинаковыми перестановками работ на станках. Рассмотрим некоторое оптимальное расписание с максимальным по длине общим префиксом на станках.
Пусть его длина равна <tex> k </tex>, где <tex> k < n </tex>. Пусть на <tex> k </tex> позиции на первом и втором станках стоит работа <tex> i </tex>, а на втором станке на позиции <tex> k + 1 </tex> стоит работа <tex> j </tex>. Тогда заметим, что если мы поставим работу <tex> j </tex> на первом станке сразу после работы <tex> i </tex>, то последовательные работы с <tex> h </tex> по <tex> m </tex> (см. Рис. 1) по-прежнему будут успевать выполниться, так как на втором станке они выполняются в текущем расписании после <tex> j </tex>. Таким образом нам удалось увеличить длину наибольшего общего префикса, а так как по нашему предположению она была максимальна, то наше предположение неверно, то искомое расписание с одиннаковым одинаковым порядком выполнения работ на обоих станках существует.
}}
Таким образом задача сводится к поиску этой искомой перестановки. Докажем, что полученный нашим алгоритмом список является отпимальной оптимальной перестановкой работ.
{{лемма
==Сложность алгоритма==
Заметим, что на каждом шаге алгоритма мы выбираем минимум из оставшихся элементов за <tex>O(\log n)</tex> (либо предварительной сортировкой, либо любой структурой данных, поддеживающей поддерживающей нахождение минимума и удаление за <tex>O(\log n)</tex>). И делаем мы это <tex> n </tex> раз, следовательно алгоритм работает за <tex>O(n\log n)</tex>.
==Источники==
