Динамическое программирование
Задачи динамического программирования: задача распределения инвестиций, задача замены оборудования, задача Джонсона
xf1(x)f2(x)f3(x)
16.345
25.267
34.34.67.8
4563
5*76.38.2
Решить онлайн
Примеры решений Задача Джонсона Симплекс метод Метод прогонки Задача замены оборудования Задача распределения инвестиций Параметры сетевой модели Задача коммивояжера Многоканальные СМО

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

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

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

Инструкция. Для решения задачи необходимо задать количество деталей (строк).
Количество строк

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

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

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

  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
Финансовый анализ онлайн
Анализ и диагностика финансово-хозяйственной деятельности предприятия:
· Оценка имущественного положения
· Анализ ликвидности и платежеспособности
· Анализ финансовой устойчивости
· Анализ рентабельности и оборачиваемости
· Анализ движения денежных средств
· Анализ финансовых результатов и многое другое
Подробнее
Аннуитетные платежи онлайн
Расчет аннуитетных платежей по схеме постнумерандо и пренумерандо с помощью удобного калькулятора.
Аннуитетные платежи онлайн
Подробнее
Профессии будущего
РБК Тренды изучили прогнозы российских и зарубежных футурологов, и составили список самых востребованных профессий в ближайшие 30 лет. Это профессии из 19 отраслей: от медицины и транспорта до культуры и космоса
Подробнее
Курсовые на заказ