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

1. Рассматриваются интервалы времени и , определяется величина .

2. Если эта величина находится в столбце , то -ю деталь помещаем на первый станок в первую очередь. Если эта величина находится в столбце , то -я деталь занимает последнее место на первом станке.

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

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

Рисунок 6.2 – Начальное расписание

По графику видно, что начальный порядок обработки деталей допускает простои второго станка (суммарное время простоев 8 единиц), длина производственного цикла равна 30 единицам времени.

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

Продолжаем процедуру поиска. Среди не вычеркнутых элементов ищем . После выбора второй детали минимальное время равно 3, и оно соответствует и . Мы можем выбрать любую деталь, поэтому произвольно выбираем , т. е. помещаем на первое место деталь 1. Теперь минимальное время соответствует . Следовательно, деталь 4 ставится на предпоследнее место.

Следующая минимальная величина равна 4 ( и ). Можем назначить 2-е место на первом станке для детали 3 и 3-е место для детали 5.

Полученная последовательность обработки деталей на двух станка =(1, 3, 5, 4, 2) будет оптимальной.

Эта последовательность представлена диаграммой Ганта на рис.6.3.

Рисунок 6.3 – Оптимальное расписание

Из рис. 6. 3 видно, что время обработки всех деталей равно 28 единиц и суммарное время простоев - 6 единиц.

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

или .

Тогда осуществляется поиск оптимальных строк по суммам

Пример. Пусть операции над деталями задаются сроками выполнения :

Условие , например, выполняется. Таким образом, мы имеем:

и алгоритм Джонсона позволяет выбрать =(4, 2, 3, 1, 5).

Задания для самостоятельной работы

Найти решение задачи Джонсона для двух последовательных приборов. Длительности обслуживания приборами А и В приведены в таблице.

ЗАДАЧА О НАЗНАЧЕНИЯХ

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

В качестве примера простейшей задачи упорядочения рассмотрим так называемую задачу Беллмана-Джонсона n ×2.

Пусть на двух станках (А и В ) необходимо обработать n разных деталей с номерами. Пусть даны нормы времени a i и b i обработки детали i на станкахА и В соответственно и пусть задано, что маршрут обработки для всех деталей жесткий: c начало деталь обрабатывается на станке А, затем на станке В . При этом:

1) для каждой детали обработка на станкеВ может начинаться не раньше, чем окончится ее обработка на станке А ;

2) на каждом станке одновременно может обрабатываться не более одной детали;

3) начавшаяся операция не прерывается до полного ее завершения.

Пусть конкретные значения величин a i и b i для случая n = 5 следующие (табл.8.1).

Будем запускать детали в производство в порядке их номеров и определим при помощи линейных диаграмм (графика Ганта) общее время Т полной обработки всех деталей (рис.8.1).

Таблица 8.1

Рис.8.1 График Ганта обработки пяти деталей на двух станках

Как видно из графика, пока станок A будет обрабатывать первую деталь, станок B будет простаивать, причем величина простоя x 1 = a 1 = 4 . Так как a 1 + a 2 >x 1 + b 1 , то и во время обработки второй детали на станке Астанок В не будет загружен полностью. Время простоя x 2 = a 1 + a 2 – x 1 – b 1 = 4 + 30 - 4 – 1 = 29. Так как a 1 + а 2 + а 3 >x 1 + b 1 + x 2 + b 2 , то будет иметь место еще один простой станка В, причем x 3 = a 1 +a 2 +a 3 – x 1 – b 1 – x 2 – b 2 = 4 + 30 + 6 - 4 – 1 – 29 – 4 = 2. Так как a 1 + а 2 + а 3 + а 4 <x 1 + b 1 + x 2 + b 2 + x 3 + b 3 , то очередного возможного простоя станка В не будет, т.е. x 4 = 0. Аналогично получаем, что и x 5 = 0. Тогда общее время простоев станка В будет равно X = x 1 + x 2 + x 3 + x 4 + x 5 = 4 + 29 + 2 + 0 + 0 = 35, а общее время полной обработки всех деталей T = T B + X = b 1 + b 2 + b 3 + b 4 + b 5 + X = 1 + 4 + 30 + 5 + 3 + 35 = 43 + 35 + = 78.

