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