<tex dpi = "200"> O \mid p_{i,j} = 1, d_i \mid - </tex>{{ЗадачаТеорема|definitionstatement=Дано <tex>m</tex> одинаковых станков, которые работают параллельно, и <tex>n</tex> работ, которые необходимо выполнить в произвольном порядке на всех станках. Любая работа Задача о проверке на любом станке выполняется единицу времени. Для каждой работы есть время окончания <tex>d_i</tex> {{пустоту пересечения двух КС---}} время, до которого она должна быть выполнена. Необходимо проверить, существует ли расписание, при котором все работы будут выполнены вовремяграмматик неразрешима.}} == Описание алгоритма ===== Идея ==={| class="wikitable" styleproof="float:right; margin-left: 10px;"|-! ! style="width:50px;"|Пусть <tex>t A = 1</tex>! style\{ (G_1, G_2) \mid L(G_1) \cap L(G_2) ="width:50px;"|<tex>2\varnothing \}</tex>! style="width:50px;"|<tex>...</tex>! style="width:50px;"|<tex>d_i - m + 1</tex>! style="width:50px;"|<tex>d_i - m + 2</tex>! style="width:50px;"|<tex>...</tex>! style="width:50px;"|<tex>d_i - 1</tex>! style="width:50px;"|<tex>d_i</tex>|-! style="widthСведем [[Примеры неразрешимых задач:50px;"|<tex>m = 1</tex>| | | | style="text-align:center;"|<tex>i</tex>| | |||-! style="width:50px;"|<tex>2</tex>| | | | | style="text-align:center;"|<tex>i</tex>| |||-! style="width:50px;"проблема соответствий Поста|проблему соответствий Поста]] к <tex>\vdots</tex>| | | | | | |||-! style="width:50px;"|<tex>m - 1</tex>| | | | || | style="text-align:center;"|<tex>i</tex>||-! style="width:50px;"|<tex>m</tex>| | | | || | | style="text-align:center;"|<tex>i</tex>|-! colspan="9"|Табл. 1. Работа <tex>i</tex> назначена на интервалы <tex>d_i - m + 1 \ldots d_i</tex>.|overline{A}Заметим, что если <tex>d_i < m</tex>, то очевиднотаким образом показав, что <tex>C_i > d_i</tex>, следовательно, расписания не существуетдополнение проблемы неразрешимо. Поэтому будем полагатьТак как рекурсивные языки [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций|замкнуты относительно дополнения]], что <tex>m \leqslant d_i</tex> для <tex>i = 1 \ldots n</tex>то из неразрешимости дополнения проблемы будет следовать неразрешимость самой проблемы.
Определим Для любого экземпляра ПСП <tex>T = \max\limits_{i \in [1(x_1, x_2, ..., n]}d_ix_n)</tex> {{---}} количество временных интервалов и <tex>[t - 1(y_1, t]</tex>y_2, где <tex>t = 1 \ldots T</tex>. Будем обозначать <tex>[t - 1.., t]y_n)</tex> как над алфавитом <tex>t\Sigma</tex>. Для каждого из них мы можем назначить не более можно подобрать символ <tex>m\# \notin \Sigma</tex> работ (по одной на каждый станок). Для каждой работы каждого экземпляра построим грамматики:* <tex>iG_1 : S \rightarrow aSa \mid a\#a</tex> будем назначать времена обработки на каждой из машин следующим образом: на машине для всех <tex>ma \in \Sigma</tex> работа займет временной интервал . Тогда <tex>d_iL(G_1) = \{ w\#w^R \mid w \in \Sigma^* \}</tex>, на машине где обозначение <tex>(m - 1)w^R</tex> {{---}} интервал разворот <tex>(d_i - 1)w</tex> и так далее, на машине .* <tex>1G_2 : S \rightarrow x_iSy^R_i \mid x_i\#y^R_i</tex> работа займет временной интервал для всех <tex>d_i - m + i = 1, 2, \dots n</tex>. В случае коллизий, то есть если найдется временной интервал Тогда <tex>k > 1</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, содержащий <tex>m + \dots i_m \in \{ 1</tex> работу, возьмем минимальный такой <tex>k</tex> и перенесем лишнюю работу из него на ту же машину2, но на один временной интервал левее. Будем повторять этот процесс\dots n \}, пока необходимо (и пока <tex>k > m \geqslant 1\}</tex>). Таким образом, только первый временной интервал может содержать более <tex>m</tex> работ. Причем это может произойти тогда и только тогда, когда задача не имеет решения, то есть не существует расписания, при котором все работы будут выполнены вовремя.
=== Псевдокод ===Определим Если данный экземпляр ПСП имеет решение, то <tex>L(G_2)</tex> содержит хотя бы одну строку вида <tex>w\#w^R</tex>, поэтому <tex>L(G_1) \cap L(G_2) \ne \varnothing</tex>, и наоборот, если он не имеет решения, то <tex>hL(tG_2)</tex> {{---}} количество работ во временном интервале не содержит строк такого вида, соответственно <tex>tL(G_1) \cap L(G_2) = \varnothing</tex>.
'''void''' checkExistenceOfSchedule('''int'''* Таким образом мы свели проблему соответствий Поста к <tex>d</tex>): <tex>T = \max\overline{d_i \mid i = 1 \ldots n\A}</tex> '''for''' <tex>t = 1</tex> '''to''' <tex>T</tex> <tex>h(t) = 0</tex> '''for''' <tex>i = 1</tex> '''to''' <tex>n</tex> '''for''' <tex>j = d_i</tex> '''to''' <tex>d_i , следовательно, задача о проверке на пустоту пересечения двух КС- m + 1</tex> <font color=green>(1)</font>грамматик неразрешима. <tex>h(j) = h(j) + 1</tex> '''while''' <tex>\exists k > 1</tex> '''and''' <tex>h(k) = m + 1</tex> <font color=green>(2)</font> '''find''' <tex>\min\{k_0 \mid h(k_0) = m + 1\}</tex> <tex>h(k_0 - 1) = h(k_0 - 1) + 1</tex> <tex>h(k_0) = m</tex> '''if''' <tex>h(1) \leqslant m</tex> '''return''' true '''else'''} '''return''' false''Замечание:'' если расписание существует, то оно может быть вычислено данным алгоритмом, если добавить в цикл (1) функцию, отвечающую за добавление работы <tex>i</tex> на момент <tex>j</tex> в расписании для соответствующей машины и в цикл (2) функцию, отвечающую за перемещение работы, которой нет во временном интервале <tex>k_0 - 1</tex>, но которая есть в <tex>k_0</tex>, на момент <tex>k_0 - 1</tex> в той же машине (этот шаг будет обоснован далее в доказательстве корректности)Из неразрешимости вышеприведенной задачи следует неразрешимость ряда других задач. Рассмотрим несколько примеров.
=== Асимптотика ===Покажем, что данный алгоритм может быть реализован за время По двум КС-грамматикам <tex>O(nm)G_1</tex>.<br>Для начала рассмотрим следующий вопрос: пусть и <tex>UG_2</tex> {{-можно построить КС--}} множество работ, грамматику для которого существует расписание, в котором отсутствуют опаздывающие работы, пусть <tex>i</tex> {{[[Замкнутость КС---}} работа, не принадлежащая <tex>U</tex>, для которой выполняется неравенство <tex>d_j \leqslant d_i</tex> для любой <tex>j \in U</tex>языков относительно различных операций#.D0.9A.D0.BE.D0.BD.D0.BA.D0.B0.D1.82.D0.B5. Можно ли построить расписание для множества <tex>V = U \cup \{i\}</tex>, в котором так же будут отсутствовать опаздывающие работыD0.<br>Введем несколько обозначенийBD. Вектора <tex>h</tex>, соответствующие множествам <tex>U</tex> и <tex>V</tex> обозначим как <tex>h^U</tex> и <tex>h^V</tex> соответственноD0. <tex>x(d_i)</tex> {{---}} количество временных интервалов <tex>t</tex> со свойствами*<tex>d_i - m + 1 \leqslant t \leqslant d_i</tex>,*<tex>h^U(t) < m</tex>B0.Будем говорить, что множество работ может быть выполнено ''вовремя'', если существует расписание, в котором все работы из этого множества успевают выполниться без опозданийD1. {{Лемма|statement=Пусть даны работы <tex>1, 2 \ldots i</tex> с дедлайнами <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_i</tex>, <tex>U = \{1, 2, \ldots i - 1\}</tex> и <tex>V = U \cup \{i\}</tex>86. Тогда для всех работ <tex>j = d_i - m + 1 \ldots d_i</tex>, для которых <tex>h^U(j) < m</tex>, будет верно, что <tex>h^V(j) = h^U(j) + 1</tex>D0.|proof=Рассмотрим вектора <tex>h^U</tex> и <tex>h^V</tex> после <tex>i - 1</tex> и <tex>i</tex> итераций алгоритмаB8. Заметим, что значения вектора <tex>h</tex>, не превосходящие <tex>m</tex>, то есть <tex>h(j) < m</tex>, никогда не уменьшаютсяD1. Следовательно, если <tex>d_i - m + 1 \leqslant j \leqslant d_i</tex> и <tex>h^U(j) < m8F|конкатенации]] задаваемых ими языков </tex>, то <tex>h^VL(jG_1) \geqslant h^UL(jG_2) + 1</tex>. Чтобы показать, что ситуация, когда при тех же условиях По аналогии с этим мы можем рассматривать язык <tex>h^VL(jG_1) \geqslant h^U(j) + 2</tex>, невозможна, рассмотрим расписание, построенное алгоритмом.<br>Если <tex>h^V#L(jG_2) \geqslant h^U(j) + 2</tex>, то это значит, что в течение <tex>i</tex> итерации во временной интервал <tex>j</tex> была добавлена работа <tex>i#</tex> и еще как минимум одна работа, пусть работа <tex>k</tex>, была перемещена из временного интервала <tex>j + 1где </tex> в <tex>j</tex>. Это возможно только если работа <tex>k</tex> ни на одной машине не была назначена до временного интервала <tex>j</tex>. Следовательно, работа <tex>k</tex> выполняется во временной интервал <tex>j</tex> и некоторые временные интервалы <tex>v > j + 1</tex>, откуда следует, что <tex>j < d_k - m + 1 \leqslant d_i - m + 1</tex>, что приводит нас к противоречию.}}{{Теорема|statement=Пусть <tex>U#</tex> {{---}} множество работновый символ, которое может быть выполнено вовремяне встречающийся в алфавите. Заметим, пусть <tex>i</tex> {{---}} работачто пересечение языков непусто, не принадлежащая то есть <tex>U</tex>, для которой выполняется неравенство <tex>d_j L(G_1) \leqslant d_i</tex> для любой <tex>j \in U</tex>. Тогда множество работ <tex>V = U cap L(G_2) \cup ne \{i\}varnothing </tex> может быть выполнено вовремя , тогда и только тогда, когда <tex>xL(d_iG_1) + \sum\limits_{t = 1}^{d_i - m}#L(m - h^U(t)G_2) \geqslant m#</tex> (1)содержит [[Алгоритм Ландау-Шмидта#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|тандемный повтор]].|proof= Неравенство (1) равносильно Аналогично можно заметить, что пересечение <tex>L(d_i - m)m \geqslant \sum\limits_{t = 1}^{d_i - m}h^U(t) + m - x(d_iG_1)</tex>. По лемме имеем <tex>\sum\limits_{j = d_i - m + 1}^{d_i}h^Vcap L(jG_2) = \sumne \limits_{j = d_i - m + 1}^{d_i}h^U(j) + x(d_i)</tex>. Вычитая это равенство из <tex>\sum\limits_{j = 1}^{d_i}h^V(j) = \sum\limits_{j = 1}^{d_i}h^U(j) + mvarnothing </tex>тогда и только тогда, получим когда <tex>\sum\limits_{t = 1}^{d_i - m}h^V(t) = m - xL(d_iG_1) + \sum\limits_{t = 1}^{d_i - m}h^U(t)</tex>. Следовательно, мы пришли к тому, что #L(1G_2) равносильно <tex>(d_i - m)m \geqslant \sum\limits_{t = 1}^{d_i - m}h^U(t)</tex>. Обозначим <tex>T = d_i - m</tex>, тогда предыдущее равенство превращается в <tex>Tm \geqslant \sum\limits_{t = 1}^{T}h^U(t)R</tex> (2)содержит палиндром.<br>Остается показать, что если равенство (2) выполняется для <tex>T = d_i - m</tex>, тогда оно выполняется и для <tex>T = 1, \ldots d_i - m - 1</tex>.}}
== Доказательство корректности ==Таким образом, мы имеем:{{ТеоремаУтверждение|statement=Для множества работ с дедлайнами Пусть дана грамматика <tex>d_1, d_2, \ldots d_nG</tex> задача имеет решение тогда и только тогда, когда <tex>hL(1G) \leqslant m= L</tex>.Тогда следующие задачи неразрешимы:|proof=# Содержит ли <tex>\RightarrowL</tex><br>Если задача имеет решение, то очевидно, что первый временной интервал не может быть переполнентандемный повтор.<br><tex>\Leftarrow</tex> Изначально алгоритм присваивает все стадии обработки каждой работы <tex>i</tex> (то есть обработку на каждом станке) попарно различным временным интервалам. Если <tex>\exists k > 1 : h(k) = m + 1</tex> и <tex>h(k - 1) \leqslant m</tex>, то это значит, что существует как минимум одна работа, которая назначена временному интервалу <tex>k</tex>, но которой нет во временном интервале <tex>k - 1</tex>. Следовательно, после перемещения вектор <tex>h</tex> по-прежнему будет удовлетворять условию, что каждая работа принадлежит # Содержит ли <tex>mL</tex> разным временным интервалам, причем в каждом из них она будет выполняться на разных машинах, так как при перемещении работ машины остаются прежними. Таким образом, если <tex>h(1) \leqslant m</tex>, то <tex>h(t) \leqslant m</tex>, где <tex>t = 1 \ldots T</tex>, то есть существует решение, при котором все работы будут выполнены вовремяпалиндром.
}}
