Задачи упорядочения в общем случае представляют собой задачи выбора порядка обслуживания, оптимизирующего какой-либо существенный показатель качества функционирования системы. К задачам упорядочения относятся, например, задачи выбора дисциплины обслуживания в системе массового обслуживания, задачи составления оптимальных расписаний и т.д.
В качестве примера простейшей задачи упорядочения рассмотрим так называемую задачу Беллмана-Джонсона n ×2.
Пусть на двух станках (А и В ) необходимо обработать n разных деталей с номерами. Пусть даны нормы времени a i и b i обработки детали i на станкахА и В соответственно и пусть задано, что маршрут обработки для всех деталей жесткий: c начало деталь обрабатывается на станке А, затем на станке В . При этом:
1) для каждой детали обработка на станкеВ может начинаться не раньше, чем окончится ее обработка на станке А ;
2) на каждом станке одновременно может обрабатываться не более одной детали;
3) начавшаяся операция не прерывается до полного ее завершения.
Пусть конкретные значения величин a i и b i для случая n = 5 следующие (табл.8.1).
Будем запускать детали в производство в порядке их номеров и определим при помощи линейных диаграмм (графика Ганта) общее время Т полной обработки всех деталей (рис.8.1).
Таблица 8.1
| i | a i | b i |
Рис.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.
| i | a t | bi |
| i | a t | b |
| i | a t | b |
| i | a i | b |
Таблица 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.
| i | a i | b i |
Определим простой 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. Преобразуем исходную таблицу в соответствии с найденной последовательностью
| i опт | a i | b i |
Как и для исходной последовательности, найдем прострой 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
| i | a i | b i |
| i | a i | b i |
| i | a i | b i |
| i | a i | b i |
| i | a i | b i |
| i | a i | b i |
| i | a i | b i |
| i | a i | b i |
| i | a i | b i |
| i | a i | b i |
| i | a i | b i |
| i | a i | b i |
| i | a i | b i |
| i | a i | b i |
| i | a i | b i |
Задание 2 . Решение задачи упорядочения с n деталями и 3-я станками
1) математическую модель задачи упорядоченияn деталей на 3-х станках;
2) условие существования решения данной задачи и следствия из него;
3) вывод правила Джонсона для данной задачи;
4)алгоритм Джонсона для данной задачи.
Пример 2. Пусть имеются исходные данные, приведенные в таблице:
| i | a i | b i | c i |
Определим, удовлетворяют ли данные таблицы одному из условий:
Первое условие выполняется: 
, поэтому можно свести данную задачу к задаче для двух некоторых станков D
, E
формулам d
i . = a
i + b
i , e
i = b
i + с
i:
| I | d i | e 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 из задачи для двух станков, переставим.
Преобразуем исходную таблицу в соответствии с найденной последовательностью
| i опт | a i | b i | c i |
Здесь нумерация в таблице идет по порядку для удобства использования формул. Как и для исходной последовательности, найдем из таблицы прострой 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
| i | a i | b i | c i |
| i | a i | b i | c i |
| i | a i | b i | c i |
| i | a i | b i | c i |
| i | a i | b i | c i |
| i | a i | b i | c i |
| i | a i | b i | c i |
| i | a i | b i | c i |
| i | a i | b i | c i |
| i | a i | b i | c i |
| i | a i | b i | c i |
| i | a i | b i | c i |
| i | a i | b i | c i |
| i | a i | b i | c i |
| i | a i | b i | c i |
| i | a i | b i | c i |
| i | a i | b i | c i |
| i | a i | b i | c i |
Вопросы к лабораторной работе №1
1. Какие показатели производственного процесса можно выделить при решении задачи упорядочения?
2. В чем состоит задача упорядочения, исследованная Джонсоном (задача Джонсона)?
3. Что является целевой функцией (оптимизируемым показателем) и оптимизирующей переменной в задаче Джонсона?
4. Каким образом получается алгоритм Джонсона?
5. В чем суть алгоритма Джонсона?
6. Из каких величин состоит совокупная длительность производственного цикла (конечное время обработки последней детали на последнем станке)?
7. Как получить математическую модель задачи Джонсона для 2-х станков?
8. Как получить математическую модель задачи Джонсона для 3-х станков?
9. Какие имеются способы определения простоя 2-го станка в задаче Джонсона?
10. Какие имеются способы определения простоя 3-го станка в задаче Джонсона?
11. Каким образом решается задача Джонсона для 3-х станков?
Алгоритм Джонсона
Алгоритм Джонсона позволяет найти кратчайшие пути между всеми парами вершин взвешенного ориентированного графа. Данный алгоритм работает, если в графе содержатся ребра с положительным или отрицательным весом, но отсутствуют циклы с отрицательным весом.
Алгоритм
Дан граф с весовой функцией. Если веса всех ребер в графе неотрицательные, можно найти кратчайшие пути между всеми парами вершин, запустив алгоритм Дейкстры один раз для каждой вершины. Если в графе содержатся ребра с отрицательным весом, но отсутствуют циклы с отрицательным весом, можно вычислить новое множество ребер с неотрицательными весами, позволяющее воспользоваться предыдущим методом. Новое множество, состоящее из весов ребер должно удовлетворять следующим свойствам.
· Для всех ребер новый вес.
· Для всех пар вершин путь является кратчайшим путем из вершины в вершину с использованием весовой функции тогда и только тогда, когда -- также кратчайший путь из вершины в вершину с весовой функцией.
Сохранение кратчайших путей
Пусть дан взвешенный ориентированный граф с весовой функцией, и пусть -- произвольная функция, отображающая вершины на действительные числа. Для каждого ребра определим:
Пусть -- произвольный путь из вершины в вершину является кратчайшим путем с весовой функцией тогда и только тогда, когда он является кратчайшим путем с весовой функцией, то есть равенство равносильно равенству Кроме того, граф содержит цикл с отрицательным весом с использованием весовой функции тогда и только тогда, когда он содержит цикл с отрицательным весом с использованием весовой функции.
Изменение веса
1. Для данного графа создадим новый граф, где, для некоторой новой вершины, а.
2. Расширим весовую функцию таким образом, чтобы для всех вершин выполнялось равенство.
Недостатком этого алгоритма является то, что в общем случае работа алгоритма может занять значительное время. /3/
Алгоритм муравья
Главная идея алгоритма муравья (метода муравьиных колоний) состоит в моделировании поведения колонии муравьев, которые способны находить кратчайший путь от муравейника до источника пищи и приспосабливаться к изменяющимся условиям внешней среды, находя новый кратчайший путь, если старый в силу каких-либо обстоятельств оказывается недоступным. При движении муравей откладывает феромон, отмечая свой путь, и эту информацию используют другие муравьи. Таким образом, взаимодействие между агентами (муравьями) происходит посредством непрямой коммуникации. /22/
Если моделировать перемещение муравьев на некотором графе, ребра которого представляют собой пути возможного перемещения муравьев, то помимо положительной обратной связи (откладывания феромона) необходимо моделировать отрицательную обратную связь, т.е. испарение феромона. Наличие отрицательной обратной связи гарантирует, что муравьи будут искать другие пути от колонии до источника пищи, т.е. найденное локально оптимальное решение не будет единственным. Решением задачи будет наиболее обогащенный феромоном путь на ребрах графа, который является оптимальным.
Муравьиные алгоритмы позволяют получить решения многих дискретных комбинаторных задач не хуже вышеперечисленных алгоритмов. Чрезвычайно хорошие результаты муравьиной оптимизации получаются для распределенных систем, параметры которых изменяются во времени. Особенностью муравьиных алгоритмов является не-конвергентность - даже после многих итераций одновременно исследуется множество разных решений, что позволяет не застревать в локальных оптимумах. /4/
В данной работе для решения задачи коммивояжера был выбран алгоритм муравья.
Cтраница 2
Для вычислений показателей методом Джонсона составляют вариационный ряд, в каждом интервале которого изделия, достигшие предельного состояния mi; группируют после К приостановленных.
Кислотность поверхности определяли методом Джонсона путем титрования w - бутиламином образцов катализаторов, суспендированных в бензоле, применяя в качестве индикатора фенилазонафтиламин.
Значительно позднее Кори и Опползер сообщили о других примерах использования метода Джонсона. Они показали, что бутилиден - и этилидендифенилсульфураны реагируют с различными карбонильными соединениями, образуя при этом соответствующие эпоксиды с хорошим выходом / Эти авторы сообщили об отсутствии стереоселективности рассматриваемой реакции, в то время как Джонсон и Граби отмечали стереоселективное образование гронс-эпоксидов.
Наиболее распространенными методами обработки результатов незавершенных испытаний являются метод максимального правдоподобия и метод Джонсона (РТМ 37.001.006 - 74), позволяющие учесть практически всю имеющуюся информацию об отказавших и приостановленных изделиях. Процесс обработки включает в себя установление закона распределения случайной величины, определение параметров этого закона, расчет основных показателей надежности. В этой последовательности и рассмотрим основные правила обработки результатов незавершенных испытаний по указанным выше методам.
При больших объемах информации (N 50 и m / N 0 2) и сгруппированных данных применяют метод Джонсона.
Используя экспериментальные данные по теплоемкости 2-метилбутана и 2-метилпентана, опубликованные в справочной литературе, рассчитана молярная теплоемкость гомологов 2-диметилалканов по предложенной нами формуле и методом Джонсона и Хуанга.
Учитывая, что теплоемкость 2-метилбутана и 2-метилпентана экспериментально изучена , в настоящей работе с применением методов, описанных в и , вычислена молярная теплоемкость 2-метилалканов и показано, что большие расхождения, которые дает метод Джонсона и Хуанга для некоторых жидких углеводородов, обусловлены структурой молекулы.
Кеталь удаляет воду, используя ее на расщепление до спирта и ацетона. Однако, согласно некоторым данным , ни метод Джонсона и др. с использованием НС1 вместо НВг, ни последняя методика не годятся для получения н-амиловых эфиров.
Как видно из таблицы, данные авторов завышены. Это объясняется тем, что они необоснованно пользуются методом Джонсона (В. Н. Русских) для обработки последних гармоник, который справедлив только для первой гармоники.
Напомним, что первый вариант имеет строгое и эффективное решение, называемое по имени его создателя алгоритмом (методом) Джонсона. Второй вариант можно при определенных условиях также свести к решению методом Джонсона, но результат при этом будет не обязательно оптимальным. Беллман, однако оно трудоемко. Эффективная эвристическая процедура его разрешения известна под названием CDS-алгоритм. Этот алгоритм распространяет метод Джонсона на общий случай постановки задачи и обеспечивает околооптимальное решение. Существуют и другие подходы, которые используют теорию очередей и компьютерное моделирование, чтобы решить эту проблему. Но все они трудоемки и сложны и в то же время не гарантируют нахождения оптимальной последовательности.
В задаче Джонсона общее время производственного цикла зависит от порядка запуска деталей в обработку. Пусть имеется n деталей, каждая из которых должна последовательно пройти обработку сначала на первом, затем на втором станке. Предполагается заданным время t ij обработки i -й детали на j -м станке (i=1,2,...,n; j=1,2). Требуется определить такой порядок запуска деталей, при котором общая длительность их обработки на обоих станках будет минимальной.
Назначение сервиса . С помощью онлайн калькулятора можно решить задачу Джонсона для частного варианта ее постановки, когда число станков n=2 . При этом рассчитывается длительность совокупного производственного цикла для найденной оптимальной очередности запуска деталей в обработку. Результаты вычислений оформляются в отчете формата Word (Пример оформления).
ИНСТРУКЦИЯ . Для решения задачи необходимо задать количество деталей (строк).
Вставьте данные из Excel (A - первый столбец,B - второй столбец), нажмите Далее.
Правило Джонсона
Вначале детали, подлежащие обработке, условно делят на две группы. В первую группу относят детали, для которых время обработки на первом станке не превышает времени обработки на втором станке. Остальные детали образуют вторую группу. Вначале следует обрабатывать детали первой группы в порядке возрастания длительности их обработки на первом станке. Затем должны обрабатываться детали второй группы в порядке убывания времени их обработки на втором станке.Алгоритм Джонсона
- В обработку сначала запускают детали, требующие минимальное время обработки на первом станке в порядке возрастания этого времени.
- В обработку запускаются сначала детали, требующие максимальное время обработки на последнем станке в порядке убывания этого времени.
- В обработку запускаются сначала детали, у которых “узкое место” находится дальше от начала процесса обработки (“узким местом” для данной детали называется станок, на котором обработка этой деталей занимает наибольшее время).
- Обрабатываются вначале детали, у которых суммарное время обработки на всех станках максимальное в порядке убывания этого времени.
Рассмотрим задачу последовательной обработки на двух машинах N различных деталей, если известно время A i и B i обработки i
-й детали на соответствующих машинах. Очевидно, что первая машина будет загружена полностью, но вторая может периодически оказываться в состоянии простоя. Попытаемся найти порядок обработки, минимизирующий время простоя второй машины и тем самым сокращающий общее время обработки деталей.
Если обозначить через X i - время простоя в ожидании i
-й детали, то:
A 1
X 1 + X 2 = max(A 1 + A 2 - B 1 , A 1)
X 1 + X 2 + X 3 = max(A 1 + A 2 +A 3 - B 1 - B 2 , A 1 + A 2 - B 1 , A 1)
∑X i = max(∑A i - ∑B i)
Если обозначить через F(t, A k , B k /k=1..N) - суммарное время обработки N деталей при условии, что вторая машина включается с задержкой t и используется оптимальный порядок обработки, то c учетом принципа оптимальности (независимо от выбора начальной детали порядок выбора последующих должен быть оптимальным) имеем:
F(t, A k , B k /k = 1..N) = min(A i + F(B i + max(t-A i ,0),A k ,B k =1..N,k≠i))
Если после i
-й детали при оптимальном порядке обрабатывается j
-я, то:
F(t, A k , B k /k=1..N) = A i + A j + F(t ij , A k , B k /k=1..N; k≠i,j)
где
t ij = B i + max = B i + B j - A i - A j + max
Если max(A i + A j - B i ,A i) < max(A j + A i - B j , A j), то сначала разумнее обрабатывать j
-ю деталь.
Можно показать, что указанное условие необходимости перестановки эквивалентно условию:
min(A j , B i) < min(A i , B j)
Соответственно ищем среди всех значений A i и B i наименьшее. Если найденное значение совпадает с некоторым A i , то i
-ю деталь ставим на обработку первой; если оно совпадает с некоторым Bi
, то последней. Эту процедуру повторяем для всех остальных деталей.
Пример 1. Пусть информация о времени обработки задана таблицей:
Шаг № 2.
Минимальное из значений равно 3 и соответствует B 2: 2-ая деталь обрабатывается последней.
Шаг № 4.
Минимальное из значений равно 5 и соответствует B 4: 4-ая деталь обрабатывается последней.
Шаг № 6.
Минимальное из значений равно 7 и соответствует B 6: 6-ая деталь обрабатывается последней.
В итоге упорядоченная информация принимает вид:
Время простоя второй машины при первичном порядке равно:
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. Пусть информация о времени обработки задана таблицей:
Шаг № 2.
Минимальное из значений равно 3 и соответствует B 1: 1-ая деталь обрабатывается последней.
Шаг № 4.
Минимальное из значений равно 4 и соответствует B 6: 6-ая деталь обрабатывается последней.
