Opi1sumu

2012-06-18T08:50:59Z

109.188.213.66: /* Описание алгоритма */

==Описание задачи==
Дано <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>m</tex> различных чисел {{---}}
номера работ, которые мы хотим выполнить в момент времени <tex>t</tex>.
}}

Введем тайм-слот для каждого момента времени от <tex>0</tex> до <tex>d_n</tex>.
Каждую работу будем пытаться сделать как можно позже. Будем рассматривать работы в порядке невозрастания дедлайнов.
<tex>i</tex>-ю работу попытаемся добавить в тайм-слоты с номерами от <tex>d_i - m + 1</tex> по <tex>d_i</tex>.
После добавления некоторые тайм-слоты могли переполниться (тайм-слот переполнился, если в нём уже находилось
<tex>m</tex> работ, и в него добавили <tex>m+1</tex>-ю).
Для переполнившегося тайм-слота найдём найдем самый правый левее него тайм-слот, который ещё не переполнился и перекинем работу,
которой там еще нет, в него. Так как в нем меньше элементов, то, по принципу Дирихле, это можно сделать.

{{Утверждение
|statement=Следуя этому алгоритму, расписания не существует тогда и только тогда, когда
переполнился нулевой тайм-слот.
|proof=
<tex>\Rightarrow</tex>
Расписания не существует, а значит, никакой алгоритм его не найдет.

<tex>\Leftarrow</tex>
Пусть при добавлении <tex>k+1</tex>-й работы произошло переполнение нулевого тайм-слота.

Рассмотрим алгоритм добавления в тайм-слоты: работа <tex>i</tex>добавляется в тайм-слоты <tex>[d_i - m + 1; d_i]</tex>, после чего из переполнившихся работы перебрасываются в более ранние. Временно разрешим хранить в тайм-слоте сколь угодно много работ: отменим перебрасывание. Посмотрим на то, что получилось. Так как работу нельзя выполнять одновременно на двух станках, то ни одну единицу работы отсрочить нельзя. Будем рассматривать тайм-слоты в порядке уменьшения времени. Если в очередном тайм-слоте <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> работ.

==Оценка сложности алгоритма==
Рассмотрим добавление очередной работы в тайм-слоты. За <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>.

Викиконспекты - Вклад участника [ru]

Opi1sumu