Нетрудно заметить, что величина простоев X (и, следовательно, общее время Т) будет зависеть от последовательности, в которой детали обрабатываются. Например, если мы вместо последовательности 1-2-3-4-5 воспользуемся обратной последовательностью 5-4-3-2-1, то получим x 1 = 2, x 2 = 1, x 3 = 1, x 4 = x 5 = 0, откуда будет следовать, что X = 4 и T = 43 + 4 = 47. Как видим, получили существенный выигрыш: величина простоев станка В уменьшилась чуть ли не в 9 раз, а общее время обработки чуть ли не на 40 %.

nх 2

Джонсон в 1963 г. предложил алгоритм построения оптимальной последовательности обработки для случая n деталей и двух станков с жесткими и одинаковыми маршрутами обработки, когда в качестве критерия оптимальности выбирается минимум общей продолжительности обработки, а начальные и конечные директивные сроки и таковы, что накладываемые этими сроками ограничения можно не учитывать.

АЛГОРИТМ ДЖОНСОНА

1. Найти наименьший элемент в таблице значений {a i ,b i }.

2. Если этот наименьший элемент принадлежит столбцу значений a i поставить на первое свободное место последовательности (в первый раз это будет первое место, во второй – второе и т.д.); если же наименьший элемент принадлежит столбцу значений b i , то деталь с соответствующим номером i поставить на последнее свободное место последовательности (в первый раз это будет n -е место, во второй – (n - 1) и т.д.); если одновременно найдется несколько одинаковых наименьших элементов, то среди них можно выбирать любой, принять за наименьший и поступать так, как описано в начале пункта 2 алгоритма.

3. Из таблицы значений {a i ,b i } вычеркнуть строку, соответствующую выбранному наименьшему элементу, и проверить, остались ли еще не вычеркнутые строки.

4. Если не вычеркнутые строки еще остались, то рассматривать их как новую таблицу значений {a i ,b i } и перейти к пункту 1 алгоритма; если вычеркнуты все строки таблицы, то это означает, что алгоритм свою работу закончил.

Применим алгоритм Джонсона к таблице примера, рассмотренного в первом параграфе данной главы.

1. Просматривая таблицу значений {a i ,b i } находим, что минимальным является b 1 =1.

2.Это означает, что деталь с номером i * = 1 в оптимальной последовательности должна быть последней, т.е. иметь номер i нов = n =5.

3. Вычеркиваем из таблицы первую строку.

4. Так как еще остались не вычеркнутые строки, то возвращаемся к первому пункту алгоритма Джонсона.

5. Находим, что минимальным элементом остаточной таблицы является a 5 = 2.

6. Ставим деталь с номером i * = 5 на первое место оптимальной последовательности, т.е. присваиваем номеру i * значение 1.

7. Вычеркиваем из таблицы пятую строку.

8. Так как еще остались не вычеркнутые строки, то опять возвращаемся к первому пункту алгоритма.

9. Находим, что минимальными являются a 4 = b 2 = 4.

10. Выбираем деталь, например, с номером i * = 4 и помещаем ее в первое свободное место оптимальной последовательности, т.е. присваиваем номеру i нов значение 2.

11. Вычеркиваем четвертую строку.

12. Возвращаемся к началу.

13. Находим, что (a i ,b i) = b 2 = 4.

14. Присваиваем детали с номером i * = 2 номер i нов = n – 1 = 4.

15. Вычеркиваем вторую строку.

16. Возвращаемся к таблице, содержащей еще одну строку. Конечно, для оставшейся не вычеркнутой детали осталось всего одно свободное место в оптимальной последовательности с номером i нов = 3, поэтому решение уже получено – оптимальная последовательность в прежних номерах деталей буде иметь вид 5,4,3,2,1. Это же решение мы получили бы, если бы продолжили алгоритм Джонсона до конца (что сделала бы ЭВМ, работая по программе, реализующей алгоритм Джонсона). Действительно, проверив оставшуюся строку, ЭВМ обнаружила бы, что min (a i ,b i) = a 3 = 6, и поместила бы деталь с номером i * = 3 в первое свободное место, т.е. присвоила бы ей номер 3. Вычеркнув третью строку таблицы, ЭВМ обнаружила бы, что не вычеркнутых строк больше не осталось, и вышла бы на конец алгоритма – печать результата и останов работы программы.

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

На это сомнение можно ответить, что, согласно правилу Джонсона, в этом случае порядок следования (и, следовательно, порядок выбора деталей) безразличен, так как если min (a j +1,b j) = min (a j ,b j +1) = a j +1 = a j , то X (S ") = X (S ”) независимо от того, какое соотношение между b j и b j +1. Аналогично получаем, что при min (a j +1,b j) = min (a j ,b j +1) = b j = b j +1 будет иметь место X (S ’) = X (S ”) независимо от значений a j и a j +1.

Проиллюстрируем сказанное на примере задачи n × 2, заданной при помощи таблицы 8.2.

Таблица 8.2 Таблица 8.3 Таблица 8.4 Таблица 8.5

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

Общая формула для расчета простоя

(8.1)

, (8.2)

где

Найдем для этих последовательностей

Для последовательности, соответствующей табл. 8.3:

X = max (8; 5; 7; 10;10) = 10.

Для последовательности, соответствующей табл. 8.4:

X = max (8; 7; 7; 10;10) = 10.

Для последовательности, соответствующей табл. 8.5:

X = max (6; 8; 7; 10;10) = 10.

Сумма простоев во всех трех последовательностях получилась одинаковой (Х = 10). Различие лишь в распределении простоев: в первом случае x 1 = 8, x 2 = 2; во втором x 1 = 8, x 2 = 2, в третьем x 1 = 6, x 2 = 2, x 4 = 2.

Это может быть учтено при планировании заполнения простоев фоновой работой.

Алгоритм Джонсона для задачи n × 2 может быть модифицирован и сведен к следующему:

1. Находим все детали, для которых a i ≤ b i и упорядочиваем их в порядке возрастания a i .

2. Оставшиеся детали, для которых a i >b i , упорядочиваем в порядке убывания b i .

3. Подписываем список деталей второй группы под списком деталей первой группы, т.е. обрабатываем сначала детали первой группы в порядке возрастания a i , затем детали второй группы в порядке убывания b i .

АЛГОРИТМ ДЖОНСОНА ДЛЯ РЕШЕНИЯ ЗАДАЧИ УПОРЯДОЧЕНИЯ n ×3

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

Обозначим станки черезА , В , С , нормы времени обработки детали i соответственно через a i , b i и c i , простои станка В через x i , станка С – через y i . График Ганта в этом случае будет иметь следующий вид (рис.8.2)

Рис.8.2 График Ганта для случая n × 3

Решение задачи n ´3 при выполнении условия сводится к решению задачи n ´2, если только интерпретировать:

· a i + b i = d i - как норму времени обработки детали i на некотором станке D i ,

· b i + c i = e i как норму времени обработки детали i на некотором станке E i .

Отсюда получаем следующий алгоритм решения задачи упорядочения при n ´3 в случае выполнения условия .

Алгоритм

1. Производим построчное сложение элементов первого и второго столбцов таблицы: d i = a i + b i .

2. Производим сложение второго и третьего столбцов таблицы: e i = b i + c i .

3. К новой таблице n ´2 применяем алгоритм Джонсона, используемый для задачи упорядочения n ´2.

Тема: Решение задачи упорядочения обработки n деталей на m cтанках (m =2 и m =3) с использованием алгоритма Джонсона

Задание 1. Решение задачи упорядочения с n деталями и 2-я станками

Изучить по изложенному выше теоретическому материалу:

· математическую модель задачи упорядочения n деталей на 2-х станках;

· вывод правила Джонсона для данной задачи;

· алгоритм Джонсона для данной задачи.

Пример 1.

Определим простой X последнего станка B по формуле:

,

где

Для этого определим значения функции K (1), K (2), K (3), K (4), K (5). Их удобно вычислять по рекуррентной формуле:

K (1) = a

K(i) =K(i –1) +a i –b i - 1 ,i = 2,3,4,5 .

K (1) = 9, K (2) = 12, K (3) = 14, K (4) = 13, K (5) = 9. Найдем простой X 2-го станка, как максимум из полученных значений:

X = max (9,12,14,13,9) = 14.

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

Используя алгоритм Джонсона, найдем оптимальную последовательность: 4, 5, 1, 2, 3. Преобразуем исходную таблицу в соответствии с найденной последовательностью

Как и для исходной последовательности, найдем прострой 2-го станка.

K (1) = 2,K (2) = K (1) + 3 - 7 = -2, K (3) = K (2) + 9 - 6 = 1,

K (4) = K (3) + 6 - 3 =4, K (5) =K (4) + 4 - 2 = 6 .

X = max (2, -2,1,4,6) = 6.

Построим график Ганта для оптимальной последовательности запуска деталей в обработку:

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

Варианты для задания №1

Задание 2 . Решение задачи упорядочения с n деталями и 3-я станками

1) математическую модель задачи упорядоченияn деталей на 3-х станках;

