КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Алгоритм составления системы уравнений Колмогорова
Методические указания к проведению лекционного занятия
Тема 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; просмотров: 207; Мы поможем в написании вашей работы!; Нарушение авторских прав |