І. Теория массового обслуживания, определение, классификация, показатели эффективности.
Теория массового обслуживания-теория, которая изучает статистические закономерности в массовых операциях, состоящих из большого числа однородных элементарных операций. К ним, в частности, относятся: составление однотипных деталей на конвейере, выдача инструментов, ремонт станков, работа телефонной станции, обслуживание покупателей в магазине, в билетных кассах, клиентов в парикмахерских, техническое обслуживание машин и оборудования и др.Синонимом теории обслуживания является теория очередей. В системах массового обслуживания, в которых заявки на элементарные операции поступают в случайные моменты времени или обслуживаются в течение случайных промежутков времени, появление очередей - неизбежное зло. При большом количестве каналов обслуживания (ремонтных бригад, продавцов, телефонисток) Система терпит убытки из-за возможных длительные простои каналов. По малого количества каналов обслуживания, убытки системы вызывают очереди, которые накапливаются.
Задача теории массового обслуживания - изучить статистические закономерности входного потока заявок на элементарные операции и длительность обслуживания заявок, а также дать оценку качества систем обслуживания (выяснить пропускную способность) при различных правил формирования очередей. Очереди могут быть организованы по-разному –с ограниченной и неограниченной длиной очереди, с ограниченным временем ожидания и др.
Предметом теории массового обслуживания является построение математических моделей, связывающих заданные условия работы систем массового обслуживания (число каналов, их производительность, характер потока, заявок и т.п.) с показателями эффективности этих систем, описывающих их способность справляться с потоком заявок.
Под потоком событий понимают последовательность однородных событий, следующих одна за другой в какие-то случайные моменты времени (например, поток вызовов на телефонной станции, поток отказов БВМ, поток покупателей и т.п.).Поток характеризуется интенсивностью λ - частотой появления события или средним числом событий, которые поступают в систему массового обслуживания за единицу времени.
В качестве показателей эффективности систем массового обслуживания могут использоваться следующие:
- Среднее (здесь и далее среднее как математическое ожидание соответствующих случайных величин) число заявок, обслуживаемых в единицу времени;
- Среднее количество заявок в очереди;
- Среднее время ожидания на обслуживание;
- Вероятность отказа в обслуживании без ожидания;
- Вероятность того, что число заявок в очереди превысит определенное значение и тому подобное.
Системы массового обслуживания делятся на два основных типа (класса): с ожиданием (очередью) и с отказами. В системе массового обслуживания с ожиданием заявка, поступившая в момент занятости каналов,не отправляется, а становится в очередь на обслуживание.
В системах с отказом заявка, поступающая в момент, когда все каналы заняты, получает отказ и покидает систему, не принимая участия в дальнейшем процессе обслуживания (например, заявка на телефонный разговор в момент, когда все каналы заняты, получает отказ и покидает систему обслуженных).
2 - очередь -требования, ожидающие обслуживания.Очередь оценивается средней длиной- числом объектов или клиентов, ожидающих обслуживания.
3 - обслуживающие аппараты (каналы обслуживания) - совокупность рабочих мест, исполнителей, оборудования, осуществляющих обслуживание требований по определенной технологии.
4 - выходящий поток требований - поток требований, прошедших СМО. В общем случае выходящий поток может состоять из требований обслуженных и необслуженных. Пример необслуженных требований: отсутствие нужной детали для автомобиля, находящегося в ремонте.
5 - замыкание (возможное) СМО - состояние системы, при котором входящий поток требований зависит от выходящего.
Классификация СМО :
1.По ограничениям на длину очереди:
• СМО с потерями - требование покидает СМО необслуженным, если в момент его поступления все каналы заняты;
• СМО без потерь - требование занимает очередь, даже если все каналы заняты;
• СМО с ограничениями по длине очереди т или времени ожидания: если существует ограничение на очередь, то вновь поступившее требование выбывает из системы необслуженным.
2. По количеству каналов обслуживания п:
• одноканальные: n = 1;
• многоканальные n > 2.
3. По типу обслуживающих каналов:
• однотипные (универсальные);
• разнотипные (специализированные).
4. По порядку обслуживания:
• однофазовые - обслуживание производится на одном аппарате (посту);
• многофазовые - требования последовательно проходит несколько аппаратов обслуживания.
5. По приоритетности обслуживания:
• без приоритета - требования обслуживаются в порядке их поступления наСМО;
• с приоритетом - требования обслуживаются в зависимости от присвоенногоим при поступлении ранга приоритетности.
6. По величине входящего потока требований:
• с неограниченным входящим потоком;
• с ограниченным входящим потоком (например, в случае предварительной записи на определенные виды работ и услуг).
7. По структуре СМО:
• замкнутые - входящий поток требований при прочих равных условиях зависит от числа ранее обслуженных требований (комплексное АТП, обслуживающее только свои автомобили;
• открытые - входящий поток требований не зависит от числа ранее обслуженных: АЗС общего пользования, магазин по продаже запасных частей.
Для всех видов СМО используются следующие показатели эффективности:
- относительная пропускная способность - это средняя доля поступающих заявок, обслуживаемых системой;
- абсолютная пропускная способность - это среднее число заявок, обслуживаемых системой в единицу времени;
- вероятность отказа - это вероятность того, что заявка покинет систему без обслуживания;
- среднее число занятых каналов - для многоканальных СМО.
ІІ. Теоретическое описание методов решения задания
2.1. СМО с отказами
Одноканальная система (СМО) с отказами
Имеется один канал, на который поступает поток заявок с интенсивностью λ,поток обслуживания имеет интенсивность μ.
Система S (СМО) имеет два состояния : – канал свободен;
- канал занят.
Важнейшими показателями эффективности СМО с отказами являются следующие параметры:
1. Абсолютная пропускная способность системы;
2. Относительная пропускная способность системы.
Абсолютной пропускной способностью СМО называется среднее число заявок, которое может обслужить система за единицу времени:
,
где - интенсивность потока заявок;
- интенсивность потока обслуживания.
При этом интенсивность потока обслуживания является обратной величиной к среднему времени обслуживания :
.
Относительной пропускной способностью СМО называется средняя доля поступивших заявок, обслуживаемая системой, т.е. отношение среднего числа заявок, которое может обслужить система за единицу времени, к среднему числу заявок, поступивших в систему за это время : .
3. Вероятность отказа (Р) – величина, характеризующая вероятность того, что заявка покинет систему массового обслуживания не обслужены. Показывает долю заявок, которым будет отказано в предоставлении соответствующей услуги: .
4. Среднее число занятых каналов (для многоканальной системы). Этот показатель рассчитывается следующим образом:
.
Учитывая нормировочное условие ;
.
Определяется также интенсивность нагрузки канала - р (или приведена интенсивность потока заявок) - это показатель, который выражает среднее количество заявок, поступающей среднего обслуживании одной заявки. Он рассчитывается по формуле: р = .
Многоканальная система (СМО) с отказами
Имеется nканалов, на которые поступает поток заявок с интенсивностью λ, поток обслуживания имеет интенсивность μ.Система S (СМО) имеет следующие состояния : ,
,
,…,
,…,
, где
- состояние системы, когда в ней находится kзаявок, т.е. занято kканалов.
Поток заявок последовательно переводит систему из любого левого состояния в соседнее правое с одной и той же интенсивностью λ. Интенсивность же потока обслуживании, переводящих систему из любого правого состояния в соседнее левое состояние, постоянно меняется в зависимости от состояния.
В многоканальных системах массового обслуживания с предельными вероятностями используют формулы для предельных вероятностей состояния, которые получили название формул Эрланга в честь А.К. Эрланга (конец XIX - начало XX в.) - Датского инженера, математика, основателя теории массового обслуживания.
Вероятность отказа системы массового обслуживания - это предельная вероятность того, что все n каналов системы будут заняты, то есть:
,
Относительная пропускная способность - вероятность того, что заявка будет обслужена определяется: .
Абсолютная пропускная способность рассчитывается:A=
Среднее число занятых каналов – математическое ожидание числа занятых каналов:
или =
.
Для классификации систем массового обслуживания важное значение имеет дисциплина обслуживания, определяет порядок выбора заявок из числа поступивших и порядок распределения их между свободными каналами. По этому признаку обслуживания заявки может быть организовано по принципу очередности поступления в порядке поступления (с начала) или наоборот обслуживаются те, которые поступили в конце (с конца), с приоритетом обслуживания (в первую очередь обслуживаются важнейшие заявки).
2.2.СМО с очередью
В качестве показателей эффективности СМО с ожиданием, кроме уже известных показателей — абсолютной Aи относительной Q пропускной способности, вероятности отказа , среднего числа занятых каналов к (для многоканальной системы) будем рассматривать также следующие:
1) — среднее число заявок в системе;
2) — среднее время пребывания заявки в системе;
3) — среднее число заявок в очереди (длина очереди);
4) — среднее время пребывания заявки в очереди;
5) — вероятность того, что канал занят (степень загрузки канала).
Одноканальная система с неограниченной очередью
Имеется одноканальная СМО с очередью, на которую не наложены никакие ограничения (ни по длине очереди, ни по времени ожидания). Поток заявок, поступающих в СМО, имеет интенсивность , а поток обслуживании — интенсивность
. Система может находиться в одном из состояний
,…,
, по числу заявок, находящихся в СМО:
— канал свободен;
— канал занят (обслуживает заявку), очереди нет;
— канал занят, одна заявка стоит в очереди;
— канал занят, (k-1) заявок стоят в очереди и т.д.
Если p< 1, т.е. среднее число приходящих заявок меньше среднего числа обслуженных заявок (в единицу времени), то предельные вероятности существуют. Если p
, очередь растет до бесконечности.
=
Так как предельные вероятности существуют лишь при p<1, то геометрический ряд со знаменателем p<1, записанный в скобках сходится к сумме, равной .
Поэтомy и с учетом соотношений :
,
, …,
, найдем предельные вероятности других состояний
,
,
, …,
, …
Предельные вероятности образуют убывающую геометрическую профессию со знаменателем р<1, следовательно, вероятность
— наибольшая. Это означает, что если СМО справляется с потоком заявок (при
), то наиболее вероятным будет отсутствие заявок в системе.
Среднее число заявок в системе определим по формуле математического ожидания:
(при p< 1).
Найдем среднее число заявок в очереди . Очевидно, что
где — среднее число заявок, находящихся под обслуживанием.
Среднее число заявок под обслуживанием определим по формуле математического ожидания числа заявок под обслуживанием, принимающего значения 0 (если канал свободен) либо 1 (если канал занят):
т.е. среднее число заявок под обслуживанием равно вероятности того, что канал занят:
В силу = p , тo
Доказано, что при любом характере потока заявок, при любом распределении времени обслуживания, при любой дисциплине обслуживания среднее время пребывания заявки в системе (очереди) равна среднему числу заявок в системе (в очереди), деленному на интенсивность потока заявок, т.е. среднее время пребывания заявки в системе определится по формуле:
Aсреднее время пребывания заявки в очереди — .