2) условие существования решения данной задачи и следствия из него;

3) вывод правила Джонсона для данной задачи;

4)алгоритм Джонсона для данной задачи.

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

Определим, удовлетворяют ли данные таблицы одному из условий:

Первое условие выполняется:
, поэтому можно свести данную задачу к задаче для двух некоторых станков D , E формулам d i . = a i + b i , e i = b i + с i:

Используя алгоритм Джонсона, определим оптимальную последовательность для полученной задачи: 4, 5, 3, 1, 2.

Теперь определим простои Y последнего станка C для исходной и оптимальной последовательностей. Для этого воспользуемся формулой

,

где
,

Для этого определим значения сумм функций

K (1) + H (1), K (2) + H (2), K (3) + H (3), K (4) + H (4), K (5) + H (5) .

Их удобно вычислять по рекуррентной формуле:

K (1) + H (1)=a 1 +b 1 ,

K (i ) + H (i ) = K (i -1) + H(i -1) +a i – b i-1 +b i – c i-1 ,i = 2,3,4,5 .

Используя эту формулу, получим:

K (1) + H (1) = 12,K (2) + H (2) = 13, K (3) + H (3) = 21, K (4) + H (4) = 20, K (5) + H (5) = 19.

Найдем простой Y 3-го станка, как максимум из полученных значений:

Y =max (12,13,21,20,19) = 21.

Время окончания обработки всех деталей на двух станках равно

Построим график Ганта для исходной последовательности:

Как видно из графика, время окончания обработки всех деталей на трех станках совпадает с расчетным и равно 54.

Используя найденную оптимальную последовательность: 4, 5, 3, 1, 2 из задачи для двух станков, переставим.

Преобразуем исходную таблицу в соответствии с найденной последовательностью

Здесь нумерация в таблице идет по порядку для удобства использования формул. Как и для исходной последовательности, найдем из таблицы прострой 3-го станка.

K (1) + H (1) = 11, K (2) +H (2) = 10, K (3) + H (3) = 7, K (4) + H (4) = 7,K (5) + H (5) = 8 .

Y= max(11,10,7,7,8) = 11.

