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

Задание. Используя исходные данные, представленные в таблице 4, выполнить следующие виды работ:
  1. Изобразить графически процесс обработки деталей на двух станках для следующей произвольно выбранной очередности запуска деталей в обработку: А?Б?В?Г?Д?Е. Определить длительность совокупного производственного цикла, время простоя станков и время пролеживания деталей
  2. Решить задачу Джонсона для частного варианта ее постановки, когда число станков n=2.
  3. Изобразить графически расписание работы технологической линии для найденной оптимальной очередности запуска деталей в обработку. Определить суммарное время простоя каждого станка и суммарное время пролеживания деталей перед каждым станком.
  4. Рассчитать длительность совокупного производственного цикла для найденной оптимальной очередности запуска деталей в обработку и сравнить ее с величиной, полученной графическим способом.
  5. Доказать оптимальность полученного решения.
  6. Оценить эффективность полученного решения.
  7. Сформировать экономико-математические модели задачи Джонсона для ее частной и общей постановки.

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

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

2 3
- -
- -
- -
- -
- -

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

2 3
- -
- -
- -
- -
8 3

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

2 3
4 6
- -
- -
- -
8 3

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

2 3
4 6
- -
- -
9 5
8 3

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

2 3
4 6
6 8
- -
9 5
8 3

Минимальное из значений равно 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
doc:xml
загрузка...