ГЛАВА 3. Вычислительные алгоритмы (методы вычислений характеристик сетей очередей)

3.1 Алгоритмы вычисления характеристик однородных замкнутых экспоненциальных сетей массового обслуживания

Рассмотренные в предыдущей главе методы исследования локально-сбалансированных сетей МО позволяют получать решение в удобной мультипликативной форме. Однако указанное решение зависит от нормализующей константы, имеющей относительно простой вид для открытых сетей МО, но представляющей собой сумму произведений для замкнутых сетей. Количество слагаемых в этой сумме соответствует мощности пространства состояний сети и даже для однородных замкнутых сетей составляет

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

Поэтому потребовалась разработка специальных методов вычисления стационарных вероятностей состояний и других характеристик замкнутых сетей МО, совокупность которых представляет собой отдельный раздел теории сетей МО.

Указанному разделу посвящены многочисленные работы [5,41,152,153,161,242], первая из которых появилась в 1971 г. Основой большинства из перечисленных алгоритмов является рекуррентный метод Бузена, названный в дальнейших работах алгоритмом свертки.

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

3.1.1 Метод Бузена

В соответствии с этим методом алгоритм расчета нормализующей константы

где множитель согласно (2.28), (2.36) имеет вид

а пространство состояний сети

сводится к простой итеративной процедуре, суть которой состоит в следующем.

Введем в рассмотрение функцию

Очевидно, что для . При имеем

Таким образом, для сети, состоящей из центров, интенсивность обслуживания которых зависит от нагрузки,

Если центр не зависит от нагрузки, то выражение (3.3) можно упростить. В этом случае

Подставляя (3.5) в выражение (3.3), после упрощений получаем

Формулы (3.6) и (3.3) позволяют осуществлять рекуррентное вычисление при начальных условиях . В таблицах. 3.1 и 3.2 дано схематическое описание алгоритма Бузена. Столбцы таблицы заполняются последовательно сверху вниз. Если центр не зависит от нагрузки, то элементы столбца вычисляются по формуле (3.6), в противном случае используется выражение (3.4) и для отыскания значений применяется рекуррентное выражение

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

Таблица 3.1

Для заполнения таблицы 3.1 требуется операций сложения и умножения; вычисления по таблице 3.1 требует арифметических операций. Заметим, что в соответствии с алгоритмом Бузена необходимо полностью сохранить столбец до тех пор, пока не вычислен последний элемент столбца т. Таким образом, этот алгоритм требует ячеек памяти для запоминания элементов Количество запоминаемых элементов можно сократить, если вычисление элементов столбца начинать с последнего элемента Если вычислено значение в таблице 3.2, то отпадает необходимость запоминания элемента так как в соответствии с (3.4) он не потребуется для вычисления . Следовательно, для вычисления элементов в этом случае необходимо запоминать элементов.

Таблица 3.2

Вычислительная эффективность алгоритма Бузена может быть улучшена, если заполнение строк в таблицах осуществлять по многомерной схеме Горнера, что позволяет сократить количество арифметических операций при вычислении до величины

Дальнейшее упрощение вычислительной процедуры возможно в частном случае сетей, зависящих от нагрузки, когда центр сети содержит одинаковых обслуживающих приборов. При этом интенсивность обслуживания m-го центра:

Последнее выражение можно записать в рекуррентном виде

где

Подставляя (3.7) в (3.3), получаем

После преобразований имеем окончательно

сети, не зависящей от нагрузки , выражение (3.8) совпадает с (3.6). Если , то

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

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

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