Задачи теории расписаний

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

Вычислительную сложность алгоритма  Джонсона определяет суммарное число  сравнений длительностей операций работ. На каждом шаге j = 0, ..., n-1 для выбора размещаемой работы нужно реализовать 2*(n - j) сравнений, поэтому общее число  сравнений за n шагов алгоритма  равно n*(n+1). Таким образом, вычислительная сложность алгоритма полиномиально  зависит от объема партии работ.

Алгоритм приоритетов разбивает  процесс поиска оптимального расписания на 2 этапа. На 1-м этапе назначаются  приоритеты всех работ партии. Приоритет  каждой работы Wq (q = 1, ... , n) вычисляется  по формуле:

Pq = sign(Aq - Bq) * { M - min(Aq, Bq)}

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

M > max min (Aq, Bq),

где максимум ищется при всех q от 1 до n. На практике допустимо назначить  константу M в формуле приоритетов  следующим образом:

M = max min (Aq, Bq) + 1

Таким образом, после 1-го этапа алгоритма  приоритетов для каждой работы Wq (q = 1, ... , n) должен быть назначен приоритет Pq в диапазоне целых чисел от -M до M, то есть:

Pq =< | M |, q = 1, ... , n

На 2-м этапе алгоритма приоритетов  выполняется сортировка работ партии с целью переставить работы в  порядке неубывания их приоритетов. Для любой пары соседних работ [i] и [i+1] в полученной сортировкой перестановке S должно быть справедливо следующее  неравенство:

P[i] =< P[i+1] , i = 1, ... , n-1

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

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

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

 

1.4.Метод  полного перебора

 

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

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

Естественный способ перечисления перестановок циклическим сдвигом  состоит в том, что начав с  некоторой произвольной перестановки, последовательно сдвигать по циклу  на одно место влево все n работ  партии. При каждом сдвиге 1-я работа текущей перестановки перемещается на последнее место без изменения  взаимного расположения остальных, образуя новую перестановку. Такая  организация циклического сдвига называется вращением. Вращение всех работ нужно  продолжать, пока оно порождает новые  перестановки, не встречавшиеся ранее. Перестановка считается оригинальной, когда после сдвига позиция последнего вращаемой части не равна его  позиции в исходной перестановке. Если в результате очередного вращения получается ранее порожденная перестановка, нужно исследовать возможность  построить оригинальную перестановку, применяя процедуру локального вращения последовательно для k = n-1, n-2, ..., 2 начальных  работ при фиксированном положении  остальных n - k хвостовых работ партии. Если локальное вращение первых 1 < k < n работ порождает оригинальную перестановку, следует продолжить вращение циклическим сдвигом всех n работ  партии. В противном случае ( k = 1 ), перебор считается завершенным, т.к. перечислены все n перестановок.

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

 

1.5. Анализ расписаний

 

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

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

Чтобы отличать операции различных  работ, отрезки операций диаграммы  Ганта должны быть помечены сообразно  обозначениям соответствующих работ. Например, если работы партии обозначить строчными литерами латинского алфавита, то каждый единичный интервал отрезка  любой операции можно маркировать  литерой работы, которой принадлежит  эта операция. Для обозначения  единичных интервалов простоя машин  может быть использован символ тире(-). Таким образом, в рассмотренном  символическом варианте диаграммы  Ганта горизонтальные цепочки одинаковых литер соответствуют операциям  работ партии или промежуткам  простоя машин. Продолжительность  операций работ, промежутков простоя  и процесса обслуживания в целом  определяется соответствующим числом знакомест диаграммы Ганта. Следующий  рисунок иллюстрирует диаграмму  Ганта для расписания процесса обслуживания партии из 5-ти работ { a, b, c, d, e }, выполняемых  в алфавитном порядке:

Машина A: aabbccdddddddeeee--

Машина B: --aaaaabbbc--ddd-ee

Из приведенной диаграммы Ганта  легко найти продолжительность  процесса обслуживания (19 единиц) и  суммарный простой машины B (5 единиц), величины которых определяют качество расписания. Для любого момента времени  можно установить характер загрузки системы обслуживания операциями работ. Например, через 12 единичных интервалов после начала процесса обслуживания, машина A будет выполнять работу d, а машина B будет находиться в  состоянии простоя (-).

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

Эффект накопления работ на между  машинами можно наблюдать по диаграмме  Ганта, приведенной выше. Из него видно, что после завершения операций работ b и c на машине A они не могут быть мгновенно переданы машине B, занятой  обслуживанием предыдущей работы (a), образуя очередь на входе машины B. Максимальная длина очереди равна 2 работы в момент завершения обслуживания работы (a) машиной B.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

2.ПРАКТИЧЕСКАЯ ЧАСТЬ

2.1.Примеры задач  теории расписаний

 

Пример 1. Р | prec, pt= 1 | Стах

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

Если  n = 7, m = 2 и условия предшествования заданы графом:

то 

 

 

одно  из допустимых решений имеет вид

 

 

Пример 2. 1 | ri,pmtn | L_max

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

Требуется найти расписание {сi}=1, минимизирующее максимальное запаздывание, то есть

Lmах = max (c_i-d_i) → min

             i=1,.n

 

 

Для n= 4 и

Одно из допустимых решений задачи имеет вид:

i	1	2	3	4
pi	2	1	2	2
ri	1	2	2	7
di	2	3	4	8

                   

L_max=max{3-2;4-3;6-4;9-8}=2.

 

 

Пример 3. J3 | p_ij = 1 | C_max,

Задача  поиска расписания с минимальным  временем окончания всех работ на трех машинах, образующих систему job shop—  рабочий цех; длительности всех операций равны 1; у каждой работы свое множество  операций; для каждой операции указана машина для ее выполнения.

При n = 5, т = 3 и матрице Машины J1 М1 М3 М2 М1 J2 М2 М3 — — J3 М3 M1 — — J4 M1 М3 M1 — J5 М3 М1 М2 М3

Одно из допустимых решений задачи имеет вид:   М1   М2   М3   J1 J5 J4   J3      J1 J4   J2     J5 J1   J5 J3 J1 J4   J5   J2   0       1       2      3        4      5      6         t