IPB
ЛогинПароль:

 
 Ответить  Открыть новую тему 
> Моделирование систем массового обслуживания
GoodWind
сообщение 17.02.2006 14:30
Сообщение #1


Автооответчик
*****

Группа: Модераторы
Сообщений: 1 188
Пол: Мужской
Реальное имя: Александр

Репутация: -  16  +


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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сообщение отредактировано: GoodWind - 17.02.2006 21:35
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
GoodWind
сообщение 17.02.2006 19:02
Сообщение #2


Автооответчик
*****

Группа: Модераторы
Сообщений: 1 188
Пол: Мужской
Реальное имя: Александр

Репутация: -  16  +


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


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

Прикрепленное изображение

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

Прикрепленное изображение

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

Прикрепленное изображение

Обозначим:

Прикрепленное изображение

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

Прикрепленное изображение

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

Прикрепленное изображение

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

Прикрепленное изображение


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

Внимание! В программе нет контроля вводимых значений и все значения округляются до целых (для удобочитаемости результатов)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
GoodWind
сообщение 17.02.2006 21:24
Сообщение #3


Автооответчик
*****

Группа: Модераторы
Сообщений: 1 188
Пол: Мужской
Реальное имя: Александр

Репутация: -  16  +


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


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

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

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

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

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

Прикрепленное изображение

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

Прикрепленное изображение

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

Прикрепленное изображение

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

Прикрепленное изображение

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

Прикрепленное изображение


ps: планировал-планировал сделать программу... не найду никак времени (( кто может, напишите...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 



- Текстовая версия 28.03.2024 21:42
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"