251
правка
Изменения
м
Опираясь на это утверждение, можно найти максимальное количество работ, которое можно выполнить===Оценка сложности алгоритма===Рассмотрим добавление очередной работы в тайм-слоты. Обозначим его За <tex>O(t)</tex> найдём переполнившийся тайм-слот и за <tex>kO(m)</tex> перекинем из него элемент. Так как <tex>t=O(nm)</tex>, итоговая сложность этой части {{---}} <tex>O(n^2m)</tex>.
Сведем задачу построения распинания по построенным таймДостроение графа до регулярного делается за <tex>O(E)</tex>, где <tex>E</tex> {{---}} количество ребер в нем. Количество ребер в регулярном двудольном графе <tex>E = Vd</tex>, где <tex>V</tex> {{---}} количество вершин в одной из долей, а <tex>d</tex> {{---}} степень. Количество вершин в правой доле {{---}} <tex>O(t) = O(nm)</tex>. Значит граф будет построен за <tex>O(nm^2)</tex>, так как степень каждой вершины {{---слотам к задаче о покрытии двудольного графа минимальным количеством паросочетаний}} <tex>m</tex>.
Построим двудольный Сложность последней фазы зависит от того, каким алгоритмом графразбивается на паросочетания. В левой доле вершинам будут соответствовать работыИспользовав, например, в правой {{---}} времена. Соответственноалгоритм Куна, в левой доле будет можно добиться сложности <tex>O(m \cdot M) = O(m \cdot n^3m^3)</tex> вершин, в правой . Итоговая сложность алгоритма {{---}} <tex>d_{max}</tex>. Ребро между работой <tex>i</tex> и временем <tex>t</tex> будет, если работа <tex>i</tex> есть в тайм-слоте <tex>t</tex>. Рассмотрим какое-то паросочетание <tex>M</tex> в этом графе. Оно соответствует корректному расписанию работ на одной машине: ни одна работа не выполняется два раза и ни в один момент времени не выполняется более одной работы. Тогда, если мы сможем построить множество мощности <tex>m</tex> такое, что каждое ребро находится хотя бы в одном из паросочетаний, то оно будет соответствовать тому, что каждая работа обработана на каждом станке, а значит, составлено корректное расписание для этих <tex>kO(n^3m^4)</tex> работ.
Достроим граф до регулярного степени <tex>m</tex>==См. Достраивать будем следующим образом. Каждая вершина в левой доле имеет степень также==* [[Opij1di|<tex>m</tex>O \mid p_{ij} = 1, так как каждая работа представлена в <tex>m</tex> тайм-слотах. В правой доле степень каждой вершины не больше <tex>m</tex>, так как в таймd_i \mid -слоте не может быть больше, чем <tex>m</tex> работ. Значит, в левой доле не больше вершин, чем в правой.Добавим в левую долю фиктивных вершин, чтобы количества вершин в левой и правой долях сравнялись. После чего просто будем добавлять ребра между вершинами, степень которых еще меньше <tex>m</tex>. Для покрытия этого графа паросочетаниями воспользуемся тем фактом, что регулярный двудольный граф степени <tex>d</tex> можно покрыть <tex>d</tex> паросочетаниями. ]]
При помощи построения паросочетаний было построено расписание для тех <tex>k</tex> работ==Источники информации==* Peter Brucker «Scheduling Algorithms», которые можно успеть сделать. Так как остальные работы уже нельзя успеть, расписание для них можно составить произвольное. Напримерfifth edition, выполнять их по очереди после выполнения первых <tex>k</tex> работSpringer {{---}} с.179 ISBN 978-3-540-69515-8
==Оценка сложности алгоритма==Рассмотрим добавление очередной работы в тайм-слоты. За <tex>O(t)</tex> найдём переполнившийся тайм-слот [[Категория: Алгоритмы и за <tex>O(m)</tex> перекинем из него элемент. Так как <tex>t=O(nm)</tex>, итоговая сложность этой части {{---}} <tex>O(n^2m)</tex>. Достроение графа до регулярного делается за <tex>O(E)</tex>, где <tex>E</tex> {{---}} количество ребер в нем. Количество ребер в регулярном двудольном графе <tex>E = Vd</tex>, где <tex>V</tex> {{---}} количество вершин в одной из долей, а <tex>d</tex> {{---}} степень. Количество вершин в правой доле {{---}} <tex>O(t) = O(nm)</tex>. Значит граф будет построен за <tex>O(nm^2)</tex>, так как степень каждой вершины {{---}} <tex>m</tex>.структуры данных]]Сложность последней фазы зависит от того, каким алгоритмом граф разбивается на паросочетания. Использовав, например, алгоритм Куна, можно добиться сложности <tex>O(m \cdot M) = O(m \cdot n^3m^3)</tex>. Итоговая сложность алгоритма {{---}} <tex>O(n^3m^4)</tex>.[[Категория: Теория расписаний]]
→Существование решения
<tex dpi ="200">O \mid p_{ij} =Описание задачи1 \mid \sum U_i</tex>{{Задача|definition==Дано <tex>m</tex> одинаковых станков, которые работают параллельно и <tex>n</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} \le d_1, d_{i2}\le d_2, \ldots, d_{ik}\le d_{k}</tex>.Тогда, если заменить во всём расписании работу <tex>i_j</tex> на работу <tex>j</tex>, то она, тем более, будет выполнена.}}
{{Определение
|definition=Обозначим за '''тайм-слот t'' ' <tex>t</tex> множество из не более, чем <tex>m</tex> различных чисел {{---}}
номера работ, которые мы хотим выполнить в момент времени <tex>t</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=Следуя этому алгоритму, расписания не существует тогда и только тогда, когда
переполнился нулевой тайм-слот.
|proof=
<tex>\Rightarrow</tex>
Расписания не существует, а значит, никакой алгоритм его не найдет.
<tex>\Leftarrow</tex>
Введем понятие ''фронта'' расписания. ''Фронтом'' назовем вектор размеров тайм-слотов. Заметим, что от того, в каком порядке происходят перебрасывания из переполнившихся тайм-слотов, итоговый фронт не зависит. Поэтому, если мы сначала положим все работы в тайм-слоты, игнорируя ограничение на их размер, а потом в каком-то порядке перекинем, итоговый фронт окажется тем же. В случае, если при построении тайм-слотов игнорировалось ограничение на их размер, ни одну единицу работы нельзя назначить позже.
Рассмотрим очередной тайм-слот. Пусть в нем занято <tex>h</tex> ячеек из <tex>m</tex>, а также есть еще <tex>a</tex> нераспределяемых позже единиц работы. Здесь возможны два случая:
* <tex>h + a > m</tex>. В этом случае, так как более <tex>m</tex> единиц работы сейчас выполнить нельзя, а также ничего нельзя назначить позже, то оказывается, что невыполняемых сейчас или позже работ стало <tex>h + a - m</tex>.
* Если <tex>h + a <= \leqslant m</tex>. Здесь можно назначить все нераспределяемые позже работы на это время, и сбросить их счетчик.
Так как и этот, и изучаемый алгоритм получают в итоге одинаковый фронт, а в этом мы вышли из нулевого времени, а невыполненные единицы работы остались, то так как распределить их никак невозможно, то не существует расписания, в котором бы выполнились все работы.
}}
