Метод приоритетов для задач разработки расписаний

"МОСКОВСКИЙ  ГОСУДАРСТВЕННЫЙ СТРОИТЕЛЬНЫЙ УНИВЕРСТИТЕТ"

Факультет Информационных Технологий и Автоматизаций  Систем  
 
 
 
 
 

Реферат

Метод приоритетов для  задач разработки расписаний 
 
 

Выполнилa:

Студентка 2 курса факультета ИСТАС  группы 2

Толстошеева М. В. 
 
 
 
 
 
 
 
 

Москва 2011

   Содержание

 

ВВЕДЕНИЕ.

1. Проблемы упорядочения                          4

    1.1 Вопросы идеального упорядочения                       4 

2. Методы решения  задач теории расписаний                 5       

   

3. Типы алгоритмов  составления расписаний                                              5 

4.   Некоторые области  применения результатов  ТР в информатике  и   вычислительной технике                                                                                        8 

5. Пример расписания экзаменов факультета ИСТАС                                     9  

6. Используемая литература                      12 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

   Введение. 
 

Теория  расписаний. 

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

Под словом «ограничения»  при составлении расписаний подразумевается  то, что круг составления расписаний ограничен двумя классами: 

1. Составление расписаний без прерываний.

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

2. Составление расписаний с помощью  списка.

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

1. Проблемы  упорядочения

 

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

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

1. Вопросы «идеального» упорядочения

 

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

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

   2) Однозначно определены устройства, выделяемые для выполнения заданных работ.

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

   Существует  определенное различие между терминами  “упорядочение” и “составление расписания”. Упорядочение подразумевает формирование очередности операций, в то время как составление расписания означает задание последовательности действий.

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

2. Методы  решения задач  теории расписаний

 

   «Временной» характер задач ТР выделяет их в  особый класс, существенно отличающийся от «объемных» экономических задач. Если в последних требуется ответить на вопрос, что и сколько производить, то в задачах ТР необходимо определить, когда, в какой последовательности выполнять работы. Это различие в существе задач определяет различие в методах и возможностях их решения. Для задач объемного характера развит достаточно мощный аппарат, главным образом математического программирования, позволяющий, в общем, с успехом добиваться их решения. Для задач ТР решающий аппарат развит в гораздо меньшей степени.

   Поиск оптимального или близкого к оптимальному расписания осуществляется с помощью одного из 4 подходов:

   - математического программирования;

   - комбинаторного;

   - эвристического;

- статистического  (вероятностного). 
 

3. Типы  алгоритмов составления  расписаний.

 

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

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

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

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

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

   Составление расписаний на ЭЦВМ с использованием одного из алгоритмов диспетчеризации называется иногда моделированием процесса. Это связано с тем, что программа воспроизводит физический процесс выполнения операций во времени в том смысле, что порядок назначений совпадает с порядком реального выполнения операций.

   Введем  теперь очень важное понятие приоритета работы или операции. Приоритет – это числовая характеристика работы или операции, используемая при выборе из всех возможных. Например, в алгоритме последовательного включения работ должно существовать какое-то правило, определяющее порядок включения работ в расписание, и это правило удобно формулировать в терминах приоритетов: работы выбираются в порядке возрастания приписанных им числовых характеристик. Каждому из n! способов назначения приоритетов работ будет в этом случае соответствовать один вполне определенный алгоритм указанного типа – алгоритм последовательного включения работ.

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

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