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]\triangleleft[/math]

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

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