Задача Джонсона

Назначение сервиса. С помощью онлайн калькулятора можно решить задачу Джонсона для частного варианта ее постановки, когда число станков n=2. При этом рассчитывается длительность совокупного производственного цикла для найденной оптимальной очередности запуска деталей в обработку. Результаты вычислений оформляются в отчете формата Word.

• Шаг №1
• Шаг №2
• Инструкция
• Оформление Word

Правило Джонсона

Алгоритм Джонсона

1. В обработку сначала запускают детали, требующие минимальное время обработки на первом станке в порядке возрастания этого времени.
2. В обработку запускаются сначала детали, требующие максимальное время обработки на последнем станке в порядке убывания этого времени.
3. В обработку запускаются сначала детали, у которых “узкое место” находится дальше от начала процесса обработки (“узким местом” для данной детали называется станок, на котором обработка этой деталей занимает наибольшее время).
4. Обрабатываются вначале детали, у которых суммарное время обработки на всех станках максимальное в порядке убывания этого времени.

Примеры

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

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

Время простоя второй машины при первичном порядке равно:
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

Пример №2. Используя исходные данные, представленные в таблице 4, выполнить следующие виды работ:

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

Решение.
Рассмотрим задачу последовательной обработки на двух машинах N различных деталей, если известно время A_i и B_i обработки i-й детали на соответствующих машинах. Очевидно, что первая машина будет загружена полностью, но вторая может периодически оказываться в состоянии простоя. Попытаемся найти порядок обработки, минимизирующий время простоя второй машины и тем самым сокращающий общее время обработки деталей.
Если обозначить через X_i - время простоя в ожидании i-й детали, то:
A₁
X₁ + X₂ = max(A₁ + A₂ - B₁, A₁)
X₁ + X₂ + X₃ = max(A₁ + A₂ +A₃ - B₁ - B₂, A₁ + A₂ - B₁, A₁)
∑X_i = max(∑A_i - ∑B_i)
Если обозначить через F(t, A_k, B_k/k=1..N) - суммарное время обработки N деталей при условии, что вторая машина включается с задержкой t и используется оптимальный порядок обработки, то c учетом принципа оптимальности (независимо от выбора начальной детали порядок выбора последующих должен быть оптимальным) имеем:
F(t, A_k, B_k/k = 1..N) = min(A_i + F(B_i + max(t-A_i,0),A_k,B_k=1..N,k≠i))
Если после i-й детали при оптимальном порядке обрабатывается j-я, то:
F(t, A_k, B_k/k=1..N) = A_i + A_j + F(t_ij, A_k, B_k/k=1..N; k≠i,j)
где
t_ij = B_i + max[B_j + max(t-A_j,0) - A_j,0] = B_i + B_j - A_i - A_j + max[t, max(t,max(A_j - A_i - B_j,A_j))]
Если max(A_i + A_j - B_i,A_i) < max(A_j + A_i - B_j, A_j), то сначала разумнее обрабатывать j-ю деталь.
Можно показать, что указанное условие необходимости перестановки эквивалентно условию:
min(A_j, B_i) < min(A_i, B_j)
Соответственно ищем среди всех значений A_i и B_i наименьшее. Если найденное значение совпадает с некоторым A_i, то i-ю деталь ставим на обработку первой; если оно совпадает с некоторым Bi, то последней. Эту процедуру повторяем для всех остальных деталей.
Пример. Пусть информация о времени обработки задана таблицей: