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

В этой главе мы рассказали о принципах работы систем календарного планирования производства . Сложность календарного планирования связана с большим количеством вариантов графиков работы . Решению этой проблемы способствуют разделение планирования и загруЗки оборудования , планирование наиболее трудоемких партий в первую очередь, применение приоритетов и использование алгоритма Джонсона. Ни один метод не дает оптимального решения,  

Для пояснения алгоритма Джонсона представим матрицу Т как двухстолбцовую  

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

Метод Петроват-Соколицына. Исходная матрица та же, что и в методе Джонсона, но снято ограничение на число операций (столбцов). Алгоритм предполагает расчет двух промежуточных сумм и их разности. Затем определяется несколько последовательностей запуска партий в обработку по следующим правилам  

Подробная характеристика первых трех вариантов решения задачи дана в главе 11. Напомним, что первый вариант имеет строгое и эффективное решение , называемое по имени его создателя алгоритмом (методом) Джонсона. Второй вариант можно при определенных условиях также свести к решению методом Джонсона, но результат при этом будет не обязательно оптимальным. Строгое решение этой задачи дал Р. Беллман, однако оно трудоемко. Третийвариант самый сложный. Эффективная эвристическая процедура его разрешения известна под названием DS-алгоритм. Этот алгоритм распространяет метод Джонсона на общий случай постановки задачи и обеспечивает околооптимальное решение. Существуют и другие подходы, которые используют теорию очередей и компьютерное моделирование , чтобы решить эту проблему. Но все они трудоемки и сложны и в то же время не гарантируют нахождения оптимальной последовательности.  

Второй пример календарной задачи на оптимизацию заключается в построении графика , наилучшим образом согласующего сроки выпуска продукции на нескольких последовательных стадиях произ-ва (переделах) при различной длительности обработки изделия на каждой из них. Напр., в типографии надо согласовать работу наборного, печатного и переплетного цехов при условии различной трудо-станкоемкости по отдельным цехам разных видов изделий (бланочной продукции, книжной продукции простого или сложного набора, в переплете или без него и т. п.). Задача может решаться при различных критериях оптимизации и различных ограничениях. Так, можно решать задачу на минимальную длительность производств, цикла и, следовательно, минимальную величину среднего остатка изделий в незавершенном произ-ве (заделе) ограничения при этом должны определяться по наличной пропускной способности различных цехов (переделов). Возможна и другая постановка той же задачи, при к-рой критерием оптимизации является наибольшее использование наличной производств, мощности при ограничениях, наложенных на сроки выпуска отдельных видов продукции. Алгоритм для точного решения этой задачи (т. н. задачи Джонсон а) разработан для случаев, когда изделие проходит всего 2 операции, и для приближенного решения при трех операциях. При большем числе операций эти алгоритмы непригодны, что практически их обесценивает, т. к. потребность в решении задачи оптимизации календарного графика возникает гл. обр. в планировании многооперационных процессов (напр., в машиностроении). Е. Боуменом (США) в 1959 и А. Лурье (СССР) в 1960 предложены математически строгие алгоритмы, основанные на общих идеях линейного программирования и позволяющие в принципе решать задачу при любом числе операций. Однако в настоящее время (1965) практически применить эти алгоритмы нельзя они слишком громоздки в расчетном отношении даже для самых мощных из существующих электронных вычислительных машин . Поэтому указанные алгоритмы имеют лишь перспективное значение либо их удастся упростить, либо прогресс вычислительной техники позволит реализовать их на новых машинах.  

Методические указания к лабораторной работе алгоритм Джонсона по курсу «ТЕОРИЯ информационныx систем» для специальностей и направлений подготовки: Специальности (направления) Квалификация специалиста Наименование Наименование Информационные системы Бакалавр информационных систем Информационные системы и технологии

УДК 774:002:006.354

Составители: О. Е. Александров.

Научный редактор: доц., канд. физ.-мат. наук О. Е. Александров

Алгоритм Джонсона: Методические указания к лабораторной работе / О. Е. Александров Екатеринбург: УГТУ-УПИ, 2010. 17 с.

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

Библиогр. 0 назв. Рис. 3. Табл. 4. Прил. 1.

Подготовлено кафедрой «Информационные системы и технологии».

Методические указания обсуждены на заседании кафедры, протокол №__

Заведующий кафедрой ________________

© Уральский государственный технический университет, 2000

Содержание

