577
правок
Изменения
→Псевдокод
=== Псевдокод ===
Пусть есть работы <tex>1 \ldots n</tex> с временами окончания <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>. Будем называть ''простоем '' временной интервал, в который на машине ничего не обрабатывается. Для определения работ, не укладывающихся в срок, заведем счетчик времени <tex>t</tex>, который будем модифицировать так, как показано ниже. Тогда следующий работа <tex>j</tex> опаздывает, если <tex>\left[ \dfrac{t}{m} \right] + p_j > d_j</tex>, где <tex>p_j = 1</tex>. Следующий алгоритм вычислит оптимальное множество <tex>S</tex>.
<tex>S = \varnothing</tex>
<tex>t = 0</tex>
'''for''' <tex>j = 1</tex> '''to''' <tex>n</tex>
'''if''' <tex>j</tex> опаздывает, и все более ранние простои заполнены
заменить <tex>i</tex> на <tex>j</tex> в <tex>S</tex>
'''else'''
<tex>t = t + 1</tex>
добавить <tex>i</tex> в <tex>S</tex> и поставить <tex>i</tex> на место самого раннего простоя
Таким образом, работы, не попавшие в <tex>S</tex>, будут иметь минимальное значение <tex>w_i</tex>.