Время окончания обработки всех деталей на двух станках в порядке оптимальной последовательности равно

Построим график Ганта для оптимальной последовательности:

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

Варианты для задания №2

Вопросы к лабораторной работе №1

1. Какие показатели производственного процесса можно выделить при решении задачи упорядочения?

2. В чем состоит задача упорядочения, исследованная Джонсоном (задача Джонсона)?

3. Что является целевой функцией (оптимизируемым показателем) и оптимизирующей переменной в задаче Джонсона?

4. Каким образом получается алгоритм Джонсона?

5. В чем суть алгоритма Джонсона?

6. Из каких величин состоит совокупная длительность производственного цикла (конечное время обработки последней детали на последнем станке)?

7. Как получить математическую модель задачи Джонсона для 2-х станков?

8. Как получить математическую модель задачи Джонсона для 3-х станков?

9. Какие имеются способы определения простоя 2-го станка в задаче Джонсона?

10. Какие имеются способы определения простоя 3-го станка в задаче Джонсона?

11. Каким образом решается задача Джонсона для 3-х станков?

Исходные данные и искомые величины при составлении расписаний. Понятие регулярного критерия.

Постановка задачи в ТР начинается с описания система устройств и множества работ. Для простого процесса обслуживания система обслуживающих устройств(ОУ) описывается их числом, то есть есть m устройств, n работ. F[i] – работа, а i номер работы в расписании. Исходные данные:

ti – длительность выполнения операции, то есть длина интервала времени, требуемого iым устройством для выполнения работы(аргумент)

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

Система состоит из 1 обслуживающего устройства. На входе стоят n работ. Время выполнения каждой работы известно. Надо составить расписание, минимизирующее среднее время пребывания работы в системе, под которым будем понимать величину, состоящую из:

Время ожидания

Время обслуживания

3. Минимизация среднего времени пребывания работ в системе n|1.

Соотношение между длительностью прохождения и средним числом работ в системе.

5. Составление расписаний в случае критерия с учетом веса в системе n|1.

Составление расписаний в соответствии с плановым сроком. Теорема Джексона.

7. Расписания с упорядочением работ в виде цепочек, которые не могут разрываться в системах n|1.

Пусть есть n работ, которые объединены в k цепочек. Цепочки разрывать нельзя при составлении расписаний, то есть, если началась выполняться первая работа из цепочки, то должны выполняться остальные работы в цепочке. Надо составить расписание, минимизирующее время пребываний работ.

ti – время выполнения цепочки

Fi – время пребывания в системе цепочки

hj – расстояние между последней работой в цепочке и jой

Fij = Fi – hij

Нужно минимизировать:

Так как hij не зависит от расписания, то сумма по hij тоже не зависит. Чтобы (*) минимизировать надо минимизировать:

В расписании, минимизирующем среднее время пребывания в том случае, когда цепочки сгруппированы и их разрывать нельзя:

8. Составление расписаний в системах n|1 при заданном отношении предшествования (цепочки, которые можно разрывать).

9. Расписания для систем конвейерного типа. Теорема о порядке выполнения на двух первых машинах. Теорема о порядке выполнения на двух первых и двух последних машинах в системе n|m|F|F max .

Задача Джонсона. Теорема Джонсона. Алгоритм, основанный на теореме Джонсона.

Алгоритм:

1) Выбрать работу с мин длительностью прохождения на устройстве А

2) Выбрать работу с мин длительностью прохождения на устройстве В

3) Если А

4) Вынесенную в итоговое расписание работуиз списка доступных вычеркнуть

5) Повторять 1-4 до тех пор, пока все работы не выйдут из списка доступных(то есть будет готовое расписание)

11. Оптимальные расписания для системы n|m|F|F max .

Но если m>3, то составление расписания сложно. Схемы:

Полный перебор(из-за факториального роста вычислительной сложности не применяется)

Динамическое программирование(путём разбиения сложных задач на более простые подзадачи)

