Автор: Ю.И.Рыжиков

           1.      Применения теории очередей

 

Пакет прикладных программ МОСТ (Массовое Обслуживание – СТационарные задачи) предназначен для расчета систем и сетей с очередями и реализует итоги почти полувековой работы автора – теперь на современном Фортране (F90 и последующие версии). Область потенциального применения теории очередей практически безгранична: в технике
связи, на транспорте, в промышленности, в автоматизированных системах, в торговле в здравоохранении, в службе быта, в органах юстиции и внутренних дел и
МЧС, в сфере науки и образования в издательском деле, в военном деле.

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

2. Пакеты программ для теории очередей 

• Сложность решения нетривиальных задач ТМО и разрыв в математической подготовке теоретиков и практиков сравнительно рано (середина 1960-х гг.) сделали эти задачи объектом усилий программистов. Впечатляет география появления уже первых пакетов: США, Пуэрто-Рико, Европа, СССР, Средний Восток, Япония и Южная Африка.

В монографии Bolch’а (2006) дается комментированный разбор описаний нескольких новых ППП (PEPSY, SPNP, MOSES, SHARPE) для расчета систем с очередями; приведены ссылки на первоисточники, примеры использования и скриншоты. Сопоставление названных пакетов затруднительно, поскольку опубликованные сведения о них неполны и имеют преимущественно рекламный характер.

 

3. История МОСТа

Пакет МОСТ предназначен для анализа проектируемых и эксплуатируемых систем обслуживания. Пакет может применяться в учебном процессе вузов и курсов повышения квалификации инженеров при проведении учебно-исследовательских работ по дисциплинам, связанным с ТМО, выполнении курсовых, дипломных и диссертационных работ. Стимулом для начала работ над МОСТом стало появление численных методов расчета сложных одноканальных и многоканальных фазовых систем и на этой основе – потребность в оценке влияния вида исходных распределений на показатели качества обслуживания.
Первая версия пакета на Алголе 60 в составе 18 процедур была разработана в 1977г. Затем он был переведен на язык ПЛ/1 применительно к ЕС ЭВМ, существенно расширен и передан в Государственный фонд алгоритмов и программ (Таллиннский НУЦ). В эту версию входили 83 функциональные процедурыУже в 1988 г. пакет эксплуатировался приблизительно в 30 организациях.

            Перенос пакета на ПЭВМ оказался возможным только после появления для них версий Фортрана 90, поддерживающих динамическое распределение памяти. МОСТ прошел через несколько волн обновления.
Текущая версия МОСТа позволяет решать широкий круг задач по расчету систем и сетей с очередями – с немарковскими исходными распределениями, различным числом каналов и разными дисциплинами обслуживания.

4. Теоретические основы пакета и элементы новизны

Теоретические основы пакета описаны в монографии «Алгоритмический подход к задачам массового обслуживания» (СПб.: ВКА им. А.Ф. Можайского, 2013). Ими являются:

• • Аппроксимация исходных распределений по методу моментов.

• • Законы сохранения теории очередей.

• Потокоэквивалентная декомпозиция сетей обслуживания.

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

 

5. Структура МОСТа и работа с ним

 

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

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

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

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

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

• • заголовок,

• • объявления переменных,

• • препроцессорные операторы интерфейса вызываемых модулей,

• • задание исходных данных,

• • операторы вызова модулей пакета,

• • дополнительные нестандартные фрагменты,

• вывод результатов.

Составление программы начинается с построения цепочки вызовов модулей. Например, для расчета распределения времени пребывания заявки в n-канальной системе следует применить цепочку

HYPER3 – MH2N – MFACT – MTIME – CONV –FCWEIB

Здесь HYPER3 по трем моментам распределения времени обслуживания подбирает параметры Н2-аппроксимации его, MH2N рассчитывает распределение числа заявок в системе M/H2/n, MFACT – факториальные моменты распределения длины очереди, MTIME – моменты распределения времени ожидания. CONV выполняет их свертку с исходными моментами распределения длительности чистого обслуживания, а FCWEIB через ее результаты табулирует ДФР распределения времени пребывания для заданных значений аргумента.

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

Доступ на внутренний уровень пакета (служебные и вспомогательные процедуры) существенно облегчает решение новых типов задач.

Пакет МОСТ/F90 включает в себя:

• • статическую библиотеку из 180 объектных модулей (3.2 Мбайта);

• • каталог пакета – 11 функциональных групп (базовые – для расчета конкретных систем, аппроксимационные – для расчета параметров исходных распределений, математические – для общематематических подзадач, служебные – для специальных вероятностных  и т. д.) с указанием назначения, особенностей использования  и параметров каждой процедуры;

• • библиотеку INTERFACE-блоков;

• • библиотеку из 120 тестов на Фортране 90;

• • библиотеку результатов тестирования;

• файл с прототипами операторов вызова.

Каждый расчет выполняется в виде проекта Фортрана 90. В проект включаются вызывающая программа и упомянутая статическая библиотека. После компиляции и линкования («Building») система формирует 32-разрядное приложение, запуск которого дает результаты счета. Формат и адресация вывода задаются программистом.

6. Автоматизированный МОСТ

Расширение круга пользователей МОСТа вовлечет в него лиц с программистской и теоретической подготовкой, недостаточной для работы на профессиональном уровне. Для таких пользователей С.В. Кокориным разработана автоматизированная версия пакета – MOCT/А. Она позволяет рассчитывать разомкнутые и замкнутые системы и сети обслуживания по исходным данным, вводимым в процессе диалога, с учетом трех моментов исходных распределений (с согласия пользователя MOCT/А по двум моментам подберет третий).