Задача Джонсона. Пример решения
Copyright © Semestr.RU

Рассмотрим задачу последовательной обработки на двух машинах N различных деталей, если известно время Ai и Bi обработки i-й детали на соответствующих машинах. Очевидно, что первая машина будет загружена полностью, но вторая может периодически оказываться в состоянии простоя. Попытаемся найти порядок обработки, минимизирующий время простоя второй машины и тем самым сокращающий общее время обработки деталей.
Если обозначить через Xi - время простоя в ожидании i-й детали, то:
A1
X1 + X2 = max(A1 + A2 - B1, A1)
X1 + X2 + X3 = max(A1 + A2 +A3 - B1 - B2, A1 + A2 - B1, A1)
∑Xi = max(∑Ai - ∑Bi)
Если обозначить через F(t, Ak, Bk/k=1..N) - суммарное время обработки N деталей при условии, что вторая машина включается с задержкой t и используется оптимальный порядок обработки, то c учетом принципа оптимальности (независимо от выбора начальной детали порядок выбора последующих должен быть оптимальным) имеем:
F(t, Ak, Bk/k = 1..N) = min(Ai + F(Bi + max(t-Ai,0),Ak,Bk=1..N,k≠i)) 
Если после i-й детали при оптимальном порядке обрабатывается j-я, то:
F(t, Ak, Bk/k=1..N) = Ai + Aj + F(tij, Ak, Bk/k=1..N; k≠i,j)
где
tij = Bi + max[Bj + max(t-Aj,0) - Aj,0] = Bi + Bj - Ai - Aj + max[t, max(t,max(Aj - Ai - Bj,Aj))]
Если max(Ai + Aj - Bi,Ai) < max(Aj + Ai - Bj, Aj), то сначала разумнее обрабатывать j-ю деталь.
Можно показать, что указанное условие необходимости перестановки эквивалентно условию:
min(Aj, Bi) < min(Ai, Bj)
Соответственно ищем среди всех значений Ai и Bi наименьшее. Если найденное значение совпадает с некоторым Ai, то i-ю деталь ставим на обработку первой; если оно совпадает с некоторым Bi, то последней. Эту процедуру повторяем для всех остальных деталей.
Пример. Пусть информация о времени обработки задана таблицей:
2	3	
8	3	
4	6	
9	5	
6	8	
9	7	

Шаг № 1.
Минимальное из значений соответствует A1: 1-ая деталь обрабатывается первой.
2	3	
-	-	
-	-	
-	-	
-	-	
-	-	

Шаг № 2.
Минимальное из значений равно 3 и соответствует B2: 2-ая деталь обрабатывается последней.
2	3	
-	-	
-	-	
-	-	
-	-	
8	3	

Шаг № 3.
Минимальное из значений соответствует A3: 3-ая деталь обрабатывается первой.
2	3	
4	6	
-	-	
-	-	
-	-	
8	3	

Шаг № 4.
Минимальное из значений равно 5 и соответствует B4: 4-ая деталь обрабатывается последней.
2	3	
4	6	
-	-	
-	-	
9	5	
8	3	

Шаг № 5.
Минимальное из значений соответствует A5: 5-ая деталь обрабатывается первой.
2	3	
4	6	
6	8	
-	-	
9	5	
8	3	

Шаг № 6.
Минимальное из значений равно 7 и соответствует B6: 6-ая деталь обрабатывается последней.
2	3	
4	6	
6	8	
9	7	
9	5	
8	3	

В итоге упорядоченная информация принимает вид:
2	3	
4	6	
6	8	
9	7	
9	5	
8	3	

Время простоя второй машины при первичном порядке равно:
max(2 , 2 + 8  - 3 , 2 + 8 + 4  - 3 - 3 , 2 + 8 + 4 + 9  - 3 - 3 - 6 , 2 + 8 + 4 + 9 + 6  - 3 - 3 - 6 - 5 , 2 + 8 + 4 + 9 + 6 + 9  - 3 - 3 - 6 - 5 - 8 ) = max(2, 7, 8, 11, 12, 13) = 13
Время простоя при оптимальной перестановке равно:
max(2 , 2 + 4  - 3 , 2 + 4 + 6  - 3 - 6 , 2 + 4 + 6 + 9  - 3 - 6 - 8 , 2 + 4 + 6 + 9 + 9  - 3 - 6 - 8 - 7 , 2 + 4 + 6 + 9 + 9 + 8  - 3 - 6 - 8 - 7 - 5 ) = max(2, 3, 3, 4, 6, 9) = 9

Решение было получено и оформлено с помощью сервиса:
Задача Джонсона