577
правок
Изменения
→Псевдокод
<tex>h(t) = 0</tex>
'''for''' <tex>i = 1</tex> '''to''' <tex>n</tex>
'''for''' <tex>j = d_i</tex> '''to''' <tex>d_i - m + 1</tex> <font color=green>(1)</font>
<tex>h(j) = h(j) + 1</tex>
'''while''' <tex>\exists k > 1</tex> '''and''' <tex>h(k) = m + 1</tex> <font color=green>(2)</font>
'''find''' <tex>\min\{k_0 \mid h(k_0) = m + 1\}</tex>
<tex>h(k_0 - 1) = h(k_0 - 1) + 1</tex>
'''else'''
'''return''' false
''Замечание:'' если расписание существует, то оно может быть вычислено данным алгоритмом, если добавить в цикл (1) функцию, отвечающую за добавление работы <tex>i</tex> на момент <tex>j</tex> в расписании для соответствующей машины и в цикл (2) функцию, отвечающую за перемещение работы, которой нет во временном интервале <tex>k_0 - 1</tex>, но которая есть в <tex>k_0</tex> на момент <tex>k_0 - 1</tex> в той же машине.
=== Асимптотика ===
Покажем, что данный алгоритм может быть реализован за время <tex>O(nm)</tex>.
