Построение моделей систем массового обслуживания средствами пакета MATLAB+Simulink

Размещено на http://www.allbest.ru/

Построение моделей систем массового обслуживания средствами пакета MATLAB+Simulink

модель массовый обслуживание matlab

Введение

Целью настоящей работы является исследование средств инженерного программного пакета MATLAB для построения, отладки и тестирования моделей систем массового обслуживания (СМО).

Задачи практикума вытекают из следующих необходимостей.

С помощью пакета MATLAB и входящего в его состав комплекса Simulink необходимо построить модель и обеспечить возможность моделирования однофазной одноканальной СМО с ограниченной очередью и обратной связью. Потоки заявок и обслуживания должны иметь показательный закон распределения (в нотации СМО: M/M/1/10 [1]). Заявки в общем случае представляют собой сложные объекты, поэтому модель должна характеризовать каждую из них как минимум одним параметром (например, весом).

Для каждого эксперимента с моделью необходимо предусмотреть возможности задания следующих параметров:

количества заявок, подаваемых на вход СМО;

интенсивности потока заявок;

максимального веса заявок;

вероятности возврата заявок в очередь по обратной связи.

По окончании каждого эксперимента необходимо представить следующие результаты:

абсолютную пропускную способность системы;

среднее время пребывания заявки в системе;

полное время пребывания каждой заявки в системе (в динамике);

графики поступления и выхода заявок из системы;

среднюю длину очереди;

количество заявок в очереди (в динамике);

коэффициент загрузки системы.

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

1. Выбор и обоснование инструментальных средств

Инженерный программный пакет MATLAB включает в себя множество средств для построения моделей в самых разных предметных областях. Одним из таких средств является инструмент StateFlow, входящий в состав комплекса Simulink. StateFlow изначально предназначен для построения моделей реактивных систем (или конечных автоматов), характеризующихся множеством состояний, в которые система переходит при наступлении определенных событий. Существуют приемы [2, 3], позволяющие успешно использовать этот инструмент для моделирования СМО. Однако его применение в этих целях сопряжено с рядом трудностей, главными из которых являются следующие факты:

представление СМО в виде конечного автомата не очевидно и не однозначно (в частности, моделирование СМО с бесконечной очередью [4] (абстракция), может стать невозможным);

переход конечного автомата из состояния в состояние не предполагает передачи какой-либо информации, в то время как почти всякое изменение в СМО сопровождается передачей какой-либо информации в/из/внутри системы;

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

В связи с перечисленными трудностями для решения поставленной задачи был выбран другой инструмент, также входящий в состав Simulink - библиотека SimEvents. Эта библиотека представляет собой набор блоков Simulink, предназначенных для моделирования систем дискретных событий (Discrete Event System, DES). Процесс построения моделей средствами SimEvents лишен недостатков, присущих StateFlow и перечисленных выше. Кроме того, эта библиотека обладает рядом полезных свойств и функций:

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

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

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

Перечисленные особенности определяют выбор библиотеки SimEvents в качестве основного инструментального средства (наряду с MATLAB и Simulink) для решения поставленной задачи.

2. Ход выполнения работы

2.1 Анализ основных требований

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

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

Описанные требования позволяют в общих чертах обозначить функциональную схему проектируемой модели, а возможность использования иерархических блоков (подсистем) в Simulink - начать составление этой схемы (рисунок 1).

Рисунок 1 - Схема проектируемой модели в первом приближении

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

2.2 Подсистема Канала обслуживания

Для упрощения описания функциональная схема канала обслуживания приведена на рисунке 2.

Рисунок 2 - Схема подсистемы канала обслуживания

Основным элементом подсистемы является собственно канал обслуживания (в терминологии SimEvents - сервер). Он принимает на вход заявку и "обслуживает" (задерживает) ее на заданный период времени. Длительность периода может задаваться как свойство блока, а может быть передана ему как входной сигнал. Последний вариант применен в данной работе. Источником сигнала времени задержки является подсистема Генератор времени обслуживания. Необходимость выделения отдельной подсистемы для Генератора продиктована необходимостью сформировать сигнал, величина которого, согласно заданию, случайна и распределена по показательному закону [5]. Кроме того, также согласно заданию, в блоке учитывается вес пришедшей заявки. Этот учет проявляется в суммировании сгенерированного времени обслуживания и веса заявки. Схема Генератора приведена на рисунке 3.

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

