Изменения
Новая страница: «==Описание задачи== Дано <tex>m</tex> одинаковых станков, которые работают параллельно и <tex>n</tex...»
==Описание задачи==
Дано <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>k</tex>.
Сведем задачу построения распинания по построенным тайм-слотам к задаче о покрытии двудольного графа минимальным
количеством паросочетаний.
Дано <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>k</tex>.
Сведем задачу построения распинания по построенным тайм-слотам к задаче о покрытии двудольного графа минимальным
количеством паросочетаний.
