Доказательство центрального утверждения 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 ■