Входным параметром для рассмотренного Генератора является вес заявки, передаваемый как ее атрибут и извлекаемый соответствующим блоком на входе всей подсистемы канала обслуживания (см. рисунок 2).

Рисунок 3 - Схема генератора времени обслуживания

В проектируемой модели для каждой обслуженной заявки необходимо решить вопрос: будет ли заявка передана на выход, или она должна быть возвращена в очередь и, пройдя ее, вновь поступить на обслуживание? Согласно заданию, ответ должен быть случайным, но с заданной вероятностью. Для простоты положим, что "решающая" величина имеет равномерный закон распределения и лежит в диапазоне от 0 до 1 - это позволит легко задавать пороговую вероятность возврата заявки в очередь. Именно такой подход реализован в канале обслуживания (рисунок 2). Выходной сигнал схемы "принятия решений" представляет собой индекс вывода Выходного переключателя. Этот блок в зависимости от полученного сигнала отправит пришедшую в него заявку либо на вывод 1 (обратно в очередь), либо на вывод 2 (далее в приемник).

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

2.3 Подсистема Очереди

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

Главным элементом этой подсистемы является блок очереди из библиотеки SimEvents. Он реализует очередь сущностей (заявок) заданной емкости с дисциплиной обслуживания FIFO. Емкость очереди согласно заданию равна 10 и задана как свойство блока. Дисциплина обслуживания выбрана такой лишь из соображений упрощения модели. Блок принимает на вход заявку, ставит ее в конец очереди, а заявку, стоящую в начале очереди (ею может быть и только что пришедшая), отправляет на выход, если он не заблокирован. Кроме того, в данной модели блок очереди является ценным источником разнообразной информации. Он в каждый момент опроса сообщает свое содержимое (количество заявок в очереди, ее длину), среднюю длину очереди и среднее время ожидания каждой заявки в очереди. Последняя характеристика не представляет особого интереса и потому отражается лишь на "локальном" осциллографе в отладочных целях.

Рисунок 4 - Схема подсистемы очереди

Заявки в очередь могут поступать не только из источника заявок, но и по обратной связи из канала обслуживания. Однако очередь имеет лишь один вход. Решением проблемы является блок Объединителя путей, который направляет заявки с обоих своих входов на один выход. Настройки блока таковы, что если две заявки прибудут в блок одновременно, на выход первой поступит заявка, пришедшая на вход IN1. Счетчик вернувшихся заявок и соответствующий дисплей оставлены лишь в отладочных целях для верификации схемы "принятия решений" в канале обслуживания.

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

2.4 Подсистема Источника заявок

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

Ключевым элементом этой подсистемы является Формирователь заявок - блок из библиотеки SimEvents. Его настройки позволяют указывать интервал между заявками как свойство самого блока, так и через входной сигнал. В данной модели интервал для Формирователя задает Генератор времени между заявками, схема которого представлена на рисунке 6.

Блок аналогичен Генератору времени обслуживания в подсистеме канала обслуживания. Отличия заключаются лишь в задании интенсивности потока в качестве входа подсистемы и в наличии участков контроля границ (позаимствованы из демонстрационных примеров к библиотеке SimEvents).

Рисунок 5 - Схема подсистемы Источника заявок

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

Согласно заданию, у каждой заявки должно быть некоторое собственное свойство. В проектируемой модели таким свойством является вес заявки. Его смысл проявляется в увеличении времени обслуживания заявки с большим весом. Другим применением этого параметра могло стать распределение приоритетов в "блатной" очереди в соответствии с весами поступивших в нее заявок. Чтобы веса у заявок были разными, но подчинялись пользователю модели, предусмотрен простой генератор весов заявок. Он генерирует равномерно распределенное случайное число от 0 до 1, которое умножается на заданный максимальный вес, обеспечивая тем самым и случайность этого параметра, и "подчиненность" его пользователю. В частности, влияние веса на процесс моделирования может быть исключено установкой слайдера максимального веса на значение 0.

Рисунок 6 - Схема Генератора интервала между заявками

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

Логическим завершением рассмотрения блоков СМО является детализации блока Приемника заявок.

2.5 Подсистема Приемника заявок

Функциональная схема подсистемы Приемника заявок представлена на рисунке 7.

Конечным пунктом назначения любой заявки является блок библиотеки SimEvents, обозначенный как Приемник заявок. Он "подавляет" в себе заявку и сообщает в виде сигнала количество пришедших в него заявок. Это количество сравнивается с заданным перед экспериментом количеством заявок. Их совпадение говорит о том, что все заявки, сгенерированные и незаблокированные в источнике, прошли обслуживание. При выполнении этого условия моделирование можно остановить.