Перечень условных обозначений символов, единиц и терминов 4

Введение 4

1. Задача упорядочения. алгоритм Джонсона 4

2. Задания для самостоятельного выполнения 14

Заключение 16

Список использованных источникоВ 17

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

	суффикс «b» означает число, записанное по основанию 2 - двоичное число;
	суффикс «h» означает число, записанное по основанию 16 - шестнадцатиричное число;
	суффикс «.» означает число, записанное по основанию 10 - десятичное число;
N 1 ..N 2	диапазон целых чисел от N 1 до N 2 ;
[X 1 ..X 2)	интервал чисел от X 1 до X 2 , X 1 принадлежит интервалу, X 2 – не принадлежит;

Введение

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

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

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

Ниже изложена простейшая теория и алгоритм Джонсона [ 1 ].

1. Задача упорядочения. алгоритм Джонсона

1.1. Постановка проблемы

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

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

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

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

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

Таблица 17.1.

программы	Время (в минутах)		Принятая очередность
	подготовка	выполнение

Так как количество номеров равно 8, то имеется 8! = 40 320 различных способов следования номеров в представлении; как выбрать тот, который будет отвечать определенному выше критерию?

Исследуем прежде всего, что произойдет, если мы выберем наугад какой-нибудь порядок следования, например: b, f, с, h, g, a, d, е . Рисунок 17.1, -а это не что иное, как диаграмма Ганта, - позволяет легко подсчитать время простоя. Первая линия диаграммы составлена отрезками, подогнанными, так сказать, впритык, длина которых пропорциональна времени соответствующей подготовки разных номеров, взятых в выбранном порядке.

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

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

В выбранном нами примере полное время простоя достигает 31 минуты.

1.2. Описание идеи алгоритма Джонсона

Зато время простоя, которое соответствует очередности е, h, a, g, f, с, d, b (рис. 17.2), составляет лишь 13 мин., из них 12 перед началом представления. Выигрыш довольно значителен; поэтому имеет смысл познакомиться с алгоритмом Джонсона, который позволил получить его:

1) Изучается таблица количеств времени, необходимых для выполнения двух операций (подготовки номера и его проведения на сцене), и наименьшее из них отмечается; в данном случае это 8 минут - время проведения на сцене номера b .

2) Если это значение относится к операции первого типа (подготовка), то принимается решение начинать с соответственной операции; если, наоборот, оно относится к операции второго типа (проведение на сцене), то принимается решение оканчивать соответственной операцией. В данном случае речь идет о проведении номера на сцене; таким образом, номер b будет завершать представление.

3) Строка, относящаяся к только что сделанному распределению, вычеркивается из таблицы времен, и к оставшимся значениям вновь применяются пункты 1), 2), 3).

Таблица 17.2.

Место в последовательности

Номера итераций вычисления

Пример. Если из таблицы 17.1 вычеркнуть строку b , то наименьшее имеющееся время будет равно 10 минутам, оно соответствует номеру d и проведению на сцене; значит, номер d будет завершать номера, еще подлежащие распределению: он будет непосредственно предшествовать номеру b , назначенному ранее.

Вычеркнув из таблицы строки b и d , распределим с (11 минут, сцена), аналогично: f (12 минут, сцена), е (12 минут, подготовка), h (15 минут, подготовка), а (20 минут, подготовка) и, наконец, g (20 минут, сцена).

Таблица 17.2 показывает порядок очередности, полученный в процессе последовательных итераций. Варианты, которые имеют место (е можно распределить на четвертой итерации, а f - на пятой; а - на последней, a g - на предпоследней), ничего не меняют в конечном результате: время простоя - по-прежнему 13 минут.

Несколько дней спустя труппа «Алькасар» оказывается в Веракрусе; устройство зала, снятого директором труппы, позволяет сократить время на подготовку, но в то же время члены труппы, исполняющие номера b и h , изменили время своего пребывания на сцене (табл. 17.3).

Таблица 17.3.

программы	Время (в минутах)
	подготовка	выполнение

Применение алгоритма Джонсона дает в результате следующую очередность: d, е, b, h, a, g, f, с, которая, согласно рис. 17.3, дает время простоя в 17 мин.

