<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= Задача о проверке на пустоту пересечения двух КС-грамматик неразрешима.|proof=Всегда существует оптимально расписание такоеПусть <tex>A = \{ (G_1, G_2) \mid L(G_1) \cap L(G_2) = \varnothing \}</tex>. Сведем [[Примеры неразрешимых задач: проблема соответствий Поста|проблему соответствий Поста]] к <tex>\overline{A}</tex>, таким образом показав, что в нем дополнение проблемы неразрешимо. Так как рекурсивные языки [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций|замкнуты относительно дополнения]], то из неразрешимости дополнения проблемы будет следовать неразрешимость самой проблемы. Для любого экземпляра ПСП <tex>(x_1, x_2, ..., x_n)</tex>C_i и <tex>(y_1, y_2, ..., y_n)</tex> над алфавитом <tex>\Sigma</tex> можно подобрать символ <tex>\# \notin \Sigma</tex>. Для каждого экземпляра построим грамматики:* <tex>G_1 : S \rightarrow aSa \mid a\leqslant m + i - 1#a</tex> для любого всех <tex>a \in \Sigma</tex>. Тогда <tex>i L(G_1) = 1 \ldots n{ w\#w^R \mid w \in \Sigma^* \}</tex>, где обозначение <tex>mw^R</tex> {{---}} количество станковразворот <tex>w</tex>.|proof=Рассмотрим оптимальное расписание * <tex>G_2 : S\rightarrow x_iSy^*R_i \mid x_i\#y^R_i</tex>, в котором для любого всех <tex>i = 1 , 2, \ldots k - 1dots n</tex> выполняется . Тогда <tex>C_i L(G_2) = \leqslant { 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 + i - \geqslant 1\}</tex>. Если данный экземпляр ПСП имеет решение, то <tex>L(G_2)</tex> содержит хотя бы одну строку вида <tex>w\#w^R</tex>, но поэтому <tex>L(G_1) \cap L(G_2) \ne \varnothing</tex>C_k , и наоборот, если он не имеет решения, то <tex> m + k - 1L(G_2)</tex>не содержит строк такого вида, где соответственно <tex>L(G_1) \cap L(G_2) = \varnothing</tex>. Таким образом мы свели проблему соответствий Поста к <tex>k\overline{A}</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|тандемный повтор]].
== Доказательство корректности ==Аналогично можно заметить, что пересечение <tex>L(G_1) \cap L(G_2) \ne \varnothing </tex> тогда и только тогда, когда <tex>L(G_1)\#L(G_2)^R</tex> содержит палиндром.
== См. также ==Таким образом, мы имеем:{{Утверждение* [[O2Cmax|statement= Пусть дана грамматика <tex>O2 \mid \mid C_{max}G</tex>]]* [[Opi1sumu|, <tex>O \mid p_{ij} L(G) = 1 \mid \sum U_iL</tex>]]. Тогда следующие задачи неразрешимы:* [[Opij1di|# Содержит ли <tex> O \mid p_{i, j} = 1, d_i \mid - L</tex>]]тандемный повтор.* [[Opij1sumwu|# Содержит ли <tex> O \mid p_{i, j} = 1 \mid - \sum w_{i} U_{i}L</tex>]]== Источники информации ==палиндром.* Peter Brucker «Scheduling Algorithms», fifth edition, Springer {{---}} с. 171-174 ISBN 978-3-540-69515-8 [[Категория: Алгоритмы и структуры данных]][[Категория: Теория расписаний]]