Рисунок 7 - Схема подсистемы Приемника заявок

Для определения абсолютной пропускной способности СМО необходимо разделить количество заявок, прошедших обслуживание в СМО, на время, прошедшее с момента начала моделирования. Однако в начале время равно нулю. Чтобы избежать ошибки, в течение первого шага моделирования ненулевое значение поддерживается блоком Ступенька; затем он переключается в 0 и на делитель поступает только сигнал времени. Количество же обслуженных заявок доставляется блоком считывания таймера. Этот же блок предоставляет информацию о времени полного цикла каждой заявки, а также о среднем времени нахождения заявок в системе.

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

2.6 Обобщение модели и подготовка к моделированию

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

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

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

Общая схема построенной модели и ее интерфейсов представлена на рисунке 8.

Таким образом, была построена модель СМО, характеризующаяся следующими параметрами (таблица 1).

Таблица 1 - Параметры моделируемой СМО

Потоки заявок и обслуживания, с которыми работает моделируемая СМО, описываются следующими параметрами (таблица 2).

Таблица 2 - Параметры потоков заявок и обслуживания

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

Рисунок 8 - Общая схема построенной модели

Обладая приведенными выше данными, можно приступать к моделированию спроектированной СМО.

2.8 Моделирование

Чтобы убедиться в правильности построения модели, следует начать ее проверку с какого-нибудь тривиального эксперимента, результаты которого легко определить априори. В качестве такого эксперимента укажем модели интенсивность входного потока, равную 1. Максимальный вес заявки установим в 0, чтобы исключить влияние веса на время обслуживания. Кроме того, укажем вероятность возврата равной 0, опять же чтобы оценить лишь "чистое" время обслуживания и простоя в очереди. Число заявок установим равным 10.

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

Графики результатов моделирования с перечисленными выше параметрами представлены на рисунке 9.

Рисунок 9 - Графики результатов первого эксперимента

Кроме того, дисплеи, используемые в модели, в результате эксперимента показали, что абсолютная пропускная способность системы составила 1.1 (заявки/с), среднее время пребывания заявки в системе - 2.182 с, средняя длина очереди составила 1.604 заявок.

По двум верхним графикам рисунка 9 можно проследить общую динамику процесса, происходившего в системе. В первые примерно 0.8с источник заявок бездействовал; простаивал и канал обслуживания. Однако сразу после этого источник начал интенсивно генерировать заявки, и все из вновь сгенерированных заявок, кроме первой, заняли места в очереди. Это обусловило рост их числа в очереди на нижнем правом графике. Интенсивность потока обслуживания в этот период, по всей видимости, отклонилась в меньшую сторону, однако канал продолжал работать, о чем говорит спад числа заявок в очереди в момент времени ~1.8 с. Другим подтверждением служит равномерность роста числа обслуженных заявок (левый верхний график) в период, когда на входе наблюдался явный перерыв (~3-5c). Небольшое различие в моментах поступления и выхода последней заявки говорит о близости или равенстве интенсивностей потоков заявок и обслуживания (в данной случае, очевидно, равенстве).

Для верификации остальных возможностей модели сделаем вес заявок ненулевым. Зададим поток из 25 заявок с интенсивностью 0.5 заявок/с и максимальным весом 4. Очевидно, что без учета веса такой поток заставил бы канал обслуживания бездействовать существенную часть времени моделирования (в пределе - половину этого времени). Однако введение веса заявок увеличит время обслуживания каждой из них на некоторую случайную величину, не превышающую максимального веса. В результате это должно дать "запаздывание" последней заявки на период, сопоставимый с числом поступивших заявок. Результаты моделирования с такими параметрами представлены на рисунке 10. Очередь в процессе моделирования не переполнялась, поэтому кривую обслуженных заявок можно считать неискаженной.

Рисунок 10 - Результаты моделирования с учетом весов заявок

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