Но в один прекрасный вечер одна из гримировщиц оказывается больна; нет ни возможности заменить ее, ни времени, чтобы исправить афишу. В этих условиях (табл. 17.4) время простоя увеличивается и достигает 25 мин. По своему обыкновению, директор, узнав, что гримировщица выбывает из коллектива дней на восемь, принимается за задачу минимизации. Тогда он пришел к результату, изображенному на рис. 17.5, с временем простоя в 24 мин., что не очень блестяще, но тем не менее дает некоторое улучшение.

Таблица 17.4.

программы	Время (в минутах)
	подготовка	выполнение

Браво, директор «Алькасара»!

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

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

Сейчас мы познакомимся с некоторыми случаями его применения к производственным процессам.

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

Время, идущее на каждую операцию, распределено очень неравномерно: обозначим через A i и B i время обработки i-й детали соответственно на машинах A и В .

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

p 1 , p 2 , ..., p i , ..., p n ,

который соответствовал бы наименее продолжительному полному ожиданию в промежутках между чистовой обработкой детали p j и детали p j+ 1 , причем сумма берется по последовательным значениям j .

Обозначим через T полное время, которое пройдет от начала расточки первой детали до конца чистовой обработки последней; пусть Х i есть время простоя между концом выполнения работы p i - 1 на машине В и началом работы p i на той же самой машине. Имеем (рис. 17.7)

и так как
известна, то надлежит минимизировать

Из рис. 17.7 можно еще усмотреть, что Х 1 = А 1 и

Следовательно, будет отыскиваться такое Х 2 , чтобы

Исследуем теперь сумму Х 1 + Х 2 ; имеем

Х 1 + Х 2 = Х 1 + max (A 1 + A 2 – B 1 – X 1 ;0 ) =

= max (A 1 + A 2 – B 1 ;X 1) =

= max (A 1 + A 2 – B 1 ;A 1)=

Аналогично,

Эта формула легко распространяется на n временных промежутков X i для некоторого порядка следования S деталей p i

ее можно записать еще лаконичнее:

Это означает, что берется максимум разностей, получаемых при каждом значении r , по всем r от 1 до n .

Таким образом, можно положить

Пусть теперь имеется порядок (S 1)

(S 1) = (p 1 , p 2 , p 3 , ..., p k- 1 , p k , p k +1 , p k+2 , …, p n )

и порядок (S 2 ), полученный из (S 1) перестановкой k -го и (k +1)-го элементов

(S 2 ) = (p 1 , p 2 , p 3 , ..., p k- 1 , p k+ 1 , p k , p k+2 , …, p n ).

Значения и , получаемые для порядков следования (S 1) и (S 2), одинаковы при всех r, кроме, может быть, r= k и r= k + 1.

Стало быть, мы имеем

то какой-то из двух порядков следования (S 1) и (S 2) предпочтительнее. Порядок (S 1), в котором k+ 1 следует за k , будет лучше, чем (S 2), в котором k+ 1 предшествует k , если

Поэтому можно записать

Соотношение (1) при этих условиях принимает следующий вид:

Min (A k+ 1 ; B k ) < - min (A k ; B k+ 1)

или иначе

min (A k ; B k+ 1) < min (A k+ 1 ; B k ). (2)

Отсюда следует, что порядок (…, p k , p k+ 1 , …) предпочтительнее порядка (…, p k+ 1 , p k , …), если

min (A k ; B k+ 1) < min (A k+ 1 ; B k ).

Рассмотрим тогда порядок

(S′ ) = (... , p k , p l , ... ),

которого всегда можно достичь перестановками. Менять местами элементы p k и p l не нужно, если

min (A k ; B l) ≤ min (A l ; B k ); (3)

последнее выполняется, если A k не превосходит B l , A l , B k

min (A k ; B k ) ≤ min (A l ; B l).

Следовательно, если в таблице времен можно найти время, не превосходящее всех прочих A l или B l , то искомый порядок должен будет начинаться с p k , если время A k , будучи по-прежнему наименьшим, равно некоторым другим A l или B l , искомый порядок можно будет начинать также с p k .

Соотношение (3) выполняется еще в том случае, когда B l не превосходит A k , A l , B k , что можно также записать в виде

min (A l ; B l) ≤ min (A k ; B k ).

Следовательно, если в таблице времен можно отыскать время B l , не превосходящее всех прочих A k или B k , то искомый порядок должен завершаться элементом p l ; если время B l , будучи по-прежнему наименьшим, равно некоторым другим A k или B k , искомый порядок можно с таким же правом завершать элементом p l .

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

