Построить график функции Точки разрыва функции Построение графика методом дифференциального исчисления Создание схемы логических элементов
Примеры решений Задача Джонсона Симплекс метод Метод прогонки
Задача замены оборудования Задача распределения инвестиций
Параметры сетевой модели Задача коммивояжера Многоканальные СМО

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

В задаче Джонсона общее время производственного цикла зависит от порядка запуска деталей в обработку. Пусть имеется n деталей, каждая из которых должна последовательно пройти обработку сначала на первом, затем на втором станке. Предполагается заданным время tij обработки i-й детали на j-м станке (i=1,2,...,n; j=1,2). Требуется определить такой порядок запуска деталей, при котором общая длительность их обработки на обоих станках будет минимальной.

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

ИНСТРУКЦИЯ. Для решения задачи необходимо задать количество деталей (строк).
Количество строк
Вставьте данные из Excel (A - первый столбец,B - второй столбец), нажмите Далее.

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

Вначале детали, подлежащие обработке, условно делят на две группы. В первую группу относят детали, для которых время обработки на первом станке не превышает времени обработки на втором станке. Остальные детали образуют вторую группу. Вначале следует обрабатывать детали первой группы в порядке возрастания длительности их обработки на первом станке. Затем должны обрабатываться детали второй группы в порядке убывания времени их обработки на втором станке.

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

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

Примеры

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

Пример №2. Используя исходные данные, представленные в таблице 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
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