Автор: GoodWind 17.02.2006 14:30
МОДЕЛИРОВАНИЕ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ
Основные понятия. Классификация СМО
При решении многих экономических задач, программист часто сталкивается с системами, выполняющими определенную работу, в которой нуждаются объекты, обращающиеся в эту систему (например: касса магазина, АЗС). Такие системы называют системами массового обслуживания (СМО), а обращающиеся объекты – заявками.
Элемент системы, в который поступают заявки, называют каналом или пунктом обслуживания. Соответственно, если в системе один канал, то систему называют одноканальной, если 2 или более – многоканальной.
На обслуживание одной заявки затрачивается определенное время, следовательно, в определенный момент времени на входе канала может либо находиться определенное количество заявок, либо вообще ни одной. В большинстве случаев предполагается, что известен некоторый вероятностный закон, управляющий поступлением заявок.
Цель решения СМО – минимизация затрат, связанных с простоем системы и затрат связанных с ожиданием заявок в очереди. СМО решается путем реформирования потоков заявок, либо определением оптимального количества каналов.
СМО делятся на два основные типа:
1. СМО с отказами:
требование, поступившее в момент, когда все каналы обслуживания заняты, получает отказ и покидает СМО не обслуженным. Пример – телефонная станция.
2. СМО ожиданием:
требование, поступившее в момент занятости всех каналов, становится в очередь и ожидает, когда освободится один из них. Пример – магазин, касса.
Основные компоненты СМО
Основными компонентами СМО являются:
1. Входной канал (прием заявок)
2. Система обслуживания
3. Очередь (для СМО с ожиданием)
Входной поток Для входного потока предполагается, что известен средний интервал между заявками.
Интенсивностью входного потока (количество заявок за единицу времени) называют величину равную
Величины λ и Т являются важными характеристиками входного потока. Величина Т определяет плотность потока, а λ — скорость поступления требований.
Функция плотности вероятности имеет вид:
а вероятность того, что за любой период Т поступит п требований вычисляется по формуле:
Все свойства и характеристики пуассоновского потока требований полностью определяются параметром λ.
Система обслуживания.Любая система обслуживания состоит одного или нескольких каналов, каждый из которых затрачивает на обслуживание определенное время, но среднее время обслуживания считается у всех одинаковым и равным t.
Величина
называется интенсивностью обслуживания. Она характеризует скорость работы канала и определяет среднее число требований, обслуживаемых каналом за единицу времени. Закон распределения обслуживания при одном и том же τ может быть различным, но чаще других встречается экспоненциальный закон. Функция плотности вероятности времени обслуживания имеет вид:
Очередь, дисциплина очередиОжидающие обслуживания заявки образуют очередь. Правила, по которым из очереди выбирают заявки для обслуживания называют дисциплиной очереди.
Различают 5 видов дисциплины:
1. FIFO – первой поступила – первой обслужена
2. LIFO – последней поступила – первой обслужена
3. По срочности
4. По приоритетам
5. Случайный выбор.
Автор: GoodWind 17.02.2006 19:02
Одноканальная СМО с отказами
Рассмотрим СМО с одним каналом обслуживания, в которую поступает поток заявок с интенсивностью λ. Интенсивность обслуживания одной заявки равна μ. Требуется найти предельные вероятности состояний системы и показатели ее эффективности. Система S в данном случае имеет 2 состояния: S0 — канал свободен и S1 канал занят. Нарисуем граф состояний системы, т.е. геометрическую схему, на которой состояние системы изображаются прямоугольниками, а переходы из состояния в состояние — стрелками:
Для составления уравнения предельных состояний применяется правило: слева в уравнениях стоит предельная вероятность данного состояния рi, умноженная на суммарную интенсивность всех потоков, ведущих из данного состояния, а справа — сумма произведений интенсивностей всех потоков, входящих в состояние I, на вероятности тех состояний, из которых эти потоки выходят.
Для данного графа система уравнений для вероятностей состояний имеет вид:
т.е. имеет одинаковые уравнения. Учитывая, что р1+р0=1, получаем систему:
Обозначим:
Величина "Альфа" называется интенсивностью загрузки канала. Она выражает среднее число заявок, приходящее за среднее время обслуживания одной заявки. Тогда из системы
, с учетом формулы
, получим выражения для предельных вероятностей состояний:
р0 — вероятность того, что канал обслуживания свободен, т.е. характеризует относительную пропускную способность СМО.
р1 — вероятность того, что канал занят, т.е. вероятность отказа.
Абсолютная пропускная способность:
Среднее число занятых обслуживанием каналов:
В прикрепленном архиве представлена программа на Delphi, иллюстрирующая вышеприведенный метод.
Odnokanalnaya_SMO_s_otkazami.zip ( 3.66 килобайт )
Кол-во скачиваний: 2156Внимание! В программе
нет контроля вводимых значений и все значения округляются до целых (для удобочитаемости результатов)
Автор: GoodWind 17.02.2006 21:24
Многоканальная СМО с отказами
Рассмотрим систему с n каналами, на которые поступает поток заявок с интенсивностью λ. Интенсивность обслуживания заявок каждым каналом равна μ. Требуется найти предельные вероятности состояний СМО и показатели ее эффективности. Эта задача называется классической задачей Эрланга. Система S (СМО) имеет следующие состояния S0,S1,S2,…,Sx,…,Sn, где состояние системы, когда в ней находится ki заявок, так как k каналов заняты обслуживанием.
Граф состояний СМО имеет вид:
Поток заявок последовательно переводит СМО из любого левого состояния в соседнее правое с одной и той же интенсивностью λ. Интенсивность потока обслуживаний, переводящих систему из любого правого состояния в соседнее левое, постоянно меняется в зависимости от состояний. Например, если СМО находится в состоянии S2 (2 канала заняты), то она может перейти в состояние S1 (1 канал занят), когда закончит обслуживание либо первый, либо второй канал, т.е. суммарная интенсивность потока обслуживаний будет равна 2μ.
Аналогично, суммарный поток обслуживаний, переводящих СМО из состояния S3 в S2, будет иметь интенсивность 3μ, т.к. может освободиться любой из трех каналов, и т.д. Формулы для предельных вероятностей состояний имеют вид:
Эти формулы называются формулами Эрланга.
Вероятность отказа СМО, т.е. вероятность того, что все n каналов будут заняты ("альфа" - интенсивность загрузки канала, см. выше):
Относительная пропускная способность — это вероятность того, что заявка будет обслужена:
Абсолютная пропускная способность:
Среднее число занятых каналов:
Запишем формулы Эрланга для двухканальной системы, т.е. когда n=2:
ps: планировал-планировал сделать программу... не найду никак времени (( кто может, напишите...