Доказательство центрального утверждения 1

Обозначим через X_i время простоя 2-го станка после окончания обработки детали P_{i –1} и до нача-ла обработки детали P_i (i = 2, …, n); через X ₁ обозначим время между началом обработки 1-ой детали на станке 1 и началом её обработки на станке 2, т.е. начальный период простоя 2-го станка. По определению,

X ₁= A ₁ (8)

(т.е. 2-й станок начинает обрабатывать деталь P ₁ сразу после того, как она обработана на 1-м станке). Далее, при A ₁ + A ₂ > X ₁+ B ₁ сразу получаем, что

X ₂= A ₁ + A ₂ – B ₁ – X ₁> 0; (9)

при A ₁ + A ₂ ≤ X ₁+ B ₁ получаем, что X ₂= 0, поэтому можно написать общую для обоих случаев форму-лу X ₂= max{ A ₁ + A ₂ – B ₁, 0}. Имеет место

Лемма 1.

X_r = max{ – – , 0} (r = 1, …, n). (10)

Доказательство. + – это, по определению, время, за которое 2-й станок обрабо-тает первые (r –1) деталей; – время, за которое 1-й станок обработает первые r деталей. Мо-мент, когда 2-й станок может начать обработку детали P_r, определяется максимумом из этих двух мо-ментов времени, откуда и следует формула (10) ■

Лемма 2. Пусть a = max{0, c – d }. Тогда

a + d = max{ c, d }. (11)

Для доказательства достаточно заметить, что при c ≥ d a = c – d и а + d = с =max{ c, d }. Если же с < d, то а =0 и а + d = d =max{ c, d }■

Лемма 3. Для всех r = 1, 2, …, n

= max{ – , – , …, A ₁}. (12)

Доказательство. Воспользуемся индукцией по r. Пусть форму­ла (12) верна при некотором r. Докажем, что она верна при r +1. Положив

a = X_{r +1}, c = – , d = , (13)

имеем, в силу (10) при r +1, a = max{0, c – d }, откуда, в силу (11) a + d = max{ c, d }. С учётом

(13) последнее равенство записывается как

X_{r +1}+ = max{ – , }

или

= max{ – , }. (14)

В правую часть (14) входит . Выразим её, по предпо­ложению индукции, формулой (12) и подставим это выражение в (14). Получим

= max{ – , max{ – , – , …, A ₁}} =

max{ – , – , – , …, A ₁}. (15)

Второе равенство в (15) следует из очевидного соотношения

max{ a, max{ b ₁, …, b_p }} = max{ a, b ₁, …, b_p }.

Оставляя в цепочке равенств (15) только первый и последний члены, получаем

= max{ – , – , …, A ₁}. (16)

Формула (16) отличается от формулы (12) заменой r на r +1. Базис индукции при r =1 верен в силу (8), что завершает доказательство леммы ■

Положив для всех r = 1, …, n

D_r = ,

L_r = – , (17)

запишем формулу (12) при r = n в виде

D_n = . (18)

Величина D_n по построению – это как раз та величина, которую надо минимизировать.

Все приведенные в доказательстве утверждения 1 формулы верны для любого порядка обработ-ки деталей. Рассмотрим теперь, наряду с исходным порядком P ₁, …, P_k, P_{k +1}, …, P_n, новый порядок P ₁, …, P_{k +1}, P_k, …, P_n, отличающийся от него перестановкой двух соседних деталей (транспозицией): P_k и P_{k +1}. Величины, относящиеся к этому новому порядку, снабдим штрихом.

Из формулы (17) сразу видно, что = при r ≠ k, k +1 (поскольку в них входят только суммы длительностей). Поэтому в силу (18) неравенство

< (19)

влечёт неравенство

max{ L_k, L_{k +1}} < max{ , }. (20)

Лемма 4. Неравенство (20) эквивалентно неравенству (2a):

min{ A_k, B_{k +1}} < min{ A_{k +1}, B_k }. (2a)

Доказательство. По определению величин L_r (см. формулу (17)) при r = k имеем

max{ L_k, L_{k +1}} = max{ – , – }, (21)

max{ , } = max{ – , – }. (21 ’)

Прибавим к обеим частям равенств (21) и (21 ’) одно и то же выражение Q = – . Полу-чим после простых преобразований

Q + max{ L_k, L_{k +1}} = max{ Q + L_k, Q + L_{k +1}}= max{– A_{k +1}, – B_k }= – min{ A_{k +1}, B_k }, (22)

Q + max{ , }= max{ Q + , Q + }= max{– A_k, – B_{k +1}}= – min{ A_k, B_{k +1}}. (22 ’)

В силу формул (21) и (22) неравенство (20) эквивалентно неравенству

– min{ A_{k +1}, B_k } < – min{ A_k, B_{k+ 1}}, которое эквивалентно требуемому неравенству (2а) ■

Поскольку (19) влечёт (20), то в силу леммы 4 (19) влечёт (2a). Но (19) означает, что старый порядок лучше нового, что завершает доказательство утверждения 1 ■