90
правок
Изменения
→Описание алгоритма
Введем понятие ''фронта'' расписания. ''Фронтом'' назовем вектор размеров тайм-слотов. Заметим, что от того, в каком порядке происходят перебрасывания из переполнившихся тайм-слотов, итоговый фронт не зависит. Поэтому, если мы сначала положим все работы в тайм-слоты, игнорируя ограничение на их размер, а потом в каком-то порядке перекинем, итоговый фронт окажется тем же. В случае, если при построении тайм-слотов игнорировалось ограничение на их размер, ни одну единицу работы нельзя назначить позже.
Будем также рассматривать тайм-слоты без номеров работ: в каждом тайм-слоте просто лежит сколько-то единиц работ. От этого итоговый фронт также не изменится. Заметим, что если нельзя составить корректную в плане наполненности конфигурацию тайм-слотов при данном ослаблении, то нельзя это сделать и в случае существования номера у каждой единицы работы. Будем рассматривать тайм-слоты по убыванию времени с <tex>d_1</tex> до <tex>0</tex>. В каждый момент времени будем хранить, сколько работ ''необходимо'' перекинуть на более ранние тайм-слоты. Изначально это число равно нулю.
Рассмотрим очередной тайм-слот. Пусть в нем занято <tex>h</tex> ячеек из <tex>m</tex>, а также, есть еще <tex>a</tex> нераспределяемых позже единиц работы. Здесь возможны два случая:
