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

Рассмотрим задачу последовательной обработки на двух машинах 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, то последней. Эту процедуру повторяем для всех остальных деталей.

Пример 1. Пусть информация о времени обработки задана таблицей:

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

Пример 2. Пусть информация о времени обработки задана таблицей:

6

3

8

5

4

5

4

2

5

8

8

4



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

-

-

-

-

-

-

-

-

-

-

4

2



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

-

-

-

-

-

-

-

-

6

3

4

2



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

4

5

-

-

-

-

-

-

6

3

4

2



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

4

5

-

-

-

-

8

4

6

3

4

2



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

4

5

5

8

-

-

8

4

6

3

4

2



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

4

5

5

8

8

5

8

4

6

3

4

2



В итоге упорядоченная информация принимает вид:

4

5

5

8

8

5

8

4

6

3

4

2

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

Перейти к онлайн решению своей задачи

загрузка...