251
правка
Изменения
Нет описания правки
{{Задача|definition==Описание задачи==Дано <tex>m</tex> одинаковых станков, которые работают параллельно и <tex>n</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 leqslant d_1, d_{i2}\le leqslant d_2, \ldots, d_{ik}\le leqslant d_{k}</tex>.
Тогда, если заменить во всём расписании работу <tex>i_j</tex> на работу <tex>j</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>. Здесь можно назначить все нераспределяемые позже работы на это время, и сбросить их счетчик.
Так как и этот, и изучаемый алгоритм получают в итоге одинаковый фронт, а в этом мы вышли из нулевого времени, а невыполненные единицы работы остались, то так как распределить их никак невозможно, то не существует расписания, в котором бы выполнились все работы.
Сложность последней фазы зависит от того, каким алгоритмом граф разбивается на паросочетания. Использовав, например, алгоритм Куна, можно добиться сложности <tex>O(m \cdot M) = O(m \cdot n^3m^3)</tex>. Итоговая сложность алгоритма {{---}} <tex>O(n^3m^4)</tex>.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]
