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

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

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

Имеется 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 деталей и два станка. Каждая деталь должна сначала пройти обработку на первом станке, затем — на втором. При этом 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 деталей, каждая из которых должна последовательно пройти обработку сначала на первом, затем на втором станке. Предполагается заданным время tij обработки i-й детали на j-м станке (i=1,2. n; j=1,2). Требуется определить такой порядок запуска деталей, при котором общая длительность их обработки на обоих станках будет минимальной.

Помогите, пожалуйста, найти саму программу, очень нужна для реферата

Задача Джонсона о двух станках
Ребят привет, помогите пожалуйста сделать задачу Традиционная постановка задачи Джонсона состоит.

Обработка заготовок двумя станками.
Помогите пожалуйста.Задача по GPSS 1.Поток из 500 заготовок,поступающих с интервалом 10-20 сек.

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

задача Джонсона
Решить задачу методом поиска с возвратом, используя рекурсивный вариант

Задача Джонсона для 2х станков
Помогите решить проблему Код: private void timer_Tick(object sender, EventArgs e) < .

Задача Джонсона о двух станках
Ребят привет, помогите пожалуйста сделать задачу Традиционная постановка задачи Джонсона состоит.

Задача Джонсона для 2-х машин
Нужно написать программу реализации классического алгоритма решения задачи Джонсона для 2-х станков.

Задача Джонсона для 4 станков: нужны ссылки или литература
Подскажите необходимые ссылки или теорию, вообщем любую информацию для оптимизации по задаче.

Модель мастерской со станками
Условие: В мастерской работают несколько станков, которые обрабатывают детали одного типа. Детали.

Источник

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

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

Имеется 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)

Источник

Читайте также:  Как сделать токарный станок без токарного станка
Оцените статью