26493

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

Реферат

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

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

Русский

2013-08-18

29.8 KB

115 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

38592. Разработка электронного датчика микроклимата на микроконтроллере типа Tiny13 фирмы Atmel 496.5 KB
  обеспечение распределения горячего воздуха СО2 инсектицидов просушки влажных листьев. Для комфортной работы стол должен удовлетворять следующим условиям: высота стола должна быть выбрана с учетом возможности сидеть свободно в удобной позе при необходимости опираясь на подлокотники; нижняя часть стола должна быть сконструирована так чтобы программист мог удобно сидеть не был вынужден поджимать ноги; поверхность стола должна обладать свойствами исключающими появление бликов в поле зрения программиста; конструкция стола должна...
38593. Сушена сировина рослинного та тваринного походження, її використання в сфері підприємств ресторанного господарства типу Бістро 234.5 KB
  Функціональнотехнологічні властивості сировини рослинного та тваринного походження.3 Розрахунок сировини готової продукції допоміжних матеріалів та тари . Підприємства на яких здійснюється сушіння сировини можуть бути наступних типів: чисто сушильні заводи комбіновані де паралельно з сушкою сировини виробляють харчові концентрати і об'єднані сушильноконсервні заводи.1 Функціональнотехнологічні властивості сировини тваринного та рослинного походження Фізикохімічні біохімічні та...
38594. Разработка технологического процесса работы вокзала малой мощности 817 KB
  На территории РК размещено большое число железнодорожных станций разъездов депо и других хозяйственных подразделений участков пути постов контактной сети электрифицированных линий устройств связи и сигнализации от бесперебойной и согласованной Работы которых зависит выполнение планов перевозок пассажиров и грузов. Важнейшим требованием к работе железнодорожного транспорта является обеспечение полной безопасности движения поездов а также безопасности пассажиров и персонала сохранности перевозимых грузов. Железнодорожный транспорт ...
38596. Прогноз розвитку блогерських мереж у найближчі роки та оцінка перспективи створення блогерських мереж в Україні 443.5 KB
  Сукупність усіх блогів являє собою соціальний та інформаційний феномен що в грудні 2001 р. Приблизно щосекунди відкривається новий блог кількість блогів подвоюється кожних півроку. Достовірно підрахована кількість блогів на початок травня 2013 р. 156 мільйонів блогів.
38597. Веб–сайт для муниципального дошкольного образовательного учреждения детского сада для детей раннего возраста № 30 «Малыш» города Дубны Московской области 3.77 MB
  Для создания вебсайта Малыш были проанализированы законодательные документы по разработке и наполнению официального сайта проведен сравнительный анализ существующих вебресурсов выявлены требования к информационной системе разработан проект системы и наполнен определенной информацией. Структура сайта Наполнение сайта В последние годы в России быстрыми темпами развивается Интернет и большая доля населения имеет у себя дома или на работе выход к его ресурсам возникает необходимость...
38598. ФРАЗЕОЛОГИЯ В СОВРЕМЕННОЙ ПРОЗЕ И СПОСОБЫ ЕЁ ПЕРЕДАЧИ В ПЕРЕВОДЕ 381 KB
  5 Проблема перевода фразеологических единиц. Все они описывают различные способы перевода фразеологических единиц. Однако не существует единого конкретного способа их перевода которым можно было бы пользоваться в работе.
38599. РАЗРАБОТКА ИНФОРМАЦИОННОЙ СИСТЕМЫ С WEB-ДОСТУПОМ ДЛЯ ПРЕДПРИЯТИЯ СОЦИАЛЬНО-КУЛЬТУРНОЙ СФЕРЫ 6.34 MB
  В данный момент используется большое количество разных ИС, многие предприятия на заказ разрабатывают необходимую для их предприятия ИС, кто-то использует готовые, но переработанные, а кто-то готовые на подобие программы «1С». С появлением интернета появилась возможность предоставлять услуги и в иных сферах, что дало толчок к созданию ИС с web-доступом.
38600. Основні передумови вдосконалення ротаційних граблів ГУР-4,2 1.57 MB
  Основні технології заготівлі сіна, що тепер застосовують, — це заготівля розсипного сіна та пресованого. У господарствах АПК України переважає перша технологія. Вона нескладна, дає змогу обходитися комплексом більш простих машин. Проте водночас вона має низку істотних вад, основними з яких є значні затрати праці, особливо ручної, та витрати енергії.