26493

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

Реферат

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

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

Русский

2013-08-18

29.8 KB

96 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Общие условия: в задаче директора предполагается, что на прием к директору записалось 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-максимальное количество этапов. При планировании и назначении работ на приборы возможны конфликтные ситуации, так называемые конфликты первого и второго рода.


 

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

41971. Обчислювальний процес, що розгалужується, з різними логічними умовами: оператор if... else, умовна операція (?:), оператор switch, оператор break, оператор goto 23.72 KB
  else умовна операція : оператор switch оператор brek оператор goto Ціль роботи: Вивчити реалізацію в мові ветвящихся обчислювальних процесів . Навчитися писати програми використовуючи оператори: розгалуження if.else переключення switch у парі з оператором brek оператор переходу goto тернарную умовну операцію .
41972. Розробка програм з циклічними обчислювальними процесами 44.87 KB
  Розробка програм з циклічними обчислювальними процесами Ціль роботи: Вивчити написання програм мовою С, використовуючи ітераційні (циклічні) методи, освоїти основні оператори, що підтримують роботу з циклами (for, while, do... while). Навчитися писати програми, використовуючи дані оператори.
41973. ПОБУДОВА ОПТИМАЛЬНОГО НЕРІВНОМІРНОГО КОДУ ЗА МЕТОДИКОЮ ХАФФМАНА 53.47 KB
  0 проводиться перехід до побудови дерева коду за допомогою проміжних вузлів. 161 00074 3 В 893 00412 21 Х 156 00072 11 Л 745 00344 29 Ю 148 00068 16 Р 699 00322 22 Ц 126 00058 №п п Символ ni pi №п п Символ ni pi 12 М 656 00303 25 Щ 108 00050 10 К 574 00265 24 Ш 60 00028 5 Д 507 00234 28 Э 59 00027 26 Ы 467 00215 20 Ф 30 00014 19 У 399 00184 8 З 4 00002 Дерево коду за методикою Хаффмана: Визначаємо ентропію джерела за формулою: Визначаємо максимальний ступінь стиснення інформації: Середня довжина кодової комбінації:...
41976. Изучение методики процедурного программирования в СУБД 903.17 KB
  Изучение управленческих конструкций IFEndIF и IIF. Изучение конструкций построения циклов For EndFOR. Изучение управленческих конструкций IFEndIF и IIF.
41977. Численное дифференцирование и интегрирование 1.37 MB
  Вычислить интеграл по формуле прямоугольников используя для оценки точности двойной просчет при n1= 8 и n2=10. По формуле левых прямоугольников получим I1=h0126.72062243; По формуле правых прямоугольников находим I2=h 6.15576821; Работа 3 Задание: 1 Вычислить интеграл по формуле трапеций с тремя десятичными знаками.
41978. Исследование объемов передаваемой информации в каналах волоконно-оптических систем связи 15.28 KB
  Целью работы является исследование энергетического потенциала и пропускной способности волоконнооптического канала системы с технологией DWDM. Для предложенной технологии задан набор исходных параметров который включает в себя частотные пространственноэнергетические и технологические параметры системы обозначены зеленым цветом. Задание к лабораторной работе Для предложенной технологии волоконнооптической системы согласно номеру рабочего места исследовать характеристики системы по всем этапам расчета при заданном наборе исходных...