Имитационное моделирование систем массового обслуживания

Содержание

Введение                   3

Общие положения                6

Действия  и события в системах                       8

Модельное время                                                                                                 10

Логическая  схема имитационной модели                                                         13

Список  использованных источников                                                                19

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

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

Система массового обслуживания считается заданной, если определены:

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

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

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

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

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

5) дисциплина  обслуживания, т. е. совокупность  правил, в соответствии с которыми требование выбирается из очереди для обслуживания. Наиболее часто на практике используются следующие правила:

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

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

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

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

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

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

Модель является средством для изучения сложных  систем.

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

1) Внешнее  проектирование

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

2) Внутреннее проектирование - проектирование отдельных элементов

системы

Типичным методом  исследования сложных систем на первом этапе является моделирование их на ЭВМ.

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

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Общие положения

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

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

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

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

1) розыгрыш  равномерно распределенного случайного  числа  xÎ[0,w];

2) определение  соответствующего значения  .

Единичная реализация этой элементарной имитационной модели из двух действий дает одно значение случайной величины Y. Если задача (цель) моделирования состоит в оценке среднего значения , то необходимо добавить в модель дополнительное (третье) действие S = S + y  для накопления суммы случайных величин (средство сбора) и многократно реализовать полученную модель. В конце моделирования в качестве оценки для принять отношение S/N (средство обработки), где N – общее число реализаций модели.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Действия и события в системах

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

Рассмотрим действия и события, имеющие  место в системах на примере СМО  типа G/G/1, где под состоянием системы понимается число заявок k, находящихся в ней в данный момент времени. Хронологическая последовательность действий и событий, имеющих место в общем случае в такой СМО при прохождении через систему одной заявки (одного элемента), представлена на рис.2.1.

Рис.2.1. Действия и события  в СМО.

Как видно  из рис. 2.1 не все события, возникающие в системе, являются равнозначными в том смысле, что не все события приводят к изменению состояния системы. Исходя из этого, различают два вида событий:

1) основные (особые) события;

2) вспомогательные (второстепенные) события. Основным событием называется событие, наступление которого приводит к изменению состояния системы.

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

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

Какие из перечисленных  на рис. 2.1 событий являются основными? Ответить на этот вопрос поможет утверждение: основные события всегда "связаны" с независимыми временными параметрами, необходимыми или задаваемыми для описания системы.

Для рассматриваемой  нами системы G/G/1  такими параметрами являются интервалы поступления и длительности обслуживания заявок. Очевидно, что по истечении интервала поступления и длительности обслуживания наступают соответственно события "прибытие заявки" и "окончание обслуживания". Именно эти два события и являются основными в рассматриваемой системе, и появление их вызывает очевидные переходы системы из состояния в состояние. Все другие события на рис.2.1 являются вспомогательными. Так, события "начало обслуживания" и "занятие прибора" являются следствием наступления либо события "приход заявки" (если система свободна), либо события "окончание обслуживания" (для предыдущей заявки). В свою очередь, события "освобождение прибора" и "уход из системы" являются следствием возникновения события "окончание обслуживания".