Изменения

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

Обсуждение участницы:Анна

14 574 байта убрано, 14:25, 12 декабря 2016
Нет описания правки
{{Определение|definition = Определим <tex>half(L)</tex> как множество первых половин цепочек языка <tex>L</tex>, то есть множество <tex>\{ w \mid </tex dpi > существует <tex>x</tex>, для которой <tex>wx \in L</tex>, причем <tex>|w| = "200"|x| \}</tex>. }}Например, если <tex> O L = \mid p_{i\varepsilon,j0010, 011, 010110 \} </tex>, то <tex>half(L) = 1 \mid { \varepsilon, 00, 010 \sum T_{i} </tex>. Заметим, что цепочки нечетной длины не влияют на <tex>half(L)</tex>.{{ЗадачаОпределение|definition=Дано Определим <tex>mcycle(L)</tex> одинаковых станков, которые работают параллельно, и как множество <tex>\{ w \mid </tex> цепочку <tex>nw</tex> работ, которые необходимо выполнить можно представить в произвольном порядке на всех станках. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть время окончания виде <tex>d_iw = xy</tex> {{---, где <tex>yx \in L \}} время, до которого она должна быть выполнена. Необходимо минимизировать суммарную [[Классификация_задач#Критерий оптимизации|медлительность]]</tex>.}} Например, если <tex>L == Описание алгоритма ===== Идея ===Будем полагать\{ 01, что работы заданы в порядке неубывания их дедлайнов011 \}</tex>, то есть <tex>d_1 cycle(L) = \leqslant d_2 { 01, 10, 011, 110, 101 \leqslant \ldots \leqslant d_n}</tex>.  {{ЛеммаУтверждение|id = st3|statement=Пусть есть работы <tex>1 \ldots nL</tex> с дедлайнами {{---}} регулярный язык. Тогда язык <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_nhalf(L)</tex>также регулярен. Тогда существует оптимальное расписание, в котором времена завершения работ идут в том же порядке|proof =Так как <tex>L</tex> {{---}} регулярный язык, то есть существует допускающий его ДКА и порождающее его регулярное выражение. Оба эти факта могут быть использованы для доказательства утверждения. Мы выберем первый.<br>Пусть <tex>C_1 M = \leqslant C_2 langle \leqslant Sigma , Q , q_0 , F , \ldots delta \leqslant C_nrangle </tex> {{---}} ДКА, допускающий язык <tex>L</tex>.|proof=Рассмотрим две работы строку <tex>ix</tex> и . Для того, чтобы проверить, что <tex>jx \in half(L)</tex> из какого-либо оптимального расписания такие, нам надо убедиться, что существует строка <tex>C_i > C_jy</tex> такой же длины, что и <tex>d_i x</tex>, которая, будучи сконкатенированной с < d_jtex>x</tex>, даст строку из <tex>L</tex>. Поменяем эти работы в расписании местами, то есть если на вход автомату подать <tex>C'_i = C_jxy</tex>, то в конце обработки мы окажемся в терминальном состоянии. Предположим, что автомат, закончив обработку <tex>x</tex> и , находится в состоянии <tex>C'_j = C_iq_i</tex>. Если они обе успевали выполниться вовремя, то это свойство сохранитсяесть <tex>\delta(q_0, так как x) = q_i</tex>d_i . Мы должны проверить, что существует строка < d_jtex>y, |y| = |x|,</tex>, значит по-прежнему которая ведет из состояния <tex>T_i = 0q_i</tex> и до какого-нибудь терминального состояния <tex>T_j = 0M</tex>, то есть значение целевой функции мы не ухудшили и расписание осталось оптимальным<tex>\delta(q_i, y) \in F</tex>. Если обе работы не успевали выполниться вовремяПредположим, то когда что мы поменяем их местами ничего не изменитсяпрошли <tex>n</tex> вершин автомата, то есть значение целевой функции останется прежним<tex>|x| = n</tex>. Обозначим за <tex>S_n</tex> множество всех состояний, так как мы не меняли значения времен окончаний, а только поменяли их местамис которых можно попасть в терминальные за <tex>n</tex> шагов. Тогда <tex>q_i \in S_n \Leftrightarrow x \in half(L)</tex>. Если работа мы сможем отслеживать <tex>jS_n</tex> успевала выполниться, а и <tex>iq_i</tex> {{---}} нет, то мы снова не ухудшим значение целевой функции. Покажем это. До тогосможем определять, как мы поменяли работы местамиверно ли, было что <tex>T_i + T_j = C_i - d_ix \in half(L)</tex>. Заметим, так как что <tex>T_j = 0S_0 \equiv F</tex>. После того, как Очевидно мы поменяли работы местами, можем построить <tex>T_i S_{n+ T_j = C'_i - d_i + C'_j - d_j = C_j - d_i + C_i - d_j = C_i - d_i + (C_j - d_j)1}</tex> зная <tex>S_n</tex>. Но так как работа и <tex>j\delta</tex> успевает выполниться до дедлайна: <tex>S_{n+1} = \{ q_j \mid \delta(q_j, q_k) \in Q, то q_k \in S_n \}</tex>C_j {{- d_j \leqslant 0--}} множество состояний, из которых есть переход в какое-либо состояние из <tex>S_n</tex>(по единственному символу).
}}
Далее будем рассматривать только оптимальное расписание со свойством <tex>C_1 \leqslant C_2 \leqslant \ldots \leqslant C_n</tex>.
{{Теорема
|statement=
Всегда существует оптимально расписание такое, что в нем <tex>C_i \leqslant m + i - 1</tex> для любого <tex>i = 1 \ldots n</tex>, где <tex>m</tex> {{---}} количество станков.
|proof=
Рассмотрим оптимальное расписание <tex>S^*</tex>, в котором для любого <tex>i = 1 \ldots k - 1</tex> выполняется <tex>C_i \leqslant m + i - 1</tex>, но <tex>C_k > m + k - 1</tex>, где <tex>k</tex> максимально среди всех возможных. Для начала покажем, что <tex>k</tex> не меньше <tex>2</tex>. Пусть есть оптимальное расписание, у которого <tex>C_1 > m</tex>. Это значит, что есть период времени <tex>t</tex> такой, что первая работа выполняется в момент <tex>t</tex> и не выполняется в <tex>t - 1</tex>. Поменяем эти периоды времени местами. То есть все работы, которые выполнялись в момент <tex>t - 1</tex>, будут выполняться на тех же станках, но в момент <tex>t</tex>, и наоборот. Значение <tex>C_i</tex> для каждой работы <tex>i</tex> не увеличится, так как <tex>C_1</tex> было минимальным из них, а значит ни одна работа не могла быть закончена раньше периода времени <tex>t</tex>. Будем продолжать этот процесс, пока не будет выполнено равенство <tex>C_1 = m</tex>.<br>
Теперь пусть <tex>C_k = m + k + t</tex>, где <tex>t \geqslant 0</tex>. Будем называть ''итерацией обработки'' работы обработку на одной машине. Разобьем все работы на три множества:
* множество <tex>A</tex> будет содержать все итерации обработки работ <tex>i = 1 \ldots k - 1</tex>
* множество <tex>B</tex> {{---}} все итерации, запланированные в расписании <tex>S^*</tex> строго после момента времени <tex>k + m + t</tex>
* множество <tex>C</tex> {{---}} итерации обработки работ <tex>i = k + 1 \ldots n</tex>, которые в <tex>S^*</tex> запланированы на время <tex>k + m + t</tex> и раньше
Таким образом, мы имеем три непересекающихся множества, которые вместе с работой <tex>k</tex> покрывают все итерации всех работ.<br>
Построим новое расписание <tex>S^*</tex>. Для начала расставим все работы из множества <tex>A \cup B</tex> так же, как они были запланированы в расписании <tex>S^*</tex>. Так как <tex>C_i \leqslant m + i - 1</tex> для <tex>i = 1 \ldots k - 1</tex>, ни одна итерация обработки в множестве <tex>B</tex> не поставлена раньше момента времени <tex>k + m + t</tex> и к моменту времени <tex>C_k = m + k + t</tex> выполнено <tex>k</tex> работ, то это значит, что между моментами времени <tex>1</tex> и <tex>k + m - 1</tex> на каждой машине есть <tex>m</tex> различных простоев, то есть моментов, когда на ней ничего не обрабатывается. Значит, мы всегда сможем поставить на эти простои итерации обработки работы <tex>k</tex>, даже если эти простои пересекаются. Таким образом, <tex>C_k \leqslant m + k - 1</tex>.<br>
Теперь назначим машины для операций из множества <tex>C</tex>. До момента времени <tex>k + m + t</tex> сейчас распланировано ровно <tex>k</tex> работ, так как по определению работы из множества <tex>B</tex> запланированы на время строго большее <tex>k + m + t</tex>. Значит, между моментами времени <tex>1</tex> и <tex>k + m + t</tex> есть <tex>k + m + t - k = m + t</tex> различных простоев на каждой машине. Исходя из определения множества <tex>C</tex> и того, что к моменту <tex>k + m + t</tex> распланировано <tex>km</tex> итераций обработок, приходим к неравенству <tex>|C| \leqslant (k + m + t)m - km = (m + t)m</tex>. Значит, мы можем распланировать итерации из множества <tex>C</tex> не позднее момента <tex>k + m + t</tex>. Таим образом, мы снова построили расписание для задачи open shop, которое так же является оптимальным, так как для множеств <tex>A</tex> и <tex>B</tex> все осталось как в оптимальном расписании <tex>S^*</tex>, работу <tex>k</tex> мы научились выполнять быстрее, а для множества <tex>C</tex> ответ был не ухудшен. Любая работа <tex>j</tex>, итерации обработки которой принадлежат множеству <tex>C</tex>, имела время окончания <tex>C_j \geqslant m + k + t</tex>. Однако это противоречит тому, что мы выбрали максимальное <tex>k</tex>.
}}
Отсортируем работы в порядке неуменьшения дедлайнов. Для текущей работы <tex>i</tex> вычислим ''лимит'' <tex>T_i</tex> {{---}} время, до которого закончится обработка данной работы, то есть <tex>1 \leqslant t_1 < t_2 < \ldots < t_m \leqslant T_i </tex>, где <tex>t_j</tex>, <tex>j = 1 \ldots m</tex> {{---}} периоды обработки работы <tex>i</tex>.
Будем выбирать эти периоды среди моментов времени, в которые выполняется наименьшее число работ.
{{Утверждение|id === Псевдокод ==st4|statement =Определим ''вектор частот'' Пусть <tex>h(t)L</tex> {{---}} количество работ во временном интервале <tex>t</tex>регулярный язык. Работы отсортированы в порядке Тогда язык <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_ncycle(L)</tex>также регулярен.|proof =
'''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>. Чтобы получить алгоритм с такой сложностью, мы распределяем работы так, чтобы после каждого шага i, сохранялся инвариант: <tex>l_1 \geqslant l_2 \geqslant \ldots \geqslant l_m </tex> при <tex>l_1 \geqslant T_i</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>
 
== Доказательство корректности ==
{{Теорема
|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 > B_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 B_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> оказался не максимальным.
}}
 
== См. также ==
* [[O2Cmax|<tex>O2 \mid \mid C_{max}</tex>]]
* [[Opi1sumu|<tex>O \mid p_{ij} = 1 \mid \sum U_i</tex>]]
* [[Opij1di|<tex> O \mid p_{i, j} = 1, d_i \mid - </tex>]]
* [[Opij1sumwu|<tex> O \mid p_{i, j} = 1 \mid - \sum w_{i} U_{i}</tex>]]
== Источники информации ==
* Peter Brucker «Scheduling Algorithms», fifth edition, Springer {{---}} с. 171-174 ISBN 978-3-540-69515-8
 
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]
Анна
577
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/57644»

Навигация