При решении многих экономических задач, программист часто сталкивается с системами, выполняющими определенную работу, в которой нуждаются объекты, обращающиеся в эту систему (например: касса магазина, АЗС). Такие системы называют системами массового обслуживания (СМО), а обращающиеся объекты – заявками.

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

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

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

СМО делятся на два основные типа:

1. СМО с отказами:

требование, поступившее в момент, когда все каналы обслуживания заняты, получает отказ и покидает СМО не обслуженным. Пример – телефонная станция.

2. СМО ожиданием:

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


Основными компонентами СМО являются:

1. Входной канал (прием заявок)
2. Система обслуживания
3. Очередь (для СМО с ожиданием)

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

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

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

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

Очередь, дисциплина очереди
Ожидающие обслуживания заявки образуют очередь. Правила, по которым из очереди выбирают заявки для обслуживания называют дисциплиной очереди.
Различают 5 видов дисциплины:

1. FIFO – первой поступила – первой обслужена
2. LIFO – последней поступила – первой обслужена
3. По срочности
4. По приоритетам
5. Случайный выбор.

Рассмотрим СМО с одним каналом обслуживания, в которую поступает поток заявок с интенсивностью λ. Интенсивность обслуживания одной заявки равна μ. Требуется найти предельные вероятности состояний системы и показатели ее эффективности. Система S в данном случае имеет 2 состояния: S0 — канал свободен и S1 канал занят. Нарисуем граф состояний системы, т.е. геометрическую схему, на которой состояние системы изображаются прямоугольниками, а переходы из состояния в состояние — стрелками:

Нажмите для просмотра прикрепленного файла

Для составления уравнения предельных состояний применяется правило: слева в уравнениях стоит предельная вероятность данного состояния рi, умноженная на суммарную интенсивность всех потоков, ведущих из данного состояния, а справа — сумма произведений интенсивностей всех потоков, входящих в состояние I, на вероятности тех состояний, из которых эти потоки выходят.
Для данного графа система уравнений для вероятностей состояний имеет вид:

Нажмите для просмотра прикрепленного файла

т.е. имеет одинаковые уравнения. Учитывая, что р1+р0=1, получаем систему:

Нажмите для просмотра прикрепленного файла

Обозначим:

Нажмите для просмотра прикрепленного файла

Величина "Альфа" называется интенсивностью загрузки канала. Она выражает среднее число заявок, приходящее за среднее время обслуживания одной заявки. Тогда из системы Нажмите для просмотра прикрепленного файла, с учетом формулы Нажмите для просмотра прикрепленного файла, получим выражения для предельных вероятностей состояний:

Нажмите для просмотра прикрепленного файла

р0 — вероятность того, что канал обслуживания свободен, т.е. характеризует относительную пропускную способность СМО.
р1 — вероятность того, что канал занят, т.е. вероятность отказа.
Абсолютная пропускная способность:

Нажмите для просмотра прикрепленного файла

Среднее число занятых обслуживанием каналов:

Нажмите для просмотра прикрепленного файла


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

Рассмотрим систему с n каналами, на которые поступает поток заявок с интенсивностью λ. Интенсивность обслуживания заявок каждым каналом равна μ. Требуется найти предельные вероятности состояний СМО и показатели ее эффективности. Эта задача называется классической задачей Эрланга. Система S (СМО) имеет следующие состояния S0,S1,S2,…,Sx,…,Sn, где состояние системы, когда в ней находится ki заявок, так как k каналов заняты обслуживанием.
Граф состояний СМО имеет вид:
Нажмите для просмотра прикрепленного файла

Поток заявок последовательно переводит СМО из любого левого состояния в соседнее правое с одной и той же интенсивностью λ. Интенсивность потока обслуживаний, переводящих систему из любого правого состояния в соседнее левое, постоянно меняется в зависимости от состояний. Например, если СМО находится в состоянии S2 (2 канала заняты), то она может перейти в состояние S1 (1 канал занят), когда закончит обслуживание либо первый, либо второй канал, т.е. суммарная интенсивность потока обслуживаний будет равна 2μ.

Аналогично, суммарный поток обслуживаний, переводящих СМО из состояния S3 в S2, будет иметь интенсивность 3μ, т.к. может освободиться любой из трех каналов, и т.д. Формулы для предельных вероятностей состояний имеют вид:
Нажмите для просмотра прикрепленного файла

Эти формулы называются формулами Эрланга.

Вероятность отказа СМО, т.е. вероятность того, что все n каналов будут заняты ("альфа" - интенсивность загрузки канала, см. выше):

Нажмите для просмотра прикрепленного файла

Относительная пропускная способность — это вероятность того, что заявка будет обслужена:

Нажмите для просмотра прикрепленного файла

Абсолютная пропускная способность:

Нажмите для просмотра прикрепленного файла

Среднее число занятых каналов:

Нажмите для просмотра прикрепленного файла

Запишем формулы Эрланга для двухканальной системы, т.е. когда n=2:

Нажмите для просмотра прикрепленного файла


ps: планировал-планировал сделать программу... не найду никак времени (( кто может, напишите...