|
|
| (не показано 19 промежуточных версий 2 участников) |
| Строка 1: |
Строка 1: |
| − | <tex dpi = "200"> O \mid p_{i,j} = 1 \mid \sum T_{i} </tex>
| |
| − | {{Задача
| |
| − | |definition=
| |
| − | Дано <tex>m</tex> одинаковых станков, которые работают параллельно, и <tex>n</tex> работ, которые необходимо выполнить в произвольном порядке на всех станках. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть время окончания <tex>d_i</tex> {{---}} время, до которого она должна быть выполнена. Необходимо минимизировать суммарную [[Классификация_задач#Критерий оптимизации|медлительность]].
| |
| − | }}
| |
| − | == Описание алгоритма ==
| |
| − | === Идея ===
| |
| − | Будем полагать, что работы заданы в порядке неубывания их дедлайнов, то есть <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>.
| |
| − | {{Лемма
| |
| − | |statement=
| |
| − | Пусть есть работы <tex>1 \ldots n</tex> с дедлайнами <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>. Тогда существует оптимальное расписание, в котором времена завершения работ идут в том же порядке, то есть <tex>C_1 \leqslant C_2 \leqslant \ldots \leqslant C_n</tex>.
| |
| − | |proof=
| |
| − | Рассмотрим две работы <tex>i</tex> и <tex>j</tex> из какого-либо оптимального расписания такие, что <tex>C_i > C_j</tex> и <tex>d_i < d_j</tex>. Поменяем эти работы в расписании местами, то есть <tex>C'_i = C_j</tex> и <tex>C'_j = C_i</tex>. Если они обе успевали выполниться вовремя, то это свойство сохранится, так как <tex>d_i < d_j</tex>, значит по-прежнему <tex>T_i = 0</tex> и <tex>T_j = 0</tex>, то есть значение целевой функции мы не ухудшили и расписание осталось оптимальным. Если обе работы не успевали выполниться вовремя, то когда мы поменяем их местами ничего не изменится, то есть значение целевой функции останется прежним, так как мы не меняли значения времен окончаний, а только поменяли их местами. Если работа <tex>j</tex> успевала выполниться, а <tex>i</tex> {{---}} нет, то мы снова не ухудшим значение целевой функции. Покажем это. До того, как мы поменяли работы местами, было <tex>T_i + T_j = C_i - d_i</tex>, так как <tex>T_j = 0</tex>. После того, как мы поменяли работы местами, <tex>T_i + 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)</tex>. Но так как работа <tex>j</tex> успевает выполниться до дедлайна, то <tex>C_j - d_j \leqslant 0</tex>.
| |
| − | }}
| |
| − | Далее будем рассматривать только оптимальное расписание со свойством <tex>C_1 \leqslant C_2 \leqslant \ldots \leqslant C_n</tex>.
| |
| | {{Теорема | | {{Теорема |
| − | |statement= | + | |statement= Задача о проверке на пустоту пересечения двух КС-грамматик неразрешима. |
| − | Всегда существует оптимально расписание такое, что в нем <tex>C_i \leqslant m + i - 1</tex> для любого <tex>i = 1 \ldots n</tex>, где <tex>m</tex> {{---}} количество станков.
| + | |proof= |
| − | |proof= | + | Пусть <tex>A = \{ (G_1, G_2) \mid L(G_1) \cap L(G_2) = \varnothing \}</tex>. Сведем [[Примеры неразрешимых задач: проблема соответствий Поста|проблему соответствий Поста]] к <tex>\overline{A}</tex>, таким образом показав, что дополнение проблемы неразрешимо. Так как рекурсивные языки [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций|замкнуты относительно дополнения]], то из неразрешимости дополнения проблемы будет следовать неразрешимость самой проблемы. |
| − | Рассмотрим оптимальное расписание <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>.
| |
| − | Будем выбирать эти периоды среди моментов времени, в которые выполняется наименьшее число работ.
| |
| | | | |
| − | === Псевдокод ===
| + | Для любого экземпляра ПСП <tex>(x_1, x_2, ..., x_n)</tex> и <tex>(y_1, y_2, ..., y_n)</tex> над алфавитом <tex>\Sigma</tex> можно подобрать символ <tex>\# \notin \Sigma</tex>. Для каждого экземпляра построим грамматики: |
| − | Определим ''вектор частот'' <tex>h(t)</tex> {{---}} количество работ во временном интервале <tex>t</tex>. Работы отсортированы в порядке <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>.
| + | * <tex>G_1 : S \rightarrow aSa \mid a\#a</tex> для всех <tex>a \in \Sigma</tex>. Тогда <tex>L(G_1) = \{ w\#w^R \mid w \in \Sigma^* \}</tex>, где обозначение <tex>w^R</tex> {{---}} разворот <tex>w</tex>. |
| | + | * <tex>G_2 : S \rightarrow x_iSy^R_i \mid x_i\#y^R_i</tex> для всех <tex>i = 1, 2, \dots n</tex>. Тогда <tex>L(G_2) = \{ x_{i_1} x_{i_2} \dots x_{i_m} \# (y_{i_1} y_{i_2} \dots y_{i_m})^R \mid i_1, i_2, \dots i_m \in \{ 1, 2, \dots n \}, m \geqslant 1 \}</tex>. |
| | | | |
| − | '''for''' <tex>t = 1</tex> '''to''' <tex>m + n - 1</tex>
| + | Если данный экземпляр ПСП имеет решение, то <tex>L(G_2)</tex> содержит хотя бы одну строку вида <tex>w\#w^R</tex>, поэтому <tex>L(G_1) \cap L(G_2) \ne \varnothing</tex>, и наоборот, если он не имеет решения, то <tex>L(G_2)</tex> не содержит строк такого вида, соответственно <tex>L(G_1) \cap L(G_2) = \varnothing</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>
| |
| − | <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>.
| |
| | | | |
| − | == Доказательство корректности ==
| + | Таким образом мы свели проблему соответствий Поста к <tex>\overline{A}</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 > 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> оказался не максимальным.
| |
| | }} | | }} |
| | + | Из неразрешимости вышеприведенной задачи следует неразрешимость ряда других задач. Рассмотрим несколько примеров. |
| | | | |
| − | == См. также ==
| + | По двум КС-грамматикам <tex>G_1</tex> и <tex>G_2</tex> можно построить КС-грамматику для [[Замкнутость КС-языков относительно различных операций#.D0.9A.D0.BE.D0.BD.D0.BA.D0.B0.D1.82.D0.B5.D0.BD.D0.B0.D1.86.D0.B8.D1.8F|конкатенации]] задаваемых ими языков <tex>L(G_1)L(G_2)</tex>. По аналогии с этим мы можем рассматривать язык <tex>L(G_1)\#L(G_2)\#</tex>, где <tex>\#</tex> {{---}} новый символ, не встречающийся в алфавите. Заметим, что пересечение языков непусто, то есть <tex>L(G_1) \cap L(G_2) \ne \varnothing </tex>, тогда и только тогда, когда <tex>L(G_1)\#L(G_2)\#</tex> содержит [[Алгоритм Ландау-Шмидта#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|тандемный повтор]]. |
| − | * [[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
| |
| | | | |
| − | [[Категория: Алгоритмы и структуры данных]]
| + | Аналогично можно заметить, что пересечение <tex>L(G_1) \cap L(G_2) \ne \varnothing </tex> тогда и только тогда, когда <tex>L(G_1)\#L(G_2)^R</tex> содержит палиндром. |
| − | [[Категория: Теория расписаний]]
| + | |
| | + | Таким образом, мы имеем: |
| | + | {{Утверждение |
| | + | |statement= Пусть дана грамматика <tex>G</tex>, <tex>L(G) = L</tex>. Тогда следующие задачи неразрешимы: |
| | + | # Содержит ли <tex>L</tex> тандемный повтор. |
| | + | # Содержит ли <tex>L</tex> палиндром. |
| | + | }} |
