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

В качестве примера простейшей задачи упорядочения рассмотрим так называемую задачу Беллмана-Джонсона 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-х станков?

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

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

8.1.1 Постановка детерминированной задачи упорядочения,

построение и исследование математической модели

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

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

Традиционная постановка задачи Джонсона состоит в следующем: требуется выбрать порядок обработки деталей (изделий), сформировать (составить) расписание работы технологической линии, обеспечивающее минимальное суммарное время выполнения всего задания, а именно за минимальное время осуществить обработку группы из т деталей, каждая из которых должна последовательно пройти обработку на каждом из п станков, образующих технологическую линию. Предполагается заданным t ij - время обработки i -ой детали (i = 1,…, m ) на j -ом станке (j =1,…,n ).

Основными ограничениями задачи являются:

1) время перехода (передачи) деталей от одного станка к другому (с одной технологической операции на другую) незначительно, и им можно пренебречь;

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

3) каждое обслуживание (обработка каждой детали на каждом станке) не может начинаться до тех пор, пока соответствующий станок (требуемый для обслуживания) еще занят обработкой предыдущей детали, то есть занят выполнением технологической операции над деталью предыдущей в очереди подач (запуска в обработку);

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

Рассматриваемая задача – одна из типичных задач оперативно-календарного планирования для машиностроительных предприятий мелкосерийного и единичного производства.

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

По математической постановке она представляет собой комбинаторную задачу на перестановки и поэтому возможно построение оптимального графика в результате полного перебора всех вариантов. Следовательно, для выявления оптимальной последовательности запуска деталей на обработку, вообще говоря, требуется полный перебор всех возможных вариантов. Однако получение решения путем прямого перебора всех возможных вариантов и с помощью компьютера становится невозможным даже при сравнительно малом числе данных (деталей, операций, станков). Это обусловлено тем, что даже если ограничиться ситуациями, когда порядок запуска на первый станок сохраняется и в дальнейшем, при поступлении деталей на последующие станки, общее число вариантов будет равно m !.

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

Так, если предположить, что в задаче поиска оптимальной очередности, в случае всего 10 деталей затрачивается всего лишь одна минута, на построение каждого варианта расписания и вычисление соответствующего ему значения функции-критерия (критерия оптимальности). Тогда нетрудно подсчитать, что при использовании метода полного перебора (число вариантов равно 10!, то есть 3 628 800 вариантов) и даже при двадцатичетырехчасовом рабочем дне эту задачу пришлось бы решать... почти семь лет. В случае же 20 деталей (число вариантов равно 20!, то есть 2,433*1018 вариантов) даже с помощью современных, быстродействующих компьютеров такая задача методом полного перебора решалась бы более 77 тысяч лет!

Если же детали различны и порядок запуска на первый станок может не сохраняется в дальнейшем, при поступлении деталей на последующие станки, то, очевидно, общее время обработки всех деталей рассматриваемой группы зависит от порядка, в котором детали запускаются на обработку на каждый станок. Следовательно, общее число возможных вариантов возрастет до огромного числа (m !) n .

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

Следовательно, чтобы разработать метод точного решения такого рода задач, необходимо предложить что-то лучшее, чем примитивный перебор всех возможных вариантов порядка (очередности) запуска.

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

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

Оставив пока в стороне вопрос об общих приемах сокращения объема перебора вариантов порядка (очередности) запуска, рассмотрим частный вариант постановки задачи Джонсона, когда число станковn =2. В этом частном случае удается установить простые приемы нахождения порядка запуска деталей, обеспечивающего наименьшую продолжительность выполнения задания (наименьшую длительность расписания), то есть минимальное суммарное время обработки группы из m деталей (m =6), каждая из которых должна последовательно пройти обработку на каждом из двух станков (сначала на первом, а затем на втором станках), образующих технологическую линию. Время обработки i -ой детали (i =1,…,m ) на j -ом станке (j =1,2) t ij предполагается заданным, и, как правило, для
. В таблице 8.1 представлены исходные данные рассматриваемого примера.

Таблица 8.1 - Исходные данные для задачи Джонсона и ее решение

детали, i	Время обработки i -ой детали на j -ом станке,(мин.)		очереди, k

Изобразим графически процесс обработки деталей на двух станках для следующей произвольно выбранной очередности запуска деталей в обработку: А→Б→В→Г→Д→Е (рисунок 8.1) (нумерация деталей и последовательность их обработки совпадают).

Рисунок 8.1 – График процесса обработки группы деталей на двух станках

На рисунке 8.1
- суммарное время обработки группы изт деталей (т =6), то есть длительность совокупного производственного цикла – время, которое пройдет от момента начала обработки первой детали (i =А) на первом станке (j =1) до момента окончания обработки последней детали (i =Е) на втором станке (j =2) рассчитывается по формуле (8.1.1) и в рассматриваемом примере равно 41 мин.

где - время обработкиi -ой детали на втором станке,i = 1,…, m ;

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

- суммарное время простоя второго станка (оборудования на второй операции);

- время простоя второго станка между окончанием выполнения работы по обработке (i -1)-ой детали на этом станке и началом обработкиi -ой детали на том же самом станке (для детали первой очереди запуска
);

- время обработки деталиk k = 1,…, m ;

- время обработки деталиk -ой очереди запуска на втором станке,k = 1,…, m -1;

Критерием оптимальности в данной постановке задачи и соответственно в экономико-математической модели является минимизация длительности совокупного производственного цикла

