Opi1sumu

Описание задачи

Дано [math]m[/math] одинаковых станков, которые работают параллельно и [math]n[/math] работ, котороые необходимо выполнить в произвольном порядке на всех станках. Время выполнения каждой работы на любом станке одинаково и равно одному. Для каждой работы известно время, до которого её необходимо выполнить. Необходимо успеть выполнить как можно больше работ.

Описание алгоритма

Отсортируем работы в порядке невозрастания дедлайнов.

Утверждение:

Если в оптимальном расписании можно сделать [math]k[/math] работ, то можно сделать первые [math]k[/math] работ.

[math]\triangleright[/math]

Пусть в оптимальном расписании были сделаны работы [math]i_1, i_2, \ldots, i_k[/math]. Докажем, что существует оптимальное расписание, в котором сделаны работы [math]1, 2, \ldots, k[/math]. Пусть работы [math]i_1, i_2, \ldots, i_k[/math] тоже отсортированы в порядке неубывания дедлайна. Тогда [math]d_{i1} \le d_1, d_{i2}\le d_2, \ldots, d_{ik}\le d_{k}[/math]. Тогда, если заменить во всём расписании работу [math]i_j[/math] на работу [math]j[/math], то она, тем более, будет выполнена.

[math]\triangleleft[/math]

Определение:

Обозначим за тайм-слот t множество из не более, чем [math]m[/math] различных чисел — номера работ, которые мы хотим выполнить в момент времени [math]t[/math].

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

Утверждение:

Следуя этому алгоритму, расписания не существует тогда и только тогда, когда переполнился нулевой тайм-слот.

[math]\triangleright[/math]

[math]\Rightarrow[/math] Расписания не существует, а значит, никакой алгоритм его не найдет. [math]\Leftarrow[/math] Пусть при добавлении [math]k+1[/math]-й работы произошло переполнение нулевого тайм-слота. Рассмотрим алгоритм добавления в тайм-слоты: работа [math]i[/math]добавляется в тайм-слоты [math][d_i - m + 1; d_i][/math], после чего из переполнившихся работы перебрасываются в более ранние. Временно разрешим хранить в тайм-слоте сколь угодно много работ: отменим перебрасывание. Посмотрим на то, что получилось. Так как работу нельзя выполнять одновременно на двух станках, то ни одну единицу работы отсрочить нельзя. Будем рассматривать тайм-слоты в порядке уменьшения времени. Если в очередном тайм-слоте [math]t[/math] в данный момент больше, чем [math]m[/math] работ, то остаток нужно перекинуть на какие-то более ранние тайм-слоты. Заметим, что выгоднее перекинуть на наиболее поздние тайм-слоты: более ранние тайм-слоты могут понадобиться для перекидываний с тайм-слотов, идущих раньше просматриваемого. . Также заметим, что алгоритм перекидывания работ таков, что итоговое распределение количеств работ в соответствующих тайм-слотах не зависит от того, в каком порядке обрабатывались переполнившиеся тайм-слоты. При рассмотрении очередного переполнившегося тайм-слота мы необходимо должны куда-то перекинуть несколько работ из него. Так как перекидывание происходит в тайм-слот с наибольшим допустимым временем, то то, что неоходимо перекинуть что-то из нулевого, влечет то, что не существует расписания, в котором можно успеть выполнить все эти работы

[math]\triangleleft[/math]

Опираясь на это утверждение, можно найти максимальное количество работ, которое можно выполнить. Обозначим его за [math]k[/math].

Сведем задачу построения распинания по построенным тайм-слотам к задаче о покрытии двудольного графа минимальным количеством паросочетаний.

Построим двудольный граф. В левой доле вершинам будут соответствоввать работы, в правой — времена. Соответственно, в левой доле будет [math]n[/math] вершин, в правой — [math]d_{max}[/math]. Ребро между работой [math]i[/math] и временем [math]t[/math] будет, если работа [math]i[/math] есть в тайм-слоте [math]t[/math].

Рассмотрим какое-то паросочетание [math]M[/math] в этом графе. Оно соответствует корректному расписанию работ на одной машине: ни одна работа не выполняется два раза, и ни в один момент времени не выполняется более одной работы.

Тогда, если мы сможем построить множество мощности [math]m[/math] такое, что каждое ребро находится хотя бы в одном из паросочетаний, то оно будет соответствовать тому, что каждая работа обработана на каждом станке, а значит, составлено корректное расписание для этих [math]k[/math] работ.

Достроим граф до регулярного степени [math]m[/math]. Достраивать будем следующим образом. Каждая вершина в левой доле имеет степень [math]m[/math], так как каждая работа представлена в [math]m[/math] тайм-слотах. В правой доле степень каждой вершины не больше [math]m[/math], так как в тайм-слоте не может быть больше, чем [math]m[/math] работ. Значит, в левой доле не больше вершин, чем в правой. Добавим в левую долю фиктивных вершин, чтобы количества вершин в левой и правой долях сравнялись. После чего просто будем добавлять ребра между вершинами, степень которых еще меньше [math]m[/math]. Для покрытия этого графа паросочетаниями воспользуемся тем фактом, что регулярный двудольный граф степени [math]d[/math] можно покрыть [math]d[/math] паросочетаниями.

При помощи построения паросочетаний было построено расписание для тех [math]k[/math] работ, которые можно успеть сделать. Так как остальные работы уже нельзя успеть, расписание для них можно составить произвольное. Например, выполнять их по очереди после выполнения первых [math]k[/math] работ.

Оценка сложности алгоритма

Рассмотрим добавление очередной работы в тайм-слоты. За [math]O(t)[/math] найдём переполнившийся тайм-слот и за [math]O(m)[/math] перекинем из него элемент. Так как [math]t=O(nm)[/math], итоговая сложность этой части — [math]O(n^2m)[/math].

Достроение графа до регулярного делается за [math]O(E)[/math], где [math]E[/math] — количество ребер в нем. Количество ребер в регулярном двудольном графе [math]E = Vd[/math], где [math]V[/math] — количество вершин в одной из долей, а [math]d[/math] — степень. Количество вершин в правой доле — [math]O(t) = O(nm)[/math]. Значит, граф будет построен за [math]O(nm^2)[/math], так как степень каждой вершины — [math]m[/math].

Сложность последней фазы зависит от того, каким алгоритмом граф разбивается на паросочетания. Использовав, например, алгоритм Куна, можно добиться сложности [math]O(m \cdot M) = O(m \cdot n^3m^3)[/math]. Итоговая сложность алгоритма — [math]O(n^3m^4)[/math].