Обобщение на трехэтапные работы. Алгоритм Джонсона применим для последовательности n работ, подлежащих выполнению в таком порядке: А , В и С , в двух нижеследующих случаях:

min A i ≥ max B i или min C i ≥ max B i .

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

A i + B i и B i + C i .

Пример. Пусть операции над деталями p 1 , ..., p 5 заданы сроками выполнения

A i , B i , C i ;

условие min A i = 6 ≥ rnax B i = 6, например, выполняется. Таким образом, мы имеем две таблицы:

Расточка (A i ) Фрезеровка (B i ) Чистовая обработка (C i )

A i + B i B i + C i

и алгоритм Джонсона позволяет выбрать

S = (p 4 , p 2 , p 3 , p 1 , p 5)

S = (p 4 , p 2 , p 1 , p 3 , p 5).

2. Задания для самостоятельного выполнения

2.1. Общие замечания

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

Варианты помеченные звездочкой дают право на освобождение от экзамена (при полном выполнении) или на освобождение от одного вопроса на экзамене (при частичном выполнении). Уровень  полное/частичное выполнение  определяет преподаватель.

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

Ознакомиться с теорией главы 1.

Ознакомиться с приложенной программой-решением задачи Форда-Фалкерсона.

Выполнить задание к лабораторной работе.

Написать и сдать отчет.

2.2. Варианты заданий

Вариант 1 (стандартный)

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

Классифицировать данную систему в соответствии с теорией систем (курсом лекций).

Указать для данной системы: множество входов, множество выходов, множество глобальных состояний.

Записать реакцию системы (либо выходную функцию).

Вариант 2 *

Разработать и описать комбинированный алгоритм (Фаулкс+Джонсон) по выбору допустимой последовательности операций и оптимизации этой ДОПУСТИМОЙ последовательности по времени.

Создать автоматизированную систему (программу) вычисления по предложенному алгоритму.

ВНИМАНИЕ!!! Самодельные реализации принимаются только в MathCAD.

1.2. Оформление результатов работы

Вы должны представить письменный отчет (один на группу) по выполненной работе (1020 страниц, не считая листингов программы - листинги рекомендуется не печатать) и работоспособный код программы. Отчет должен быть оформлен в соответствии со стандартом [ 2 ].

Отчет должен состоять из следующих частей:

титульный лист;

введение;

основная часть (может состоять из нескольких глав);

заключение;

список использованных источников.

Отчет должен содержать:

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

описание проблем, с которыми вы столкнулись при написании программы, и их решений;

подробное описание вашего кода и наиболее интересных решений, использованных в нем;

описание результатов сравнения эффективности работы вашего и предоставленного вам готового кода.

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

1.4. Прием зачета по результатам работы

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

Знание основ теории.

Знание устройства и взаимодействия частей представленного и/или своего кода программы.

Умение компилировать код и запускать программу.

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

Умение интерпретировать результаты сравнения работы своего и предоставленного вам готового кода.

Заключение

В результате выполнения этой работы:

Вы сможете лучше понять что такое упорядочение операций.

Ознакомитесь с примерами методов оптимизации порядка выполнения операций.

Получите практический навык использования алгоритма L;jycjyf.

Алгоритм Беллмана-Форда. Алгоритм Флойда. Топологическая сортировка. Сильно... . Потоки в сетях. Метод Форда-Уоршола. Алгоритм Джонсона для разреженных графов. Метаэвристики в примерах...

1. Алгоритмы построения расписаний для одноприборных систем входящих в состав систем реального времени

   Документ

   Функции становится единственно значимым. В алгоритмах «упаковки» и алгоритмах сочетающих жадные стратегии и стратегии... М., Джонсон Д. Вычислительные машины и трудно решаемые задачи. - М.: Мир, 1982. Костенко В.А., Гурьянов Е.С. Алгоритм построения...

2. Основная образовательная программа (100)

   Основная образовательная программа

   Задача «Максимальная выполнимость» Вероятностный алгоритм Джонсона . Дерандомизация. Алгоритм Гоеманса-Вильямсона. 3.11. Решение... (r|p)-центроиде. 13. Рандомизированные алгоритмы

Рассмотрим задачу последовательной обработки на двух машинах 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-ая деталь обрабатывается последней.

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

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

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)

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

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

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

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

Эта задача называется иногда задачей двухпроцессорного обслуживания задач, или задачей Джонсона (по имени 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 ; }

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

Отчетность