Так как суммарное время обработки всех деталей на втором станке, то есть сумма известна и в формуле (8.1.2) для любой очередности запуска деталей является константой, то для того, чтобы обеспечить наименьшее значение длительности совокупного производственного цикла необходимо минимизировать суммарное время простоя оборудования на второй операции (время простоя второго станка):

В нашем примере время простоя второго станка:

Если для решения рассматриваемой задачи использовать метод полного перебора, то при наличии m деталей и двух станков и при условии, что все детали обрабатываются сначала на первом, а затем на втором станке в одинаковом порядке на каждом из них, как было показано выше, существуетm ! возможных вариантов (последовательностей), то есть для нашего примера имеется 6!=720 вариантов.

Известен весьма простой алгоритм для нахождения оптимальной последовательности (порядка) обработки т деталей на двух станках – алгоритм Джонсона.

Указанный алгоритм включает следующие основные шаги:

1) выбирается деталь с наименьшей продолжительностью обработки на одном из станков; в нашем примере на первой итерации это деталь Б ;

2) выбранная деталь помещается в начало очереди, если наименьшая продолжительность обработки соответствует первому станку, или в конец очереди, если – второму станку; в нашем примере деталь Б помещается в конец очереди (k =6);

3) строка(и) таблицы 8.1, соответствующая(ие) выбранной(ым) детали(ям) исключается(ются) из дальнейшего рассмотрения (вычеркивается(ются));

4) выбирается деталь среди оставшихся со следующей наименьшей продолжительностью обработки на одном из станков; в нашем примере на второй итерации это деталь В , на третьей итерации это детальЕ , на четвертой итерации это деталиА иГ , на последней итерации это детальД ;

5) выбранная деталь помещается ближе к началу или к концу очереди по указанному в шаге 2 правилу; в нашем примере на второй итерации деталь В помещается ближе к концу очереди (k =5), перед детальюБ , на третьей итерации детальЕ помещается в начало очереди (k =1), на четвертой итерации детальА k =4), а детальГ помещается в начало очереди (k =2), на последней итерации детальД помещается ближе к концу очереди (k =3);

6) если определена очередность запуска для всех деталей, то решение получено, иначе переходим к шагу 3.

В итоге реализации данного алгоритма можно получить оптимальное расписание работы двух станков (рисунок 8.2). В нашем примере (см. таблицу 8.1) найдена оптимальная очередность запуска деталей в обработку - Е→Г→Д→А→В→Б . В последней графе таблицы 8.1 показан номер очереди запуска (k ) соответствующей детали в обработку на каждом станке технологической линии.

№ операции

Рисунок 8.2 – График оптимального расписания работы двух станков

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

(8.1.5)

Затем рассчитывается длительность совокупного производственного цикла по следующей формуле:

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

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

Постановка задачи в ТР начинается с описания система устройств и множества работ. Для простого процесса обслуживания система обслуживающих устройств(ОУ) описывается их числом, то есть есть 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. Параллельные приборы. Система заданий с древовидной структурой.

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

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

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

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

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

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

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

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

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

Эта задача называется иногда задачей двухпроцессорного обслуживания задач, или задачей Джонсона (по имени S.M. Johnson, который в 1954 г. предложил алгоритм для её решения).

Стоит отметить, что когда число станков больше двух, эта задача становится NP-полной (как доказал Гэри (Garey) в 1976 г.).

Построение алгоритма

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

Рассмотрим порядок подачи деталей на станки, совпадающий с их входным порядком: .

Обозначим через время простоя второго станка непосредственно перед обработкой -ой детали (после обработки -ой детали). Наша цель — минимизировать суммарный простой :

Для первой детали мы имеем:

Для второй — т.к. она становится готовой к отправке на второй станок в момент времени , а второй станок освобождается в момент времени , то имеем:

Третья деталь становится доступной для второго станка в момент , а станок освобождается в , поэтому:

Таким образом, общий вид для выглядит так:

Посчитаем теперь суммарный простой . Утверждается, что он имеет вид:

(В это можно убедиться по индукции, либо последовательно находя выражения для суммы первых двух, трёх, и т.д. .)

Воспользуемся теперь перестановочным приёмом : попробуем обменять какие-либо два соседних элемента и и посмотрим, как при этом изменится суммарный простой.

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

Таким образом, чтобы деталь шла до детали , достаточно (хотя и не необходимо), чтобы:

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

Отняв от обеих частей этого неравенства, получим:

или, избавляясь от отрицательных чисел, получаем:

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

Впрочем, можно ещё больше упростить сортировку, если посмотреть на этот компаратор с другой стороны. Фактически он говорит нам о том, что если минимум из четырёх чисел достигается на элементе из массива , то соответствующая деталь должна идти раньше, а если на элементе из массива — то позже. Тем самым мы получаем другую форму алгоритма: отсортировать детали по минимуму из , и если у текущей детали минимум равен , то эту деталь надо обработать первой из оставшихся, иначе — последней из оставшихся.

Так или иначе, получается, что задача Джонсона с двумя станками сводится к сортировке деталей с определённой функцией сравнения элементов. Таким образом, асимптотика решения составляет .

Реализация

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

struct item { int a, b, id; bool operator< (item p) const { return min(a,b) < min(p.a ,p.b ) ; } } ; sort (v.begin () , v.end () ) ; vector< item> a, b; for (int i= 0 ; i< n; ++ i) (v[ i] .a <= v[ i] .b ? a : b) .push_back (v[ i] ) ; a.insert (a.end () , b.rbegin () , b.rend () ) ; int t1= 0 , t2= 0 ; for (int i= 0 ; i< n; ++ i) { t1 + = a[ i] .a ; t2 = max(t2,t1) + a[ i] .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-ая деталь обрабатывается последней.