Метод ветвей и границ

Метод ветвей и границ – метод решения задач дискретной оптимизации, основанный на вычислении оценок и ветвлений. Это пошаговая процедура конструирования расписаний:

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

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

13. Параллельные приборы. Система заданий с древовидной структурой.

Есть система задач, причем:

В этой системе определено отношение предшествования(работа может выполняться только если выполнена предшествующая)

Время выполнения каждой работы одинаково и равно единичке

В определенный момент времени: одни работы готовы(предшественники выполнены) и не готовы(иначе).

Для решения целесообразно использовать уровневую стратегию:

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

Готовое расписание

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

Рассмотрим участок с двумя агрегатами. Совокупность деталей должна последовательно пройти обработку на первом агрегате, а потом на втором. Между агрегатами отсутствует склад, поэтому занятость второго агрегата задерживает освобождение первого. Требуется выбрать очередность обработки деталей, обеспечивающую меньшее суммарное время занятости участка. Это время рассчитывается от момента начала обработки первой детали на первом агрегате до окончания обработки последней детали на втором агрегате.

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

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

Каждое из вышеописанных обобщений алгоритма Джонсона в определенных условиях имеет свои преимущества и свои недостатки. Каждое из этих правил в определенной степени логично. Применение первого из них способствует скорейшему вовлечению в обработку второго станка. Второе правило позволяет уменьшить конечный простой первого станка. Третье правило способствует наиболее быстрому "проскакиванию" к концу технологической линии тех деталей, для которых обработка на первом станке занимает меньшее время, с тем, чтобы освободить первый станок деталям, для которых он является узким местом. К сожалению, эти правила не совместимы друг с другом: последовательность обработки, найденная с использованием одного из них, не соответствует последовательности, полученной по другим правилам.

Пример решения задачи методом Джонсона Время обработки, мин Станок деталь 1 2 3 4 5 Суммарное время обработки 2 5 10 1 5 8 7 5 1 10 3 5 10 2 3 7 7 4 4 5 9 3 1 10 7 4 8 3 1 4 1 2 9 8 2 8 9 2 6 11 25 29 23 27 30 20 22 36

В результате решения задачи по четырем выше указанным рекомендациям получаем такой порядок запуска деталей в обработку: – по первой рекомендации: 7 -1 -3 -6 -2 -4 -8 -5; – по второй рекомендации: 2 -8 -5 -4 -6 -3 -7 -1; – по третьей рекомендации: 2 -8 -5 -7 -3 -1 -6 -4; – по четвертой рекомендации: 8 -5 -2 -4 -1 -3 -7 -6. Примечание. Если по какой-либо рекомендации две, или больше деталей оказываются равноценными, то для определения их приоритетов следует воспользоваться какой-либо другой рекомендацией. Например, по рекомендациям вторая и восьмая детали равноценны, но по первой рекомендации целесообразно в обработку запустить сначала вторую деталь, т. к. время ее обработки на первом станке меньше, чем у восьмой детали.

Для каждой детали найдем сумму мест во всех полученных решениях: первая деталь: (2 + 8 + 6 + 5) = 21; вторая деталь: (5 + 1 + 3) = 10; третья деталь: (3 + 6 + 5 + 6) = 20; четвертая деталь: (6 + 4 + 8 + 4) = 22; пятая деталь: (8 + 3 + 2) = 16; шестая деталь: (4 + 5 + 7 + 8) = 24; седьмая деталь: (1 + 7 + 4 + 7) = 19; восьмая деталь: (7 + 2 + 1) = 12.

Расположим детали в порядке возрастания суммы мест: 2– 8– 5– 7– 3– 1– 3– 6. Это и является новым решением. При решении конкретных задач для трех и более станков рекомендуется проанализировать результаты, полученные по каждому из этих правил, и в качестве окончательного варианта выбрать ту последовательность, которая обеспечивает минимум суммарного времени обработки.