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

СОДЕРЖАНИЕ

Введение               

1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ               

1.1. Основные понятия теории расписаний               

1.2. Задача двух машин              

1.3. Перестановочный прием               

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

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

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

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

СПИСОК ЛИТЕРАТУРЫ             

Введение

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

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

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

1.ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

1.1.Основные понятия теории расписаний

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

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

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

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

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

-число машин в системе обслуживания;

-количество операций в каждой работе;

-порядок прохождения машин для каждой работы.

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

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

• параллельное выполнение операций одной работы недопустимо;
• каждая операция выполняется полностью одной машиной;
• прерывания выполнения операций отсутствуют;
• любая машина в любой момент выполняет не более одной операции.

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

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

1. Задача  двух машин

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

Классической прикладной интерпретацией задачи 2-х машин является составление  оптимального расписания конвейерной  обработки партии деталей на 2-х  станках или пакета заданий 2-мя процессорами. По этой причине эту задачу часто  называют задачей о 2-х станках  или задачей о 2-х процессорах. Независимо от прикладной интерпретации  исходными данными задачи 2-х машин  являются:

• состав партии работ;
• перечень машин системы обслуживания;
• продолжительности выполнения операций.

Состав партии формально задает конечное множество:

W = { Wq , q = 1,...,n },

где Wq - обзначение q-й работы, а n - число  работ партии. Например, для обозначения  работ могут быть использованы строчные буквы латинского алфавита:

W = { a, b, c, ... x, y, z }.

Систему обслуживания задает упорядоченная  пара (A, B), где A и B обозначают машины для  выполнения 1-й и 2-й операции каждой работы. Длительности операций каждой работы Wq на машинах A и B задаются величинами Aq и Bq (q = 1,...,n), соответственно. Причем, Aq = 0 или Bq = 0, если работа Wq не обслуживается  машиной A или B, т.е. имеет только одну операцию.

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

S = ( [1], [2], ... [i], ... [n] ) ,

где [i] обозначает работу, которая  имеет i-ю очередность обслуживания.

Если i-ю очередь имеет работа Wq, то длительности ее операций Aq и Bq обозначаются A[i] и B[i], соответственно. Для партии объемом n работ можно построить n различных перестановок работ, определяющих n различных допустимых расписаний.

Специфика задачи 2-х машин позволяет  ограничиться рассмотрением только перестановочных расписаний, в которых  машина A не имеет простоев. Желаемую плотность упаковки графика машины A можно обеспечить сдвигом даты начала всех операций влево. Однако, упаковка графика машины A не означает отсутствие простоев машины B. Более того, в расписании обычно необходимо предусмотреть простои  машины B, чтобы гарантировать выполнение условий простого процесса обслуживания.

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

X[i] = max(Y[i] - X[1] - X[2] - ... - X[i-1], 0),

где величины Y[i] определяются как:

Y[i] = A[1] + A[2] + ... + A[i] - B[1] - B[2] - ... - B[i-1] .

Пусть D[i] обозначает частную сумму  простоев машины B до начала выполнения на ней работы [i], т.е.:

D[i] = X[i] + X[2] + ... + X[i].

Подстановка выражений локальных  простоев машины B позволяет представить  указанные частные суммы в  виде следующих рекуррентных соотношений:

D[i] = max(Y[i], D[i-1]), D[1] = A[1],

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

D[i] = max(Y[i], Y[i-1], ..., Y[1]).

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

F(S) = B[1] + ... + B[n] + max(Y[n], Y[n-1], ..., Y[1]).

Оптимальное расписание для задачи 2-х машин должно гарантировать  минимальную продолжительность  обслуживания партии. Формально оно  определяется перестановкой работ S, которая обеспечивает минимум  функции цели F(S) на множестве всех n различных перестановок работ партии. Выполнение условий простого процесса обслуживания гарантирует способ назначения простоев машины B, рассмотренный выше.

Следует отметить, что суммарная  длительность операций машины B не зависит  от порядка обслуживания работ партии, так как:

B[1] + ... + B[i] + ... + B[n] = const.

Это обстоятельство позволяет упростить  функцию цели F(S) и свести задачу 2-х машин к выбору перестановки работ, которая минимизирует суммарный  простой машины B, или обеспечивает минимум максимальной из величин Y[i] (i=1,...,n):

max (Y[n], Y[n-1], ..., Y[1]) -> min

на множестве всех n перестановок S работ партии.

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

1.3.Перестановочный прием

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

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

min (A[i], B[i+1]) =< min (A[i+1], B[i]), i = 1, ..., n-1.

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

Алгоритм Джонсона разбивает процедуру  синтеза оптимального расписания для  партии из n работ на n последовательных шагов. На каждом шаге определяется место  в расписании для одной из работ  партии. При этом, на очередном шаге выбирается работа, которая обладает самой короткой, т.е. минимальной  по длительности, операцией среди  всех пока неразмещенных работ. Для  размещения выбранной работы используется либо наименьшее, либо наибольшее по номеру свободное место расписания в  зависимости от соотношения длительности ее операций на машинах A и B. Если короткая операция выбранной работы Wq выполняется  машиной B, т.е. Bq < Aq, то для размещения работы Wq назначается наибольшее по номеру свободное место расписания. В остальных случаях (Aq < Bq или Aq = Bq), выбранная работа Wq размещается  на 1-м свободном месте расписания. На последнем шаге, оставшаяся неразмещенная  работа назначается на единственное свободное место расписания.

При равенстве продолжительности  коротких операций у 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

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

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

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