Главная > Математика > Исследование операций: задачи, принципы, методология
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

3. n-канальная СМО с неограниченной очередью.

Совершенно аналогично задаче 2, но чуточку более сложно, решается задача об n-канальной СМО с неограниченной очередью. Нумерация состояний — опять по числу заявок, находящихся в системе:

— в СМО заявок нет (все каналы свободны),

— занят один канал, остальные свободны,

— занято два канала, остальные свободны,

— занято k каналов, остальные свободны,

— заняты все каналов (очереди нет),

— заняты все каналов, одна заявка стоит в очереди,

— заняты все каналов, заявок стоит в очереди,

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

Рис. 20.3.

Граф рис. 20.3 есть схема гибели и размножения, но с бесконечным числом состояний. Сообщим без доказательства естественное условие существования финальных вероятностей: Если очередь растет до бесконечности.

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

(20.22)

Теперь найдем характеристики эффективности СМО. Из них легче всего находится среднее число занятых каналов (это вообще справедливо для любой СМО с неограниченной очередью).

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

(20.23)

Прибавляя к нему среднее число заявок под обслуживанием (оно же — среднее число занятых каналов) получим:

(20.24)

Деля выражения для на , по формуле Литтла получим средние времена пребывания заявки в очереди и в системе:

(20.25)

А теперь решим любопытный пример. Железнодорожная касса по продаже билетов с двумя окошками представляет собой двухканальную СМО с неограниченной очередью, устанавливающейся сразу к двум окошкам (если одно окошко освобождается, ближайший в очереди пассажир его занимает). Касса продает билеты в два пункта: А и В. Интенсивность потока заявок (пассажиров, желающих купить билет) для обоих пунктов А и В одинакова: (пассажира в минуту), а в сумме они образуют общий поток заявок с интенсивностью . Кассир тратит на обслуживание пассажира в среднем две минуты. Опыт показывает, что у кассы скапливаются очереди, пассажиры жалуются на медленность обслуживания. Поступило рационализаторское предложение: вместо одной кассы, продающей билеты и в А и в В, создать две специализированные кассы (по одному окошку в каждой), продающие билеты одна — только в пункт А, другая — только в пункт В. Разумность этого предложения вызывает споры — кое-кто утверждает, что очереди останутся прежними. Требуется проверить полезность предложения расчетом. Так как мы умеем считать характеристики только для простейших СМО, допустим, что все потоки событий — простейшие (на качественной стороне выводов это не скажется).

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

Вариант I (существующий). На двухканальную СМО поступает поток заявок с интенсивностью интенсивность потока обслуживаний . Так как , финальные вероятности существуют. По первой формуле (20.22) находим Среднее число заявок в очереди находим по формуле (20.23): среднее время, проводимое заявкой в очереди (по первой из формул (20.25)), равно (мин.).

Вариант II (предлагаемый). Надо рассмотреть две одноканальные СМО (два специализированных окошка); на каждую поступает поток заявок с интенсивностью по-прежнему равно финальные вероятности существуют. По формуле (20.20) находим среднюю длину очереди (к одному окошку)

Вот тебе и раз! Длина очереди, оказывается, не только не уменьшилась, а увеличилась! Может быть, уменьшилось среднее время ожидания в очереди? Посмотрим. Деля на получим (минут).

Вот так рационализация! Вместо того чтобы уменьшиться, и средняя длина очереди, и среднее время ожидания в ней увеличились!

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

— Ну, ладно, — готов согласиться читатель, — увеличение можно объяснить, но почему оно такое существенное? Нет ли тут ошибки в расчете?

И на этот вопрос мы ответим. Ошибки нет. Дело в том, что в нашем примере обе СМО работают на пределе своих возможностей; стоит немного увеличить время обслуживания (т. е. уменьшить ), как уже перестанут справляться с потоком пассажиров, и очередь начнет неограниченно возрастать.

А «лишние простои» кассира в каком-то смысле равносильны уменьшению его производительности

Таким образом, кажущийся сначала парадоксальным (или даже просто неверным) результат вычислений оказывается на поверку правильным и объяснимым.

Такого рода парадоксальными выводами, причина которых отнюдь не очевидна, богата теория массового обслуживания. Автору самому неоднократно приходилось «удивляться» результатам расчетов, которые потом оказывались правильными.

Размышляя над последней задачей, читатель может поставить вопрос так: ведь если касса продает билеты только в один пункт, то, естественно, время обслуживания должно уменьшиться, ну, не вдвое, а хоть сколько-нибудь, а мы считали, что оно по-прежнему в среднем равно 2 (мин.). Предлагаем такому придирчивому читателю ответить на вопрос: а насколько надо его уменьшить, чтобы «рационализаторское предложение» стало выгодным? Снова мы встречаемся хотя и с элементарной, но все же задачей оптимизации. С помощью ориентировочных расчетов даже на самых простых, марковских моделях удается прояснить качественную сторону явления — как выгодно поступать, а как — невыгодно. В следующем параграфе мы познакомимся с некоторыми элементарными немарковскими моделями, которые еще расширят наши возможности.

После того, как читатель ознакомился с приемами вычисления финальных вероятностей состояний и характеристик эффективности для простейших СМО (овладел схемой гибели и размножения и формулой Литтла), ему можно предложить для самостоятельного рассмотрения еще две простейшие СМО.

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