Главная > Математика > Численные методы Монте-Карло
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

1.3. Системы массового обслуживания.

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

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

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

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

Аналитические методы позволяют рассчитывать системы массового обслуживания только в простейших случаях. Во всех более сложных задачах приходится прибегать к статистическому моделированию [7, 38, 43].

1.3.1. Описание потока заявок.

Чаще других рассматривается стационарный пуассоновский поток, называемый также простейшим потоком, в котором интервалы между моментами поступления двух последовательных заявок независимы и подчиняются экспоненциальному распределению: и функция распределения О равна

Величина называется интенсивностью потока заявок.

Из более сложных стационарных потоков отметим только потоки Эрланга, в которых величины также независимы, но подчиняются более общему гамма-распределению (см. гл. 2, п. 4.2) с плотностью

Интенсивность такого потока равна

Сравнительно редко используют нестационарные пуассоновские потоки, в которых функция распределения зависит от

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

1.3.2. Алгоритм расчета системы с отказами.

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

Пусть в рассматриваемую систему поступает простейший поток заявок с интенсивностью а. Требуется оценить среднее число отказов за время

Поставим в соответствие линии с номером i ячейку ЭВМ, в которую будем записывать момент освобождения этой линии . В начальный момент, очевидно, . В отдельную ячейку будем записывать величину

Момент поступления первой заявки разыграем по формуле

Очевидно, первую заявку начнет обслуживать первая линия. Время обслуживания найдем из уравнения

Линия номер 1 будет занята до момента новое Следовательно, в соответствующей первой линии ячейке надо заменить на и вычислить новое

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

и проверяем, если ли свободные линии. Для этого доста точно проверить неравенство

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

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

б) Если неравенство (3) невыполнено, то свободных линий в момент 4 нет и система должна выдать отказ.

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

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

Рис. 57.

К этому времени в счетчике отказов будет стоять количество отказов за время

Повторив такой опыт N раз (с различными случайными числами), получим N значений , по которым можно оценить среднее число отказов за время . Схема обработки одной заявки изображена на рис. 57.

<< Предыдущий параграф Следующий параграф >>
Оглавление