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

СОДЕРЖАНИЕ

 

Введение               

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-м свободном месте расписания. На последнем шаге, оставшаяся неразмещенная  работа назначается на единственное свободное место расписания.