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


 

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

39065. Программа для бизнес-планирования производства и оказания услуг в бизнесе Project Expert 90.5 KB
  Аналитическая система Project Expert программа позволяющая прожить планируемые инвестиционные решения без потери финансовых средств предоставить необходимую финансовую отчётность потенциальным инвесторам и кредиторам обосновать для них эффективность участия в проекте. Project Expert поможет: Разработать бизнесплан развития предприятия Разработать финансовую модель проекта и компании Определить финансирование проекта. Работу с программой Project Expert можно разделить на 6 этапов: 1.
39066. Язык UML 91 KB
  На UML диаграмме примечание присоединяется к одному или нескольким элементам диаграммы. Внутри прямоугольникапримечания помещаются комментарии или ограничения относящиеся к элементу или нескольким элементам диаграммы. UML диаграммы С помощью комбинации пиктограмм строятся UML диаграммы. Рассмотрим три из них: диаграммы прецедентов диаграммы классов и диаграммы действий.
39067. Характеристика case-средства Rational Rose 138 KB
  Назначение элементов экрана интерфейса Rose: Браузер browser используется для быстрой навигации по модели. C его помощью можно документировать элементы модели Rose. Документация будет выводиться также в отчетах создаваемых в среде Rose.
39068. Работа с объектами информационных систем на платформе 1С:Предприятие 43 KB
  1С:Предприятие является универсальной системой автоматизации деятельности предприятий учреждений. За счет своей универсальности система 1С:Предприятие может быть использована для автоматизации самых разных участков экономической деятельности предприятия: учета товарных и материальных средств взаиморасчетов с контрагентами. Самыми распространенными наверное являются такие конфигурации как Бухгалтерия Бухгалтерия государственного учреждения Зарплата и кадры бюджетного учреждения Зарплата и управление персоналом Управление...
39069. Тестированию программного обеспечения с использованием языка программирования C# и NUnit-тестов 82.5 KB
  Тестовая деятельность предусматривающая эксплуатацию программного продукта носит название динамического тестирования. Статическое и динамическое тестирование дополняют друг друга и каждый из этих типов тестирования реализует собственный подход к выявлению ошибок. К четырем компонентам которые должны быть оптимизированы для целей быстрого тестирования относятся персонал процесс комплексных испытаний статическое тестирование и динамическое тестирование. 1 Для выполнения быстрого тестирования нужны хорошо подготовленные и гибкие...
39070. Использование программных продуктов CRM на российском рынке 304.5 KB
  Системы управления взаимоотношения с клиентами CRM Система управления взаимоотношениями с клиентами CRM CRMсистема сокращение от англ. CRM модель взаимодействия полагающая что центром всей философии бизнеса является клиент а основными направлениями деятельности являются меры по поддержке эффективного маркетинга продаж и обслуживания клиентов. Состав системы CRMсистема может включать в себя: Фронтальную часть обеспечивающую обслуживание клиентов на точках продаж с автономной распределенной или централизованной обработкой...
39071. Универсальный язык моделирования (UML) 128.5 KB
  UML – это набор различных видов диаграмм: диаграмма классов диаграмма объектов диаграмма связей диаграмма вариантов использования текстовый сценарий диаграмма действий диаграмма состояний диаграмма последовательности UML – это не средство разработки программного обеспечения это всего лишь средство понятных иллюстраций разрабатываемого проекта. Варианты использования Сценарий. Диаграмма вариантов использования. Описание вариантов использования.
39072. Технология подготовки и решения задач с помощью компьютера 122.5 KB
  Сопровождение программы: доработка программы для решения конкретных задач; составление документации к pешенной задаче к математической модели к алгоpитму к пpогpамме к набору тестов к использованию. Процесс разработки программы можно выразить следующей формулой: На начальном этапе работы анализируются и формулируются требования к программе разрабатывается точное описание того что должна делать программа и каких результатов необходимо достичь с ее помощью. Полученный вариант программы подвергается систематическому тестированию...
39073. Использование компьютеров в науке и производстве 126 KB
  Системы автоматизированного проектирования САПР комплексные программнотехнические системы предназначенные для выполнения проектных работ с применением математических методов. Системы САПР широко используются в архитектуре электронике энергетике механике и др. Автоматизированные системы научных исследований АСНИ.