577
правок
Изменения
Нет описания правки
{{Теорема
|statement=Всегда существует оптимально расписание такое, что в нем <tex>C_i \leqslant m + i Задача о проверке на пустоту пересечения двух КС- 1</tex> для любого <tex>i = 1 \ldots n</tex>, где <tex>m</tex> {{---}} количество станковграмматик неразрешима.|proof=Рассмотрим оптимальное расписание Пусть <tex>S^*</tex>A = \{ (G_1, в котором для любого <tex>i = 1 G_2) \ldots k - 1</tex> выполняется <tex>C_i mid L(G_1) \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 cap L(G_2) = m</tex>.<br>Теперь пусть <tex>C_k = m + k + t</tex>, где <tex>t \geqslant 0varnothing \}</tex>. Будем называть ''итерацией обработки'' работы обработку на одной машине. Разобьем все работы на три множестваСведем [[Примеры неразрешимых задач:* множество <tex>Aпроблема соответствий Поста|проблему соответствий Поста]] к </tex> будет содержать все итерации обработки работ <tex>i = 1 \ldots k - 1</tex>* множество <tex>B</tex> overline{{---}} все итерации, запланированные в расписании <tex>S^*</tex> строго после момента времени <tex>k + m + t</tex>* множество <tex>C</tex> {{---}A} итерации обработки работ <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>0</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>0</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>(x_1, x_2, ..., x_n)</tex> и <tex>(y_1, y_2, ..., y_n)</tex> над алфавитом <tex>\Sigma</tex> можно подобрать символ <tex>\# \notin \Sigma</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>.
Если данный экземпляр ПСП имеет решение, то <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>.
