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

[GoodWind]

МОДЕЛИРОВАНИЕ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ
Основные понятия. Классификация СМО

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

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

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

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

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

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

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

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

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

Основные компоненты СМО

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

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

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

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

Функция плотности вероятности имеет вид:

а вероятность того, что за любой период Т поступит п требований вычисляется по формуле:

Все свойства и характеристики пуассоновского потока требований полностью определяются параметром λ.

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

Величина

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


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

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

Сообщение отредактировано: GoodWind - 17.02.2006 21:35

[GoodWind]

Одноканальная СМО с отказами

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



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



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



Обозначим:



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



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



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




В прикрепленном архиве представлена программа на Delphi, иллюстрирующая вышеприведенный метод.
 Odnokanalnaya_SMO_s_otkazami.zip ( 3.66 килобайт ) Кол-во скачиваний: 2695

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

[GoodWind]

Многоканальная СМО с отказами

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


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

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


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

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



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



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



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



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




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