Доказательство центрального утверждения 1
Обозначим через Xi время простоя 2-го станка после окончания обработки детали Pi–1 и до нача-ла обработки детали Pi (i = 2, …, n); через X1 обозначим время между началом обработки 1-ой детали на станке 1 и началом её обработки на станке 2, т.е. начальный период простоя 2-го станка. По определению,
X1= A1 (8)
(т.е. 2-й станок начинает обрабатывать деталь P1 сразу после того, как она обработана на 1-м станке). Далее, при A1 + A2 > X1+ B1 сразу получаем, что
X2= A1 + A2 – B1 – X1> 0; (9)
при A1 + A2 X1+ B1 получаем, что X2= 0, поэтому можно написать общую для обоих случаев форму-лу X2= max{A1 + A2 – B1, 0}. Имеет место
Лемма 1.
Xr = max{ 
– 
– 
, 0} (r = 1, …, n). (10)
Доказательство. + – это, по определению, время, за которое 2-й станок обрабо-тает первые (r–1) деталей; – время, за которое 1-й станок обработает первые r деталей. Мо-мент, когда 2-й станок может начать обработку детали Pr, определяется максимумом из этих двух мо-ментов времени, откуда и следует формула (10)
Лемма 2. Пусть a = max{0, c–d}. Тогда
a + d = max{c, d}. (11)
Для доказательства достаточно заметить, что при cd a=c–d и а+d=с=max{c, d}. Если же с<d, то а=0 и а+d=d=max{c, d}
Лемма 3. Для всех r = 1, 2, …, n
= max{ – , 
– 
, …, A1}. (12)
Доказательство. Воспользуемся индукцией по r. Пусть формула (12) верна при некотором r. Докажем, что она верна при r+1. Положив
a = Xr+1, c = 
– 
, d = , (13)
имеем, в силу (10) при r+1, a = max{0, c–d}, откуда, в силу (11) a + d = max{c, d}. С учётом
(13) последнее равенство записывается как
Xr+1+ = max{ – , }
или
= max{ – , }. (14)
В правую часть (14) входит . Выразим её, по предположению индукции, формулой (12) и подставим это выражение в (14). Получим
= max{ – , max{ – , – , …, A1}} =
max{ – , – , – , …, A1}. (15)
Второе равенство в (15) следует из очевидного соотношения
max{a, max{b1, …, bp}} = max{a, b1, …, bp}.
Оставляя в цепочке равенств (15) только первый и последний члены, получаем
= max{ – , – , …, A1}. (16)
Формула (16) отличается от формулы (12) заменой r на r+1. Базис индукции при r=1 верен в силу (8), что завершает доказательство леммы
Положив для всех r = 1, …, n
Dr = ,
Lr = – , (17)
запишем формулу (12) при r = n в виде
Dn = 
. (18)
Величина Dn по построению – это как раз та величина, которую надо минимизировать.
Все приведенные в доказательстве утверждения 1 формулы верны для любого порядка обработ-ки деталей. Рассмотрим теперь, наряду с исходным порядком P1, …, Pk, Pk+1, …, Pn, новый порядок P1, …, Pk+1, Pk, …, Pn, отличающийся от него перестановкой двух соседних деталей (транспозицией): Pk и Pk+1. Величины, относящиеся к этому новому порядку, снабдим штрихом.
Из формулы (17) сразу видно, 
что 
= 
при r k, k+1 (поскольку в них входят только суммы длительностей). Поэтому в силу (18) неравенство
< 
(19)
влечёт неравенство
max{Lk , Lk+1} < max{ 
, 
}. (20)
Лемма 4. Неравенство (20) эквивалентно неравенству (2a):
min{Ak, Bk+1} < min{Ak+1, Bk}. (2a)
Доказательство.По определению величин Lr (см. формулу (17)) при r = k имеем
max{Lk , Lk+1} = max{ 
– 
, 
– 
}, (21)
max{ , } = max{ 
– , – 
}. (21’)
Прибавим к обеим частям равенств (21) и (21’ ) одно и то же выражение Q = – . Полу-чим после простых преобразований
Q + max{Lk , Lk+1} = max{Q+Lk , Q+Lk+1}= max{– Ak+1, – Bk}= – min{Ak+1, Bk}, (22)
Q + max{ , }= max{Q+ , Q+ }= max{– Ak, – Bk+1}= – min{Ak, Bk+1}. (22’)
В силу формул (21) и (22) неравенство (20) эквивалентно неравенству
– min{Ak+1, Bk} < – min{Ak, Bk+1}, которое эквивалентно требуемому неравенству (2а)
Поскольку (19) влечёт (20), то в силу леммы 4 (19) влечёт (2a). Но (19) означает, что старый порядок лучше нового, что завершает доказательство утверждения 1