В модели осталась еще одна не проверенная особенность - наличие обратной связи между каналом обслуживания и очередью. В предыдущих экспериментах ее влияние было исключено указанием нулевой вероятности возврата. В третьем эксперименте она будет задействована. Для этого укажем максимальный вес заявки равным нулю (чтобы не "загромождать" результаты его учетом), а вероятность возврата установим равной 0.5. Необходимо сразу отметить, что модель не различает заявок, уже возвращенных по обратной связи ранее. Для его каждому экземпляру заявки необходимо присвоить соответствующий признак (что может быть легко реализовано с помощью атрибутов сущностей библиотеки SimEvents). В связи с этим, каждая заявка может быть возвращена более одного раза. Составим поток входящих заявок из 20 штук с интенсивностью 0.9. Как и в первом эксперименте, такие параметры (без учета возможности возврата) должны привести к равномерной нагрузке на канал и общее время обслуживания почти совпало бы с периодом поступления заявок. Однако введение обратной связи существенно меняет представленную картину. Результаты моделирования с указанными параметрами представлены на рисунке 11.

Рисунок 11 - Результаты моделирования с учетом обратной связи

Первое, на что следует обратить внимание в представленных графиках, это существенное различие в общих временах поступления и обслуживания. Кроме того, на графике обслуженных заявок можно видеть несколько "пауз". Каждая из них говорит о том, что заявка (или даже несколько подряд), прошедшая обслуживание в канале, была вместо приемника заявок направлена снова в очередь. Об этом также свидетельствуют скачки числа заявок в очереди в моменты времени, соответствующие выходам обслуженных заявок из канала обслуживания. Кроме того, число "фронтов" (в том числе и мгновенных) на графике содержимого очереди получилось равным 35, в то время как число заявок в эксперименте всего 20. Это говорит о том, что всего по обратной связи в очередь вернулись 15 (не обязательно различных) заявок. Подтверждением этой цифре служат показания соответствующего дисплея в подсистеме очереди. Таким образом, полученные результаты можно считать адекватными.

Эксперименты с более сложными комбинациями параметров могут быть проинтерпретированы схожим образом.

3. Пути совершенствования модели

Не вызывает сомнений тот факт, что построенная модель является по многим параметрам примитивной. Однако за счет выбранной идеологии построения и инструментальных средств MATLAB+Simulink+SimEvents она может быть улучшена во многих направлениях. Обозначим основные из них и пути их достижения:

увеличение числа каналов - может быть достигнуто как размножением каналов нынешней модели, так и использованием специальных блоков библиотеки SimEvents;

увеличение числа фаз - путем копирования основного блока СМО и внесения некоторых корректировок в расчеты характеристик;

изменение емкости очереди - путем простого изменения параметра блока очереди на желаемое значение (в том числе бесконечность);

изменение распределения интенсивности потоков заявок/обслуживания - заменой/модификацией нынешних блоков расчета;

изменение дисциплины обслуживания в очереди - заменой блока очереди на желаемый (в том числе, с приоритетами);

ограничение времени нахождения заявок в системе - с помощью параметров Time-Out блоков библиотеки SimEvents;

введение задержки на пути обратной связи для возвращенных заявок - путем вставки в обратную связь модуля сервера SimEvents с постоянным (или требуемым) временем обработки;

придание заявкам дополнительных свойств, параметров - при помощи введения дополнительных атрибутов заявок (атрибуты могут быть любого типа);

введение множественных связей (типа 1:n и n:1) для многоканальных многофазных систем - путем использования блоков Path Combiner (n:1) и Path Splitter (1:n).

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

Заключение

Инженерный программный пакет MATLAB включает в свой состав инструментальные средства, позволяющие строить, моделировать и отлаживать модели СМО. Эти средства представлены комплексом Simulink и входящей в его состав библиотекой блоков SimEvents.

Блоки библиотеки SimEvents являются мощным, гибким, но легким в освоении инструментом для описания моделей СМО.

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

Список литературы

1. Системы и модели массового обслуживания в коммерческой деятельности. Учеб. пособие для вузов по экон. спец./Г. П. Фомин. - М.: Финансы и статистика, 2007 - 144 с.

2. Вокруг форумов сайтов Exponenta.ru и Matlab.ru/Математика в приложениях, №2(6) 2004 г. - httpHYPERLINK "http://exponenta.ru/"://HYPERLINK "http://exponenta.ru/"exponentaHYPERLINK "http://exponenta.ru/".HYPERLINK "http://exponenta.ru/"ru

3. Справочные материалы по пакету MATLAB R2008a (http://mathworks.com)

4. Исследование операций. Задачи, принципы, методология. Учеб. пособие для студ. втузов/Е. С. Вентцель.-4-е изд., стер. - М.: Высш.шк., 2007. - 208 с.

5. Теория вероятностей и математическая статистика: Учеб. пособие для вузов/В. Е. Гмурман. - 9-е изд., стер. - М. Высш. шк., 2003. - 479 с.

Размещено на Allbest.ru