Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Алгоритм составления системы уравнений Колмогорова




Читайте также:
  1. I этап реформы банковской системы (подготовительный)приходится на 1988–1990 гг.
  2. UNIT I. СИСТЕМЫ ОБРАЗОВАНИЯ
  3. VI. Имитативно-интердиктивное преддверие второй сигнальной системы
  4. А. ПОНИМАНИЕ СИСТЕМЫ И ТЕОРИИ ОПТИМИЗАЦИИ
  5. Автоматизированное исследование патологии системы гемостаза
  6. Адаптивно-ландшафтные системы земледелия
  7. Аккумуляторные топливные системы типа Common Rail
  8. Алгоритм безопасного хеширования SHA. Главный цикл алгоритма SHA.
  9. Алгоритм измерения температуры в прямой кишке
  10. Алгоритм измерения температуры тела пациенту

Методические указания к проведению лекционного занятия

Тема 9.10. Задачи массового обслуживания

План:

1. Основные понятия теории массового обслуживания

2. Система массового обслуживания с отказами

3. Система массового обслуживания с неограниченной очередью

4. Система массового обслуживания с ограниченной очередью

 

Основные понятия теории массового обслуживания

Многие экономические задачи связаны с системами массового обслуживания (СМО), в которых происходит удовлетворение требований на выполнение каких либо услуг. К системам массового обслуживания можно отнести обслуживание покупателей в сфере розничной торговли, медицинское обслуживание населения, ремонт оборудования и т.д. Заявки в систему массового обслуживания обычно поступают не регулярно, а случайно. Поэтому главной особенностью процессов массового обслуживания является их случайность.

Общая схема системы массового обслуживания показана на рис. 1:

 


Рис. …

 

Рис. 1. Схема системы массового обслуживания.

Каналами обслуживания СМО называются обслуживающие единицы, например, пункты, транспортные средства и т.д. Описание схемы: требование на обслуживание (например, неисправный автомобиль) поступает в обслуживающую систему (автомастерскую). Если есть свободные каналы обслуживания (мастера), то требование выполняется. Если все каналы заняты, то требование ставится в очередь по определенным правилам или покидает систему не обслуженным.

По числу каналов СМО делятся на одноканальные и многоканальные.

Поступающие на вход СМО заявки образуют случайный поток заявок (требований). Обслуживание заявки происходит в течение промежутка времени, длительность которого зависит от ее сложности. Поэтому данный промежуток времени также является случайным. Эти два случайных события образуют систему массового обслуживания.

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



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

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

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

Системы массового обслуживания, состояние которых не влияет на поток заявок, требующих обслуживания, называются разомкнутыми. Характеристики входного потока заявок такой СМО не зависят от того, сколько заявок уже находится в системе в данный момент.

В теории очередей поток требований описывается простейшим (пуассоновским) потоком событий, который обладает тремя свойствами:



Стационарностьюпостоянным количеством событий в единицу времени;

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

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

(9.1)

где - вероятность, что за время t произойдет k событий, λ - количество событий в единицу времени (интенсивность потока).

Дисциплина очереди описывает порядок обслуживания требований в системе. Длина очереди может быть ограниченной или не ограниченной. Правила обслуживания:

- FIFO – «первый пришел - первый обслужился» (First Input – First Output);

- LIFO – «последний пришел – первый обслужился» (Last Input - First Output);

- ограничено время пребывания в очереди;

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

- случайно.

Механизм обслуживания характеризуется продолжительностью процедур обслуживания и количеством одновременно обслуживаемых требований.

Время обслуживания – случайная величина, описываемая экспоненциальным законом распределения:

(9.2)
где μ – интенсивность обслуживания, т.е. количество требований обслуживающихся в единицу времени: , где Тобссреднее время обслуживания.

Коэффициент загрузки СМО среднее число каналов, которые необходимо иметь, чтобы обслуживать в единицу времени все поступающие требования.

(9.3)

Если α<n, где п – количество каналов обслуживания, то очередь не может расти безгранично, то есть число обслуживающих каналов должно быть больше среднего числа каналов, необходимых для того, чтобы за единицу времени обслужить все поступающие требования. Данное условие называется условием стационарности.

Различают три вида СМО:

Система с отказами – это система, в которой в случае загрузки всех каналов обслуживания, новые требования не обслуживаются и система отказывает в удовлетворении этих требований.

Система с очередью – это система, в которой вновь поступившие требования в случае загрузки всех каналов обслуживания ставятся в очередь.

Система смешанного типа – это система, которая имеет ограниченную длину очереди.

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

Это система массового обслуживания, состоящая из одного телефонного аппарата, который находится в двух возможных состояниях: либо свободен, либо занят. Обозначения: S0 аппарат свободен; S1аппарат занят; λ01 – интенсивность нагрузки аппарата, или количество заявок на переговоры в единицу времени; λ10 – интенсивность обслуживания аппаратом, или количество обслуживаемых заявок в единицу времени. Стрелка из S0 в S1 означает переход системы из состояния «аппарат свободен» в состояние «аппарат занят» и наоборот.

Анализ состояния системы массового обслуживания сводится к определению вероятности, с которой система пребывает в данном состоянии.

В общем случае вероятностью i-го состояния рi(t), называется вероятность того, что в момент времени t система будет находиться в состоянии Sj.

Для любого момента t справедливо соотношение:

(9.4)

где п + 1 – общее число состояний системы массового обслуживания.

Определить вероятности состояний системы массового обслуживания можно, решив систему уравнений Колмогорова.

Алгоритм составления системы уравнений Колмогорова

1. В левую часть каждого уравнения ставится производная веро­ятности i-го состояния по времени.

2. В правую часть каждого уравнения ставится:

а) сумма произведений вероятностей всех состояний, из кото­рых идут стрелки в i-е состояние, на интенсивности соответствующих потоков событий;

б) минус суммарная интенсивность всех потоков, выводящих систему из данного состояния, умноженная на вероятность i-го состояния.

В полученной системе Колмогорова независимых уравнений на единицу меньше их общего числа. Для решения системы добавляют уравнение (9.4).

Задав начальные условия и решив систему дифференциальных уравнений Колмогорова, находят систему функций времени рi(t), где i – номер состояния. Это позволяет получить дискретное рас­пределение вероятностей системы массового обслуживания для лю­бого момента времени.


Дата добавления: 2015-09-13; просмотров: 23; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2020 год. (0.005 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты