І. Теория массового обслуживания, определение, классификация, показатели эффективности.

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

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

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

Под потоком событий понимают последовательность однородных событий, следующих одна за другой в какие-то случайные моменты времени (например, поток вызовов на телефонной станции, поток отказов БВМ, поток покупателей и т.п.).Поток характеризуется интенсивностью λ - частотой появления события или средним числом событий, которые поступают в систему массового обслуживания за единицу времени.

В качестве показателей эффективности систем массового обслуживания могут использоваться следующие:

- Среднее (здесь и далее среднее как математическое ожидание соответствующих случайных величин) число заявок, обслуживаемых в единицу времени;

- Среднее количество заявок в очереди;

- Среднее время ожидания на обслуживание;

- Вероятность отказа в обслуживании без ожидания;

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

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

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

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среднее время пребывания заявки в очереди — .