577
правок
Изменения
→Псевдокод
Определим <tex>h(t)</tex> {{---}} количество работ во временном интервале <tex>t</tex>.
'''void''' checkExistenceOfSchedule('''int[]'''* <tex>d</tex>):
<tex>T = \max\{d_i \mid i = 1 \ldots n\}</tex>
'''for''' <tex>t = 1</tex> '''to''' <tex>T</tex>
<tex>h(k_0) = m</tex>
'''if''' <tex>h(1) \leqslant m</tex>
'''return''' ''' true'''
'''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> в той же машине (этот шаг будет обоснован далее в доказательстве корректности).
