1632
правки
Изменения
м
Отсортируем работы в порядке невозрастания дедлайнов.
===Доказательство корректности===
{{Теорема
|statement=Если в оптимальном расписании можно сделать <tex>k</tex> работ, то можно сделать первые <tex>k</tex> работ.
|proof=Пусть в оптимальном расписании были сделаны работы <tex>i_1, i_2, \ldots, i_k</tex>. Докажем, что существует
оптимальное расписание, в котором сделаны работы <tex>1, 2, \ldots, k</tex>. Пусть работы <tex>i_1, i_2, \ldots, i_k</tex>
тоже отсортированы в порядке неубывания дедлайна. Тогда <tex>d_{i1} \leqslant d_1, d_{i2}\leqslant d_2, \ldots, d_{ik}\leqslant d_{k}</tex>.
Тогда, если заменить во всём расписании работу <tex>i_j</tex> на работу <tex>j</tex>, то она, тем более, будет выполнена.
}}
===Существование решения===
Опираясь на это утверждение, можно найти максимальное количество работ, которое можно выполнить. Обозначим его за <tex>k</tex>.
Сведем задачу построения распинания по построенным тайм-слотам к задаче о покрытии двудольного графа минимальным
количеством паросочетаний.
Построим двудольный граф. В левой доле вершинам будут соответствовать работы, в правой {{---}} времена. Соответственно, в левой доле будет <tex>n</tex> вершин, в правой {{---}} <tex>d_{max}</tex>. Ребро между работой <tex>i</tex> и временем <tex>t</tex> будет, если работа <tex>i</tex> есть в тайм-слоте <tex>t</tex>.
Рассмотрим какое-то паросочетание <tex>M</tex> в этом графе. Оно соответствует корректному расписанию работ на одной машине: ни одна работа не выполняется два раза и ни в один момент времени не выполняется более одной работы.
Тогда, если мы сможем построить множество мощности <tex>m</tex> такое, что каждое ребро находится хотя бы в одном из паросочетаний, то оно будет соответствовать тому, что каждая работа обработана на каждом станке, а значит, составлено корректное расписание для этих <tex>k</tex> работ.
Достроим граф до регулярного степени <tex>m</tex>. Достраивать будем следующим образом. Каждая вершина в левой доле имеет степень <tex>m</tex>, так как каждая работа представлена в <tex>m</tex> тайм-слотах. В правой доле степень каждой вершины не больше <tex>m</tex>, так как в тайм-слоте не может быть больше, чем <tex>m</tex> работ. Значит, в левой доле не больше вершин, чем в правой.
Добавим в левую долю фиктивных вершин, чтобы количества вершин в левой и правой долях сравнялись. После чего просто будем добавлять ребра между вершинами, степень которых еще меньше <tex>m</tex>. Для покрытия этого графа паросочетаниями воспользуемся тем фактом, что регулярный двудольный граф степени <tex>d</tex> можно покрыть <tex>d</tex> паросочетаниями.
При помощи построения паросочетаний было построено расписание для тех <tex>k</tex> работ, которые можно успеть сделать. Так как остальные работы уже нельзя успеть, расписание для них можно составить произвольное. Например, выполнять их по очереди после выполнения первых <tex>k</tex> работ.
rollbackEdits.php mass rollback
==Алгоритм==
===Описание алгоритма===
{{Определение
|definition=Обозначим за '''тайм-слот''' <tex>t</tex> множество из не более, чем <tex>m</tex> различных чисел {{---}}
которой там еще нет, в него. Так как в нем меньше элементов, то по принципу Дирихле, это можно сделать.
Сведем задачу построения распинания по построенным тайм-слотам к задаче о покрытии двудольного [[Основные_определения_теории_графов|графа]] минимальным количеством [[Паросочетания:_основные_определения,_теорема_о_максимальном_паросочетании_и_дополняющих_цепях|паросочетаний]]. Определим <tex>k</tex> как максимальное число работ, которые можно успеть выполнить. Построим двудольный граф. В левой доле вершинам будут соответствовать работы, в правой {{Утверждение---}} времена. Соответственно, в левой доле будет <tex>n</tex> вершин, в правой {{---}} <tex>d_{max}</tex>. Ребро между работой <tex>i</tex> и временем <tex>t</tex> будет, если работа <tex>i</tex> есть в тайм-слоте <tex>t</tex>. Рассмотрим какое-то паросочетание <tex>M</tex> в этом графе. Оно соответствует корректному расписанию работ на одной машине: ни одна работа не выполняется два раза и ни в один момент времени не выполняется более одной работы. Тогда, если мы сможем построить множество мощности <tex>m</tex> такое, что каждое ребро находится хотя бы в одном из паросочетаний, то оно будет соответствовать тому, что каждая работа обработана на каждом станке, а значит, составлено корректное расписание для этих <tex>k</tex> работ. Достроим граф до регулярного степени <tex>m</tex>. Достраивать будем следующим образом. Каждая вершина в левой доле имеет степень <tex>m</tex>, так как каждая работа представлена в <tex>m</tex> тайм-слотах. В правой доле степень каждой вершины не больше <tex>m</tex>, так как в тайм-слоте не может быть больше, чем <tex>m</tex> работ. Значит, в левой доле не больше вершин, чем в правой.Добавим в левую долю фиктивных вершин, чтобы количества вершин в левой и правой долях сравнялись. После чего просто будем добавлять ребра между вершинами, степень которых еще меньше <tex>m</tex>. Для покрытия этого графа паросочетаниями воспользуемся тем фактом, что регулярный двудольный граф степени <tex>d</tex> можно покрыть <tex>d</tex> паросочетаниями. При помощи построения паросочетаний было построено расписание для тех <tex>k</tex> работ, которые можно успеть сделать. Так как остальные работы уже нельзя успеть, расписание для них можно составить произвольное. Например, выполнять их по очереди после выполнения первых <tex>k</tex> работ. <!--{{Теорема|statement=Если в оптимальном расписании можно сделать <tex>k</tex> работ, то можно сделать первые <tex>k</tex> работ.|proof=Пусть в оптимальном расписании были сделаны работы <tex>i_1, i_2, \ldots, i_k</tex>. Докажем, что существует оптимальное расписание, в котором сделаны работы <tex>1, 2, \ldots, k</tex>. Пусть работы <tex>i_1, i_2, \ldots, i_k</tex>тоже отсортированы в порядке неубывания дедлайна. Тогда <tex>d_{i1} \leqslant d_1, d_{i2}\leqslant d_2, \ldots, d_{ik}\leqslant d_{k}</tex>.Тогда, если заменить во всём расписании работу <tex>i_j</tex> на работу <tex>j</tex>, то она, тем более, будет выполнена.}}--> ===Существование решения==={{Теорема
|statement=Следуя этому алгоритму, расписания не существует тогда и только тогда, когда
переполнился нулевой тайм-слот.
Так как и этот, и изучаемый алгоритм получают в итоге одинаковый фронт, а в этом мы вышли из нулевого времени, а невыполненные единицы работы остались, то так как распределить их никак невозможно, то не существует расписания, в котором бы выполнились все работы.
}}
===Оценка сложности алгоритма===
Сложность последней фазы зависит от того, каким алгоритмом граф разбивается на паросочетания. Использовав, например, алгоритм Куна, можно добиться сложности <tex>O(m \cdot M) = O(m \cdot n^3m^3)</tex>. Итоговая сложность алгоритма {{---}} <tex>O(n^3m^4)</tex>.
==См. также==
* [[Opij1di|<tex>O \mid p_{ij} = 1, d_i \mid - </tex>]]
==Источники информации==
