26493

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

Реферат

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

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

Русский

2013-08-18

29.8 KB

101 чел.

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

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

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

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

- последовательность операций строго упорядочена, то есть существует не более одной операции как непосредственно до, так и после данной операции.

- любая работа в каждый момент времени может выполняться только прибором одного типа.

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

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

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

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

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

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

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

Основными методами решения задач теории расписания являются:

- метод прямого перебора.

- метод решающих правил.

- метод выбора из активных расписаний.

- метод ветвей и границ.

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

- метод генераторов расписаний.

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

Метод прямого перебора для решения задачи теории расписаний.

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

Применение решающих правил.

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

Постановка задачи директора.

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

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

Математическая постановка задачи: 

Допустим, Tj() – это вероятность ожидания j-посетителя в случае использования    для перестановки приглашения.

Критическая оптимальность:

Решение правил для минимизации критерия F времени собеседования . Для минимизации критерия оптимальности времена собеседования необходимо установить в порядке их возрастания. Тогда оптимальная перестановка – это последовательность номеров.

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

Решающее правило для задачи одного станка.

Общие условия для постановки задачи.

И для каждой задано время обработки на станке, величина штрафа.

Штраф устанавливается за единицу времени ожидания для детали в момент поступления ее на обработку.

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

Время ожидания . Критерий оптимальности будет определен выражением: .

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

Решающее правило для задачи двух станков.

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

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

Шаг 1 – формируется множество всех деталей.  I={1,2 … in}

Шаг 2 – определяется множество j деталей, для которых время обработки на станке А меньше времени обработки на станке В.  J={i  I, if }

Шаг 3 – определяется множество оставшихся деталей Q. Q={q(I-J)}

Шаг 4 – формируется первый кортеж из номеров деталей, принадлежащих множеству J и упорядочены в порядке возрастания времени обработки на первом станке Aj. J*={j1,j2 … jk, if }}

Шаг 5 – из номеров оставшихся деталей формируется второй кортеж Q*, детали упорядочены по возрастанию времени Bj.

Q*={q1,q2 … ql, if }

Шаг 6 – оптимальная последовательность запуска деталей на обработку будет выглядеть следующим образом.

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

Метод выбора из активных расписаний

  1.  Задано множество работ     M={1,2 … m}
  2.  Задано множество приборов N={1,2 … n}
  3.  Определена матрица T=||tij|| элементы соответствующего времени выполнения i-работ j-приборами
  4.  F=||fil || - технологическая матрица, которая устанавливает порядок прохождения работ через приборы. Элементы матрицы fil  очереди номер прибора, на котором выполнена i-работа l-этапе технологии.

Здесь l-текущий номер этапов технологий и L-максимальное количество этапов. При планировании и назначении работ на приборы возможны конфликтные ситуации, так называемые конфликты первого и второго рода.


 

А также другие работы, которые могут Вас заинтересовать

59185. Нехай панують на землі добро і справедливість. Сценарій для молодших школярів 44 KB
  От саме в цій країні якось йшли вулицею хлопчик і дівчинка. Хлопчик: Що це Дівчинка: Це мабуть Чарівна паличка. Хлопчик: Як нам пощастило Тепер у нас буде скільки завгодно морозива жуйок тістечок.
59186. Навчаємось разом з героями казок. Cценарій заняття для малят у дитячому садочку 44 KB
  У проведенні заняття беруть участь діти їхні батьки рідні вихователі дитячого дошкільного закладу. Оскільки діти запросили в гості до себе своїх батьків та рідних то вони першими заходять до кімнати й зручно розташовуються.
59187. СВЯТО ПИСАНКИ 83 KB
  Ведуча: Ой що в Софіївському заграли Дзвони затремтіли Не білі голуби янголи в небі полетіли. Ведуча: А між тим нашій незалежності пішов вже десятий рік. Ведуча: В очі нам дивляться ті хто клав своє життя на алтар Вітчизни від звитяжців Запорізької Січі до в’язнів сталінських...
59188. Лицарі ввічливості 37 KB
  І ведучий: Доброго дня дорогі друзі ІІ ведучий: Доброго здоров’я ІІ ведучий: Раді бачити вас у цьому залі І ведучий: Сьогодні у нас відбудеться турнір лицарів ввічливості. ІІ ведучий: У ньому беруть участь ваші ровесники знавці правил ввічливості і хорошого тону.
59189. Сценарій спортивного свята 24.5 KB
  Естафета з обручами Дві команди за сигналом по одному від кожної команди біжать до півфінішної прямої. 3 естафета.
59190. БАТЬКИ І ДІТИ 45.5 KB
  Ми раді вітати Вас сьогодні у нашій світлиці на нашому родинному святі. У дитячому садку ми знайомимо дітей з обрядами та звичаями нашого народу, з казками та приказками, вчимо загадки, прислівя, вірші, скоромовки. А сьогодні будемо вести розмову про родину.
59191. Ой на Йвана, ой на Купала 32.5 KB
  Добре й літом у лісочку На травичці в холодочку Відпочити погуляти Зілля квітів тут нарвати Дівчата прикрасимо нашу купальницю щоб була ще красивіша. Дівчата збирають квіти плетуть вінки прикрашають ними деревце купальницю і співають...
59193. Новий рік 17.5 KB
  ік старий вирушає в дорогу Залишає нам зоряний дім Кожний кожному щастя нового Зичить радісно з роком Новим. Ведуча: Пада пада сніг лапатий Вже ступило на поріг В кожен дім це світле свято Здравствуй здраствуй Новий рік.