26493

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

Реферат

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

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

Русский

2013-08-18

29.8 KB

110 чел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

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

82237. Науки о природе и науки об обществе (их сходства и отличия): современные трактовки и проблемы 39.22 KB
  Шаги в развитии проблемы классификации наук предпринятые в частности Вильгельмом Дильтеем 1833-1911 привели к отделению наук о духе и наук о природе. В работе Введение в науки о духе философ различает их прежде всего по предмету. Предмет наук о природе составляют внешние по отношению к человеку явления.
82238. Конвергенция естественнонаучного и социально – гуманитарного знания в неклассической науке, эволюция и механизмы взаимодействия 42.89 KB
  Представители философия жизни Дильтей Ницше Зиммель Бергсон утверждают что жизнь первичная реальность органический прцесс для познания которого нужны интуиция понимание вживание вчувствование. Предмет социального познания культурно значимая индивидуальная действительность. Признается возможность объективного познания культурноисторических и соц явлений. Соцгум познание признается частным видом научного познания подчиняющимся общим научным закономерностям.
82239. Применение общенаучных достижений в социально-гуманитарном познании. Междисциплинарные связи и научная картина мира в социально-гуманитарных науках 34.93 KB
  Социальногуманитарные науки как и наука в целом всегда создают целостные картины общества. Научная картина общества это целостная система знаний которая объясняет основные законы возникновения и существования окружающей социальной действительности и систематизирует конкретные знания полученные в различных областях социальногуманитарных наук. Она представляет собой своеобразную модель общества включающую в себя общие понятия принципы гипотезы прежде всего обществознания которые сформулированы в терминах обыденного языка и...
82240. Индивидуальный и коллективный субъекты, формы их существования. Включённость сознания субъекта, его системы ценностей и интересов в объект исследования СГН 40.74 KB
  Означает ли сказанное что мы должны признать футбольную команду самостоятельным субъектом деятельности И не означает ли такое признание что мы приписываем собственную деятельность ее сознательно или стихийно сложившиеся надындивидуальные условия регулятивные механизмы и результаты некоему мифологическому субъекту вполне подобному Абсолютной Идее Гегеля действующей посредством живых людей Такова например позиция Э.Если мы не хотим впасть в какуюто туманную мистику или мифологию в понимании общества то можно ли вообще видеть в нем...
82241. Коммуникативная рациональность. Роль традиций, ценностей, образцов интерпритации и предрассудков (Г.Гадамер) в межсубъектном понимании и смыслополагании 38.92 KB
  Что такое понимание Можно ли рассматривать понимание только как знание наравне с эмпирическим и теоретическим знанием Несомненно понимание является знанием но знанием особенным имеющим специфические черты которые существенно отличают его от других видов знания. Так прежде всего необходимо рассматривать понимание как осмысление как выявление и реконструкцию смысла. Таким образом главной задачей герменевтики становится истолкование и понимание текстов. Дильтей полагает что главным методом данных наук является понимание.
82242. Методологические функции «предпосылочного знания» и регулятивных принципов в науке 34.35 KB
  Одновременно произошло уточнение понимания природы социальности и исследования в сфере философии науки должны раскрывать как и в каких формах социальный и культурно-исторический моменты входят в содержание знания и влияют на способы и результаты познавательной деятельности. Сегодня найдены реальные вполне адекватные формы и опосредующие механизмы такого воздействия в частности выявлена роль идеалов и норм философско-мировоззренческих предпосылок и оснований научного знания. Через них принимая форму ценностного сознания социальная и...
82243. Ценностные предпосылки как следствия коммуникативности СГН. Оценочные суждения в науке и необходимость «ценностной нейтральности» в социальном исследовании 34.11 KB
  Наиболее важной классификацией ценностей является их деление на абсолютные ценности, т.е., разделяемые всеми людьми (жизнь, здоровье, любовь, красота, истина, справедливость, свобода, счастье и т.д.) и относительные ценности, т.е., разделяемые только определенной группой людей (деньги, слава, наслаждение, власть, статус и т.д.).
82244. Принципы «логики социальных наук» К. Поппера 30.45 KB
  Признание того что ценности в науке выражают ее социокультурную обусловленность становится определяющим в философии и методологии науки особенно социально гуманитарного знания. В этом отличие науки от социального знания кот субъективно. Поппер утверждает что и естественный и соц науки имеют общий научный метод познания основаны на доказательствах. Согласно Адорно нельзя уравнивать соц и естеств науки.
82245. Роль научной картины мира, стиля научного познания, философских категорий и принципов, представлений здравого смысла в исследовательском процессе социально-гуманитарных наук 33.42 KB
  Все больше возрастает значимость понятия картина мира для методологии соцгум наук а развитие соцгум наук в свою очередь все активнее вводит гум составляющую в НКМ. Понимание КМ в соцгум науках не возможно без ориентации на человека понимания его места в культуре в мире способов видения им мира. В КМ соцгум наук нет противопоставления субъектачеловека и объектамира описываются лишь типы понимания мира включающего самого человека.