Алгоритм с двумя станками

Алгоритм с двумя станками

Задача Джонсона с двумя станками

Имеется n деталей и два станка. Каждая деталь должна сначала пройти обработку на первом станке, затем — на втором. При этом i -ая деталь обрабатывается на первом станке за a i времени, а на втором — за b i времени. Каждый станок в каждый момент времени может работать только с одной деталью.

Требуется составить такой порядок подачи деталей на станки, чтобы итоговое время обработки всех деталей было бы минимальным.

Решение задачи описано на e-maxx.ru

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

Опуская доказательства: в решении предлагается отсортировать пары чисел (a i, b i) следующим компаратором:

Мы определили некоторое бинарное отношение на множестве пар чисел. Внимание, вопрос: почему этим отношением можно пользоваться как компаратором?

Сначала о плюсах: Это отношение действительно транзитивно.

Давайте это докажем (если вы хотите минусов, эту часть можно пропустить).

Из этого следует a 1 2, a 1 1 . Из нашего предположения получаем, что

А вот теперь о минусах. Очевидно, это отношение не обладает свойством антисимметричности. Более того: Давайте на множестве пар чисел введем отношение «быть равными» в том смысле, что ни одна из пар не больше другой. . Это отношение транзитивным не является!

Пример: (2, 3) = (1, 1) = (4, 5) , но (2, 3) .

Давайте определим отсортированную последовательность так: Последовательность отсортирована по неубыванию, если для любых , т.е. никогда больший элемент не идет перед меньшим.

Построим ориентированный граф так: Вершины — элементы последовательности, дуга из i в j соответствует p i j . Тогда наше определение отсортированной последовательности совпадает с топологической сортировкой этого графа.

Мы показали, что ориентированных циклов в этом графе нет, а значит на нем есть топологическая сортировка, т.е. нашу последовательность можно отсортировать.

Но если мы просто передадим наш компаратор в пузырьковую сортировку, то последовательность не будет отсортирована.

Думаю, что для остальных сортировок тоже несложно будет подобрать соответствующий пример (возможно, он будет зависеть от конкретной реализации, потому что все такие контрпримеры завязаны на обработке «равных» элементов).

Таким образом, доказательство на e-maxx не верно.

Источник

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

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

  • Шаг №1
  • Шаг №2
  • Видеоинструкция

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

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

  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) Пример 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)

Источник

Читайте также:  Ремонт станка сдм 2500
Оцените статью