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

Четвериков С. Ю. , Попов М.А.

Россия, Институт экономики и предпринимательства (г. Москва)

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

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

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

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

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

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

В противном случае с течением времени требования будут накапливаться в системе.

Параметры X и ц имеют простой физический смысл:

X - среднее число поступающих за единицу времени требований или интенсивность входящего потока;

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

/7ц - среднее число требований, которое способны обслужить п приборов, или интенсивность обслуживания требовании всей системой.

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

Так называемую загрузку системы.

Тогда неравенство (1) можно переписать в виде:

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

Наконец, еще одно замечание к функционированию системы с детерминированными характеристиками:

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

в случае р

наконец, если р > 1, то за единицу времени очередь в среднем увеличивается на Мр-1).

В реальных системах массового обслуживания существенную роль играют элементы случайности:

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

во-вторых, не являются детерминированными времена обслуживания требований.

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

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

Рассмотрим формализованное описание СМО. Основными параметрами СМО являются:

входящий поток требований;

структура системы;

временные характеристики обслуживания требований;

дисциплина обслуживания.

Рассмотрим эти параметры.

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

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

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

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

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

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

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

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

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

Тем не менее, в СМО используются и более сложные дисциплины обслуживания. Простейшими примерами таких дисциплин являются инверсионный (обратный) порядок обслуживания (LIFO), при котором обслуживается требование, поступившее в систему последним.

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

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

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

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

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

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

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

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

Литература

• 1. Гнеденко Б.В. Курс теории вероятностей. М.: Физматгиз, 1961.
• 2. Феллер В. Введение в теорию вероятностей и ее приложения.T.I. М.: Мир,
• 1984.
• 3. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. М.: Наука, 1966.
• 4. Саати Т.Л. Элементы теории массового обслуживания и ее приложения. М.: Сов. радио, 1965.

Курсовая работа

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

по курсу «Исследование операций»

Введение

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

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

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

– Абсолютная пропускная способность системы (А

Q

– вероятность отказа обслуживания заявки ();

k );

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

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

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

1. Основные характеристики CМОи показатели их эффективности

1.1 Понятие марковского случайного процесса

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

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

Процесс работы СМО – это случайный процесс с дискретными состояниями и непрерывным временем.

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

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

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

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

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

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

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

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

Поток событий называется простейшим (или стационарным пуассоновским), если он одновременно стационарен, ординарен и не имеет последействия.

1.2 Уравнения Колмогорова

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

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

Например, для графа состояний, приведенного на рис. 1, уравнения Колмогорова имеют вид:

Т.к. в правой части системы каждое слагаемое входит 1 раз со знаком и 1 раз со знаком , то, складывая все уравнений, получим, что

,

,

Следовательно, одно из уравнений системы можно отбросить и заменить уравнением (1.2.1).

Чтобы получить конкретное решение надо знать начальные условия, т.е. значения вероятностей в начальный момент времени.

1.3 Финальные вероятности и граф состояний СМО

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

Смысл финальных вероятностей состоит в том, что они равны среднему относительному времени нахождения системы в данном состоянии.

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

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

Рис. 2. Граф состояний в моделях СМО

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

Получается система из ( n +1) уравнения, которая решается методом исключения. Этот метод заключается в том, что последовательно все вероятности системы выражаются через вероятность .

,

.

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

1.4 Показатели эффективности СМО

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

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

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

– вероятность отказа (), т.е. вероятность того, что заявка покинет СМО не обслуженной;

– среднее число занятых каналов (k );

– среднее число заявок в СМО ();

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

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

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

– среднее время пребывания заявки в очереди ();

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

– степень загрузки канала (), т.е. вероятность того, что канал занят;

– среднее число заявок, обслуживаемых в единицу времени;

– среднее время ожидания обслуживания;

– вероятность того, что число заявок в очереди превысит определенное значение и т.п.

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

(1.4.1)

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

Формулы для вычисления показателей эффективности приведены в таб. 1.

Таблица 1.

Показатели	Одноканальная СМО с ограниченной очередью	Многоканальная СМО с ограниченной очередью
Финальные вероятности
Вероятность
Абсолютная пропускная способность
Относительная пропускная способность
Среднее число заявок в
Среднее число заявок под обслуживанием
Среднее число заявок в системе

1.5 Основные понятия имитационного моделирования

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

Компьютерное имитационное моделирование следует рассматривать как статический эксперимент.

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

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

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

1.6 Построение имитационных моделей

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

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

Характеристики самого процесса массового обслуживания могут изменять свои значения либо в момент поступления новой заявки на обслуживание, либо при завершении обслуживания очередной заявки. К обслуживанию очередной заявки СМО может приступить немедленно (канал обслуживания свободен), но не исключена необходимость ожидания, когда заявке придется занять место в очереди (СМО с очередью, канал обслуживания занят). После завершения обслуживания очередной заявки СМО может сразу приступить к обслуживанию следующей заявки, если она есть, но может и простаивать, если таковая отсутствует. Необходимую информацию можно получить, наблюдая различные ситуации, возникающие при реализациях основных событий. Так, при поступлении заявки в СМО с очередью при занятом канале обслуживания длина очереди увеличивается на 1. Аналогично длина очереди уменьшается на 1, если завершено обслуживание очередной заявки и множество заявок в очереди не пусто.

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

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

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

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

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

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

2) при фиксированной длительности времени Т имитационного моделирования провести N вычислительных экспериментов, называемых еще прогонами модели, с различными наборами псевдослучайных чисел, каждый из которых дает одно наблюдение. Все прогоны начинаются при одном и том же начальном состоянии моделируемой системы, но с использованием различных наборов псевдослучайных чисел. Преимуществом этого метода является независимость получаемых наблюдений , показателей эффективности системы. Если число N модели достаточно велико, то границы симметричного доверительного интервала для параметра определяются следующим образом:

, , т.е. , где

Исправленная дисперсия, ,

N – число прогонов программы, – надежность, .

2. Аналитическое моделирование СМО

2.1 Граф состояний системы и уравнения Колмогорова

Рассмотрим двухканальную систему массового обслуживания (n = 2) с ограниченной очередью равной шести (m = 4). В СМО поступает простейший поток заявок со средней интенсивностью λ = 4,8 и показательным законом распределения времени между поступлением заявок. Поток обслуживаемых в системе заявок является простейшим со средней интенсивностью μ = 2 и показательным законом распределения временем обслуживания.

Данная система имеет 7 состояний, обозначим их:

S 0 – система свободная, нет заявок;

S 1 – 1 заявка на обслуживании, очередь пуста;

S 2 – 2 заявки на обслуживании, очередь пуста;

S 3 – 2 заявки на обслуживании, 1 заявка в очереди;

S 4 – 2 заявки на обслуживании, 2 заявки в очереди;

S 5 – 2 заявки на обслуживании, 3 заявки в очереди;

S 6 – 2 заявки на обслуживании, 4 заявки в очереди;

Вероятности прихода системы в состояния S 0 , S 1 , S 2 , …, S 6 соответственно равны Р 0 , Р 1 , Р 2 , …, Р 6 .

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

Рис. 3. Граф состояний двухканальной СМО

Для построенного графа запишем уравнения Колмогорова:

Чтобы решить данную систему зададим начальные условия:

Систему уравнений Колмогорова (систему дифференциальных уравнений) решим численным методом Эйлера с помощью программного пакета Maple 11 (см. Приложение 1).

Метод Эйлера

где- в нашем случае, это правые части уравнений Колмогорова, n=6.

Выберем шаг по времени . Предположим , где Т – это время, за которое система выходит на стационарный режим. Отсюда получаем число шагов . Последовательно N раз вычисляя по формуле (1) получим зависимости вероятностей состояний системы от времени, приведенной на рис. 4.

Значения вероятностей СМО при равны:

Рис. 4. Зависимости вероятностей состояний системы от времени

P 0

P 5

P 4

P 3

P 2

P 1

2.2 Финальные вероятности системы

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

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

Решим данную систему линейных уравнений с помощью программного пакета Maple 11 (см. Приложение 1).

Получим финальные вероятности системы:

Сравнение вероятностей, полученных из системы уравнений Колмогорова при , с финальными вероятностями показывает, что ошибки равны:

Т.е. достаточно малы. Это подтверждает правильность полученных результатов.

2.3 Расчет показатели эффективности системы по финальным вероятностям

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

Сначала вычислим приведенную интенсивность потока заявок:

1) Вероятность отказав обслуживании заявки, т.е. вероятность того, что заявка покидает систему не обслуженной.В нашем случае заявке отказывается в обслуживании, если все 2 канала заняты, и очередь максимально заполнена (т.е. 4 человек в очереди), это соответствует состоянию системы S 6 . Т.к. вероятность прихода системы в состояние S 6 равна Р 6 , то

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

5) Среднее время пребывания заявки в очередиопределяется формулой Литтла:

3. Имитационное моделирование СМО

3.1 Алгоритм метода имитационного моделирования СМО (пошаговый подход)

Рассмотрим двухканальную систему массового обслуживания (n = 2) с максимальной длиной очереди равной шести (m = 4). В СМО поступает простейший поток заявок со средней интенсивностью λ = 4,8 и показательным законом распределения времени между поступлением заявок. Поток обслуживаемых в системе заявок является простейшим со средней интенсивностью μ = 2 и показательным законом распределения временем обслуживания.

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

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

Где (3.1.1)

Исходя из условия (3.1.1) определим шаг по времени .

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

Рассмотрим поступление заявки в СМО. Вероятность того, что на интервале в СМО поступит заявка, равна: . Сгенерируем случайное число , и, если , то будем считать, что заявка на данном шаге в систему поступила, если , то не поступила.

В программе это осуществляет isRequested () . Интервал времени примем постоянным и равным 0,0001, тогда отношение будет равно 10000. Если заявка поступила, то она принимает значение «истина», в противном случае значение «ложь».

bool isRequested()

double r = R. NextDouble();

if (r < (timeStep * lambda))

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

double GetServiceTime()

double r = R. NextDouble();

return (-1/mu*Math. Log (1-r, Math.E));

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

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

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

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

3.2 Блок-схема программы

Блок-схема программы, реализующей описанный алгоритм, приведена на рис. 5.

Рис. 5. Блок-схема программы

Распишем некоторые блоки более подробно.

Блок 1. Задание начальных значений параметров.

Random R; // Генератор случайных чисел

public uint maxQueueLength; // Максимальная длина очереди

public uint channelCount; // Число каналов в системе

public double lambda; // Интенсивность потока поступления заявок

public double mu; // Интенсивность потока обслуживания заявок

public double timeStep; // Шагповремени

public double timeOfFinishProcessingReq; // Время окончания обслуживания заявки во всех каналах

public double timeInQueue; // Время пребывания СМО в состояниях с очередью

public double processingTime; // Времяработысистемы

public double totalProcessingTime; // Суммарноевремяобслуживаниязаявок

public uint requestEntryCount; // Числопоступившихзаявок

public uint declinedRequestCount; // Числоотказанныхзаявок

public uint acceptedRequestCount; // Числообслуженныхзаявок

uint queueLength; // Длина очереди //

Тип, описывающий состояния СМО

enum SysCondition {S0, S1, S2, S3, S4, S5, S6};

SysCondition currentSystemCondition; // Текущее состояние системы

Задание состояний системы. Выделим у данной 2-х канальной системы 7 различных состояний: S 0 , S 1 . S 6 . СМО находится в состоянии S 0 , когда система свободна; S 1 – хотя бы один канал свободен; в состоянии S 2 , когда все каналы заняты, и есть место в очереди; в состоянии S 6 – все каналы заняты, и очередь достигла максимальной длины (queueLength = 4).

Определяем текущее состояние системы с помощью функции GetCondition()

SysCondition GetCondition()

SysCondition p_currentCondit = SysCondition.S0;

int busyChannelCount = 0;

for (int i = 0; i < channelCount; i++)

if (timeOfFinishProcessingReq[i] > 0)

busyChannelCount++;

p_currentCondit += k * (i + 1);

if (busyChannelCount > 1)

{p_currentCondit ++;}

return p_currentCondit + (int) QueueLength;

Изменение времени пребывания СМО в состояниях с длиной очереди 1, 2,3,4. Это реализуется следующим программным кодом:

if (queueLength > 0)

timeInQueue += timeStep;

if (queueLength > 1)

{timeInQueue += timeStep;}

Присутствует такая операция, как помещение заявки на обслуживание в свободный канал. Просматриваются, начиная с первого, все каналы, когда выполняется условие timeOfFinishProcessingReq [ i ] <= 0 (канал свободен), в него подается заявка, т.е. генерируется время окончания обслуживания заявки.

for (int i = 0; i < channelCount; i++)

if (timeOfFinishProcessingReq [i] <= 0)

timeOfFinishProcessingReq [i] = GetServiceTime();

totalProcessingTime+= timeOfFinishProcessingReq [i];

Обслуживаниезаявоквканалахмоделируетсякодом:

for (int i = 0; i < channelCount; i++)

if (timeOfFinishProcessingReq [i] > 0)

timeOfFinishProcessingReq [i] -= timeStep;

Алгоритм метода имитационного моделирования реализован на языке программирования C#.

3.3 Расчет показателей эффективности СМО на основе результатов ее имитационного моделирования

Наиболее важными являются такие показатели, как:

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

2) Относительная пропускная способность – это средняя доля поступивших заявок, обслуживаемых системой.

3) Абсолютная пропускная способность– это среднее число заявок, обслуживаемых в единицу времени.

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

5) Среднее время пребывания заявки в очереди определяется формулой Литтла

6) Среднее число занятых каналовопределяется следующим образом:

7) Процент заявок, которым было отказано в обслуживании, находится по формуле

8) Процент обслуженных заявок находится по формуле

3.4 Статистическая обработка результатов и их сравнение с результатами аналитического моделирования

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

Величина попадает в доверительный интервал, если выполняется неравенство

, где

математическое ожидание (среднее значение), находится по формуле

Исправленная дисперсия,

,

N =20 – число прогонов,

– надежность. При и N =20 .

Результат работы программы представлен на рис. 6.

Рис. 6. Вид программы

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

Таблица 2.

Показатели эффективности СМО	Результаты аналитического моделирования	Результаты имитационного моделирования (послед. шаг)	Результаты имитационного моделирования
			Нижняя граница доверительного интервала	Верхняя граница доверительного интервала
Вероятность отказа		0,174698253017626	0,158495148639101	0,246483801571923
Относительная пропускная способность		0,825301746982374	0,753516198428077	0,841504851360899
Абсолютная пропускная способность		3,96144838551539	3,61687775245477	4,03922328653232
Средняя длина очереди		1,68655313447018	1,62655862750852	2,10148609204869
Среднее время пребывания заявки в очереди	0,4242558575	0,351365236347954	0,338866380730942	0,437809602510145
Среднее число занятых каналов		1,9807241927577	1,80843887622738	2,01961164326616

Из табл. 2 видно, что результаты, полученные при аналитическом моделировании СМО, попадают в доверительный интервал, полученный по результатам имитационного моделирования. Т.е., результаты, полученные разными методами, согласуются.

Заключение

В данной работе рассмотрены основные методы моделирования СМО и расчета показателей их эффективности.

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

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

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

Литература

1. Вентцель Е.С. Исследование операций. – М.: Дрофа, 2004. – 208 с.

2. Волков И.К., Загоруйко Е.А. Исследование операций. – М.: Изд.-во МГТУ им. Н.Э. Баумана, 2002. – 435 с.

3. Волков И.К., Зуев С.М., Цветкова Г.М. Случайные процессы. – М.: Изд.-во МГТУ им. Н.Э. Баумана, 2000. – 447 с.

4. Гмурман В.Е. Руководство к решению задач по теории вероятностей и математической статистике. – М.: Высшая школа, 1979. – 400 с.

5. Ивницкий В.Л. Теория сетей массового обслуживания. – М.: Физматлит, 2004. – 772 с.

6. Исследование операций в экономике/ под ред. Н.Ш. Кремера. – М.: Юнити, 2004. – 407 с.

7. Таха Х.А. Введение в исследование операций. – М.: ИД «Вильямс», 2005. – 902 с.

8. Харин Ю.С., Малюгин В.И., Кирлица В.П. и др. Основы имитационного и статистического моделирования. – Минск: Дизайн ПРО, 1997. – 288 с.

За последние десятилетия в самых разных областях народного хозяйства возникла необходимость решения вероятностных задач, связанных с работой систем массового обслуживания. Примерами таких систем служат телефонные станции, ремонтные мастерские, торговые предприятия, билетные кассы и т.д. работа любой системы массового обслуживания состоит в обслуживании поступающего в нее потока требований (вызовы абонентов, при ход покупателей в магазин, требования на выполнение работы в мастерской и т. д.).
Математическая дисциплина, изучающая модели реальных систем массового обслуживания, получила название теории массового обслуживания. Задача теории массового обслуживания - установить зависимость результирующих показателей работы системы массового обслуживания (вероятности того, что требование будет обслужено; математического ожидания числа обслуженных требований и т. д.) от входных показателей (количество приборов в системе, параметров входящего потока требований и т. д.) установить такие зависимости в формульном виде можно только для простых систем массового обслуживания. Изучение же реальных систем проводится путем имитации, или моделирования их работы на ЭВМ с привлечением метода статистических испытаний.
Система массового обслуживания считается заданной, если определены:
1) входящий поток требований, или, иначе говоря, закон распределения, характеризующий моменты времени поступления требований в систему. Первопричину требований называют источником. В дальнейшем условимся считать, что источник располагает неограниченным числом требований и что требования однородны, т. е. различаются только моментами появления в системе;
2) система обслуживания, состоящая из накопителя и узла обслуживания. Последний представляет собой одно или несколько обслуживающих устройств, которые в дальнейшем будем называть приборами. Каждое требование должно поступить на один из приборов, чтобы пройти обслуживание. Может оказаться, что требованиям придется ожидать, пока приборы освободятся. В этом случае требования находятся в накопителе, образуя одну или несколько очередей. Положим, что переход требования из накопителя в узел обслуживания происходит мгновенно;
3) время обслуживания требования каждым прибором, которое является случайной величиной и характеризуется некоторым законом распределения;
4) дисциплина ожидания, т. е. совокупность правил, регламентирующих количество требований, находящихся в один и тот же момент времени в системе. Система, в которой поступившее требование получает отказ, когда все приборы заняты, называется системой без ожидания. Если требование, заставшее все приборы занятыми, становится в очередь и ожидает до тех пор,
пока освободиться один из приборов, то такая система называется чистой системой с ожиданием. Система, в которой требование, заставшее все приборы занятыми, становится в очередь только в том случае, когда число требований, находящихся в системе, не превышает определенного уровня (в противном случае происходит потеря требования), называется смешанной системой обслуживания;
5) дисциплина обслуживания, т. е. совокупность правил, в соответствии с которыми требование выбирается из очереди для обслуживания. Наиболее часто на практике используются следующие правила:
- заявки принимаются к обслуживанию в порядке очереди;
- заявки принимаются к обслуживанию по минимальному времени получения отказа;
- заявки принимаются к обслуживанию в случайном порядке в соответствии с заданными вероятностями;
6) дисциплина очереди, т.е. совокупность правил, в соответствии с которыми требование отдает предпочтение той или иной очереди (если их не сколько) и располагается в выбранной очереди. Например, поступившее требование может занять место в самой короткой очереди; в этой очереди оно может расположиться последним (такая очередь называется упорядоченной), а может пойти на обслуживание вне очереди. Возможны и другие варианты.

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

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

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

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

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

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

3 Формирование реализаций случайного потока заявок

При исследовании сложных систем методом имитационного моделирования существенное внимание уделяется учету случайных факторов.
В качестве математических схем, используемых для формализации действия этих факторов, используются случайные события, случайные величины и случайные процессы (функции). Формирование на ЭВМ реализаций случайных объектов любой природы сводится к выработке и преобразованию случайных чисел. Рассмотрим способ получения возможных значений случайных величин с заданным законом распределения. Для формирования возможных значений случайных величин с заданным законом распределения исходным материалом служат случайные величины, имеющие равномерное распределение в интервале (0, 1). Другими словами, возможные значения xi случайной величины £, имеющей равномерное распределение в интервале (0, 1), могут быть преобразованы в возможные значения yi случайной величины г), закон распределения которой задан. Способ преобразования состоит в том, что из равномерно распределенной совокупности отбираются случайные числа, удовлетворяющие некоторому условию таким образом, чтобы отобранные числа подчинялись заданному закону распределения.
Предположим, что необходимо получить последовательность случайных чисел yi , имеющих функцию плотности 1^(у). Если область определения функции f^y) не ограничена с одной или обеих сторон, необходимо перейти к соответствующему усеченному распределению. Пусть область возможных значений для усеченного распределения равна (a, b).
От случайной величины г), соответствующей функции плотности f ^ y), перейдем к f.
Случайная величина Ъ, будет иметь область возможных значений (0, 1) и функцию плотности f ^(z), задаваемую выражением.
Пусть максимальное значение f^(z) равно f m . Зададим равномерные распределения в интервалах (0, 1) случайных чисел x 2 i-1 и x 2 i. Процедура по лучения последовательности yi случайных чисел, имеющих функцию плотности ^(у), сводится к следующему:
1) из исходной совокупности выбираются пары случайных чисел x2i-1,
2) для этих чисел проверяется справедливость неравенства
х 21 <-- ^[а + (Ъ-а)х 2М ] (3)
m
3) если неравенство (3) выполнено, то очередное число yi определяется из соотношения
yi =a + (b-а)х 21 (4)
При моделировании процессов обслуживания возникает необходимость формирования реализаций случайного потока однородных событий (заявок). Каждое событие потока характеризуется моментом времени tj, в который оно наступает. Чтобы описать случайный поток однородных событий как случайный процесс, достаточно задать закон распределения, характеризующий последовательность случайных величин tj. Для того, чтобы получить реализацию потока однородных событий t1, t2..., tk, необходимо сформировать реализацию z b z 2 ,...,zk k-мерного случайного вектора ££2,..., Sk и вычислить значения ti в соответствии со следующими соотношениями:
t 2 =
Пусть стационарный ординарный поток с ограниченным последействием задан функцией плотности f(z). В соответствии с формулой Пальма (6) найдем функцию плотности f1(z1) для первого интервала z1.
1- Jf (u) du
Теперь можно сформировать случайное число z b как было показано выше, соответствующее функции плотности f1(z1), и получить момент появления первой заявки t1 = z1 . Далее формируем ряд случайных чисел, соответствующих функции плотности f(z), и при помощи соотношения (4) вычисляем значения величин t2, t3 ,.., tk.
4 Обработка результатов моделирования
При реализации моделирующих алгоритмов на ЭВМ вырабатывается информация о состояниях исследуемой системы. Эта информация является исходным материалом для определения приближенных значений искомых величин, или, как принято говорить, оценок для искомых величин.
Оценка вероятности события А вычисляется по формуле
p(A) = mN . (7)
Оценка среднего значения x случайной величины Ъ, вычисляется по
формуле
_ 1 n
k =1
Оценка S 2 для дисперсии случайной величины ^ вычисляется по формуле
1 N 1 (N Л 2
S 2 =1 YA xk 2-5> J (9)
Оценка корреляционного момента К^ для случайных величин Ъ, и ц с возможными значениями x k и y k соответственно вычисляется по формуле
1 N 1 NN
У> [ Ух

5 Пример моделирования СМО
Рассмотрим следующую систему:
1 Требования поступают в случайные моменты времени, при этом
промежуток времени Q между любыми двумя последовательными требованиями имеет показательный закон с параметром i, т. е. функция распределения имеет вид
>0. (11) Система обслуживания состоит из s одинаковых, пронумерованных приборов.
3 Время Т о бсл - случайная величина с равномерным законом распределения на отрезке .
4 Система без ожидания, т.е. требование, заставшее все приборы занятыми, покидает систему.
5 Дисциплина обслуживания такова: если в момент поступления k - го требования первый прибор свободен, то он приступает к обслуживанию требования; если этот прибор занят, а второй свободен, то требование обслуживается вторым прибором, и т.д.
Требуется оценить математические ожидания числа требований, обслуженных системой за время Т и получивших отказ.
За начальный момент расчета выберем момент поступления первого требования Т1=0. Введем следующие обозначения: Тk- момент поступления k-го требования; ti - момент окончания обслуживания требования i-м прибором, i=1, 2, 3, ...,s.
Предположим, что в момент T 1 все приборы свободны.
Первое требование поступает на прибор 1. Время обслуживания этим прибором имеет равномерное распределение на отрезке . Поэтому конкретное значение tобсл этого времени находим по формуле
(12)
где r- значение случайной величины R , равномерно распределенной на отрезке . Прибор 1 будет занят в течение времени t о бсл. Поэтому момент времени t 1 окончания обслуживания требования прибором 1 следует считать равным: t 1 = Т1+ t о бсл.
Затем следует добавить единицу в счетчик обслуженных требований и перейти к рассмотрению следующего требования.
Предположим, что k требований уже рассмотрено. Определим момент Т k+1 поступления (k+1)-го требования. Для этого найдем значение т промежутка времени между последовательными требованиями. Так как этот про межуток имеет показательный закон, то
12
х = - In r (13)
| Ll
где r -очередное значение случайной величины R . Тогда момент посту пления (k+1)-го требования: Т k +1 = Тк+ Т.
Свободен ли в этот момент первый прибор? Для ответа на этот вопрос необходимо проверить условие ti < Tk + i - Если это условие выполнено, то к моменту Т k +1 первый прибор освободился и может обслуживать требование. В этом случае t 1 заменяем на (Т k +1 + t обсл), добавляем единицу в счетчик об служенных требований и переходим к следующему требованию. Если t 1>Т k +1, то первый прибор в момент Т k +1 занят. В этом случае проверяем, свободен ли второй прибор. Если условие i 2< Tk + i выполнено, заменяем t2 на (Т k +1+ t о бсл), добавляем единицу в счетчик обслуженных требований и переходим к следующему требованию. Если t 2>Т k +1, то проверяем условие 1з<Тк+1 и т. д. Eсли при всех i от 1 до s имеет ti >Т k +1, то в момент Т k +1 все приборы заняты. В этом случае прибавляем единицу в счетчик отказов и переходим к рассмотрению следующего требования. Каждый раз, вычислив Т k +1, надо проверить еще ус ловие окончания реализации: Tk + i < T . Если это условие выполнено, то одна реализация процесса функционирования системы воспроизведена и испыта ние заканчивается. В счетчике обслуженных требований и в счетчике отказов находятся числа n обсл и n отк.
Повторив такое испытание n раз (с использованием различных r) и усреднив результаты опытов, определим оценки математических ожиданий числа обслуженных требований и числа требований, получивших отказ:
(14)
(Ji
n j =1
где (n обсл) j и (n отк) j - значения величин n обсл и n отк в j -ом опыте.
13

Список использованных источников
1 Емельянов А.А. Имитационное моделирование экономических процессов [Текст]: Учеб. пособие для вузов / А.А. Емельянов, Е.А. Власова, Р.В. Дума. - М. : Финансы и статистика, 2002. - 368с.
2 Бусленко, Н.П. Моделирование сложных систем [Текст]/ Н.П. Бусленко.- М. : Наука, 1978. - 399с.
3 Советов Б.Я. Моделирование систем [Текст]: Учеб. для вузов / Б.Я. Сове тов, С.А. Яковлев. -М. : Высш. школа, 1985. - 271 с.
4 Советов Б.Я. Моделирование систем [Текст]: Лабораторный практи кум: Учеб. пособие для вузов по специальности: "Автом. сист. обработ. инф. и управл." / Б.Я. Советов, С.А. Яковлев. -М. : Высш. шк., 1989. - 80 с.
5 Максимей И.В. Имитационное моделирование на ЭВМ [Текст]/ Максимей, И.В. -М: РАДИО И СВЯЗЬ, 1988. - 231с.
6 Вентцель Е.С. Теория вероятностей [ Текст ] : учеб. для вузов / Е.С. Вент цель.- М. : Высш. шк., 2001. - 575 с.
7 Гмурман, В.Е. Теория вероятностей и математическая статисти ка [ Текст ] : учеб. пособие / В.Е. Гмурман.- М. : Высш. шк., 2001. - 479 с.
Приложение А
(обязательное)
Примерные темы расчетно-графических работ
1 На травмопункте работает один врач. Длительность лечения больного
и промежутки времени между поступлениями больных - случайные величи ны, распределенные по пуассоновскому закону. По тяжести травм больные делятся на три категории, поступление больного любой категории - случай ное событие с равновероятным распределением. Врач вначале занимается больными с максимально тяжелыми травмами (в порядке их поступления), затем, если таковых нет, больными средней тяжести, и лишь затем - больны ми с легкими травмами. Смоделировать процесс и оценить средние времена ожидания в очереди больных каждой из категорий.
2 В городском автохозяйстве две ремонтные зоны. Первая обслуживает ремонты краткой и средней продолжительности, вторая - средней и долгой. По мере поломок в автохозяйство доставляют транспорт; промежуток време ни между доставками - случайная пуассоновская величина. Продолжительности ремонта - случайная величина с нормальным законом распределения. Смоделировать описанную систему. Оценить средние времена ожидания в очереди транспорта, требующие соответственно краткосрочного, среднесрочного и длительного ремонта.
3 Мини-маркет с одним контролером - кассиром обслуживает покупа телей, входящий поток которых подчиняется закону Пуассона с параметром 20 покупателей/час. Провести моделирование описанного процесса и определить вероятность простоя контролера - кассира среднюю длину очереди, среднее число покупателей в мини-маркете, среднее время ожидания обслуживания, среднее время пребывания покупателей в мини-маркете и дайте оценку его работы.
4 На АТС поступают заявки на междугородние переговоры. Поток зая вок является пуассоновским. В среднем за 1 час поступает 13 заявок. Найдите среднее число заявок, поступающих за сутки, среднее время между появлением заявок. На телефонной станции появляются сбои в работе, если за полчаса на нее поступит более 50 заявок. Найдите вероятность сбоя станции.
5 На станцию технического обслуживания поступает простейший по
ток заявок с интенсивностью 1 автомобиль за 2 ч. Во дворе в очереди может находиться не более 3 машин. Среднее время ремонта - 2 часа. Дайте оценку работы СМО и разработайте рекомендации по улучшению обслуживания.
6 Одна ткачиха обслуживает группу станков, осуществляя по мере необходимости краткосрочное вмешательство, длительность которого - случайная величина. Смоделировать описанную ситуацию. Какова вероятность простоя сразу двух станков. Как велико среднее время простоя одного станка.
7 На междугородней телефонной станции две телефонистки обслуживают общую очередь заказов. Очередной заказ обслуживает та телефонистка, которая первой освободилась. Если обе в момент поступления заказа заняты, звонок аннулируется. Смоделировать процесс, считая входные потоки пуассоновскими.
8 На травмопункте работают два врача. Длительность лечения больно
го и промежутки времени между поступлениями больных - случайные вели чины, распределенные по пуассоновскому закону. По тяжести травм больные делятся на три категории, поступление больного любой категории - случай ное событие с равновероятным распределением. Врач вначале занимается больными с максимально тяжелыми травмами (в порядке их поступления), затем, если таковых нет, больными средней тяжести, и лишь затем - больны ми с легкими травмами. Смоделировать процесс и оценить средние времена ожидания в очереди больных каждой из категорий.
9 На междугородней телефонной станции две телефонистки обслужи
вают общую очередь заказов. Очередной заказ обслуживает та телефонистка,
которая первой освободилась. Если обе в момент поступления заказа заняты, то формируется очередь. Смоделировать процесс, считая входные потоки пу- ассоновскими.
10 В системе передачи данных осуществляется обмен пакетами данных между узлами A и B по дуплексному каналу связи. Пакеты поступают в пункты системы от абонентов с интервалами времени между ними 10 ± 3 мс. Передача пакета занимает 10 мс. В пунктах имеются буферные регистры, ко торые могут хранить два пакета, включая передаваемый. В случае прихода пакета в момент занятости регистров пунктам системы предоставляется вы ход на спутниковую полудуплексную линию связи, которая осуществляет передачу пакетов данных за 10 ± 5 мс. При занятости спутниковой линии па кет получает отказ. Смоделировать обмен информацией в системе передачи данных в течение 1 мин. Определить частоту вызовов спутниковой линии и ее загрузку. В случае возможности отказов определить необходимый для безотказной работы системы объем буферных регистров.
11 Пусть на телефонной станции с одним входом используется обычная система: если абонент занят, то очередь не формируется и надо звонить сно ва. Смоделировать ситуацию: три абонента пытаются дозвониться до одного и того же владельца номера и в случае успеха разговаривают с ним некоторое (случайное по длительности) время. Какова вероятность того, что некто, пы тающийся дозвониться, не сможет это сделать за определенное время Т.
12 Торговая фирма планирует выполнять заказы на приобретение това ров по телефону, для чего необходимо установить соответствующую мини- АТС с несколькими телефонными аппаратами. Если заказ поступает, когда все линии заняты, то клиент получает отказ. Если в момент поступления за явки хотя бы одна линия свободна, то производится переключение на эту линию и оформляется заказ. Интенсивность входящего потока заявок составляет 30 заказов в час. Длительность оформления заявки в среднем равна 5 мин. Определите оптимальное число каналов обслуживания, чтобы обеспечить условие стационарной работы СМО.
13 В магазине самообслуживание 6 контролеров - кассиров. Входящий поток покупателей подчиняется закону Пуассона с интенсивностью 120 чел/час. Один кассир может обслужить 40 человек в час. Определите вероят ность простоя кассира, среднее число покупателей в очереди, среднее время ожидания, среднее число занятых кассиров. Дайте оценку работы СМО.
14 В магазин самообслуживания поступает пуассоновский поток с ин тенсивностью 200 покупателей в час. В течение дня их обслуживают 3 кон тролера-кассира с интенсивностью 90 покупателей в час. Интенсивность входного потока покупателей в часы пик возрастает до величины 400 поку пателей в час, а в часы спада достигает величины 100 покупателей в час. Определите вероятность образования очереди в магазине и среднюю длину очереди в течение дня, а также необходимое число контролеров-кассиров в часы пик и часы спада, обеспечивающие такую же длину очереди и вероятность ее образования, как и в номинальном режиме.
15 Среднее число покупателей, поступающих на узел расчета в магазин самообслуживания 100 чел/час. Кассир может обслужить 60 человек в час. Смоделируйте процесс и определите, какое число кассиров необходимо для того, чтобы вероятность появления очереди не превысила 0.6.
16 Провести моделирование очереди в магазине с одним продавцом при равновероятных законах распределения случайных величин: прихода по купателей и длительности обслуживания (при некотором фиксированном на боре параметров). Получить устойчивые характеристики: средние значения ожидания в очереди покупателем и простой продавца в ожидании прихода покупателей. Оценить их достоверность.
17 Провести моделирование очереди в магазине с одним продавцом при пуассоновских законах распределения случайных величин: прихода по купателей и длительности обслуживания (при некотором фиксированном на боре параметров). Получить устойчивые характеристики: средние значения ожидания в очереди покупателем и простой продавца в ожидании прихода покупателей. Оценить их достоверность.
18 Создайте модель бензоколонки. Найдите показатели качества обслуживания заявок. Определите количество стоек с тем, чтобы очередь не увеличивалась.
19 Среднее число покупателей, поступающих на узел расчета в магазин самообслуживания, 60 человек в час. Кассир может обслужить 35 человек в час. Смоделируйте процесс и определите, какое число кассиров необходимо для того, чтобы вероятность появления очереди не превысила 0.6.
20 Разработайте модель автобусного маршрута с n остановками. Определите показатели эффективности использования СМО.

Рисунок 0 - 2 Потоки событий (а) и простейший поток (б)

10.5.2.1. Стационарность

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

Рисунок 0-2 , а) зависит только от длины участка и не зависит от того, где именно на оси t расположен этот участок.

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

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

10.5.2.2. Отсутствие последействия

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

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

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

Рисунок 0 - 3 Распределение Пуассона

Рассмотрим на оси t простейший поток событий с интенсивностью λ. (Рисунок 0-2 б). Нас будет интересовать случайный интервал времени Т между соседними событиями в этом потоке; найдем его закон распределения. Сначала найдем функцию распределения:

F(t) = P(T (0-2)

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

F (t ) = 1 - Р0

Вероятность Р 0 найдем по формуле (1), полагая m = 0:

откуда функция распределения величины Т будет:

(0-3)

Чтобы найти плотность распределения f (t ) случайной величины Т, необходимо продифференцировать выражение (0‑1) по t :

0-4)

Закон распределения с плотностью (0‑4) называется показательным (или экспоненциальным). Величина λ называется параметром показательного закона.

Рисунок 0 - 4 Экспоненциальное распределение

Найдем числовые характеристики случайной величины Т - математическое ожидание (среднее значение) M [ t ]= m t , и дисперсию D t . Имеем

( 0-5)

(интегрируя по частям) .

Дисперсия величины Т составляет:

(0-6)

Извлекая корень квадратный из дисперсии, найдем среднее квадратическое отклонение случайной величины Т.

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

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

Пример СМО- 1 .

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

Рассчитаем вероятность Р (m ) появления m сообщений в 1 с. Так как λ = 2, то из предыдущей формулы имеем

Подставляя m = 0, 1, 2, 3, получим следующие величины (с точностью до четырех десятичных знаков):

Рисунок 0 - 5 Пример простейшего потока

Возможно поступление и более 9 сообщений в 1 с, но вероятность этого очень мала (около 0,000046).

Полученное распределение может быть представлено в виде гистограммы (показана на рисунке).

Пример СМО- 2 .

Прибор (сервер), обрабатывающей три сообщения в 1с.

Пусть имеется оборудование, которое может обрабатывать три сообщения в 1 с (µ=3). Поступает всреднем два сообщения в 1с, причем в соответствии c распределением Пуассона. Какая часть этих сообщений будет обрабатываться сразу же после поступления?

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

Если система может обрабатывать максимум 3 сообщения в 1 с, то вероятность того, что она не будет перегружена, равна

Другими словами, 85,71% сообщений будут обслуживаться немедленно, а 14,29% с некоторой задержкой. Как видим, задержка в обработке одного сообщения на время, большее времени обработки 3 сообщений, будет встречаться редко. Время обработки 1сообщения составляет в среднем 1/3 с. Следовательно, задержка более 1с будет редким явлением, что вполне приемлемо для большинства систем.

Пример СМО- 3

· Если кассир банка занят в течение 80% своего рабочего времени, а остальное время он тратит на ожидание клиентов, то его можно рассматривать как устройство с коэффициентом использования 0,8.

· Если канал связи используется для передачи 8-битовых символов со скоростью 2400 бит/с, т. е. передается максимум 2400/8 символов в 1 с, и мы строим систему, в которой суммарный объем данных составляет 12000 символов, посылаемых от различных устройств через канал связи в минуту наибольшей нагрузки (включая синхронизацию, символы конца сообщений, управляющие и т. д.), то коэффициент использования оборудования канала связи в течение этой минуты равен

· Если механизм доступа к файлу в час наибольшей нагрузки осуществляет 9000 обращений к файлу, а время одного обращения равно в среднем 300 мс, то коэффициент использования оборудования механизма доступа в час наибольшей нагрузки составляет

Понятие коэффициента использования оборудования будет использоваться довольно часто. Чем ближе коэффициент использования оборудования к 100%, тем больше задержки и длиннее очереди.

Используя предыдущую формулу, можно составить таблицы значений функции Пуассона, по которым можно определить вероятность поступления m или более сообщений в данный отрезок времени. Например, если в среднем поступает 3,1 сообщения в секунду [т. е. λ = 3,1], то вероятность поступления 5 и более сообщений в данную секунду равна 0,2018 (для m = 5 в таблице). Или в аналитическом виде

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

Часто первоначальные расчеты могут быть проведены для значений загрузки оборудования

ρ ≤ 0,9

Эти значения можно получить с помощью таблиц Пуассона.

Пусть снова средняя скорость поступления сообщений λ = 3,1 сообщения/с. Из таблиц следует, что вероятность поступления 6 или более сообщений в 1 с равна 0,0943. Следовательно, это число можно взять в качестве критерия нагрузки для проведения начальных расчетов.

10.6.2. Задачи проектирования

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

Чем больше коэффициент использования оборудования, тем длиннее возникающие очереди. Как будет показано ниже, можно спроектировать удовлетворительно работающую систему с коэффициентом использований ρ =0,7 но коэффициент, превышающий ρ > 0,9, может привести к ухудшению качества обслуживания. Другими словами, если канал пересылки массива данных имеет загрузку 20%, вряд ли на нем возникнет очередь. Если же загрузка; составляет 0,9, то, как правило, будут образовываться очереди, иногда очень большие.

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

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

· Какова длина очереди?

· Сколько времени на нее будет затрачиваться?

На вопросы подобного типа можно ответить с помощью теории очередей.

10.6.3. Системы массового обслуживания, их классы и основные характеристики

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

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

СМО классифицируются на системы с:

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

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

Обслуживание (дисциплина очереди) в системе с ожиданием может быть

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

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

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

· Приоритетным

o со статическим приоритетом

o с динамическим приоритетом

(в последнем случае приоритет может, например, увеличиваться с длительностью ожидания заявки).

Системы с очередью делятся на системы

· с неограниченным ожиданием и

· с ограниченным ожиданием.

В системах с неограниченным ожиданием каждая заявка, поступившая в момент, когда нет свободных каналов, становится в очередь и «терпеливо» ждет освобождения канала, который примет ее к обслуживанию. Любая заявка, поступившая в СМО, рано или поздно будет обслужена.

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

· длины очереди (числа заявок, одновременно находящихся в очереди система с ограниченной длиной очереди),

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

· общего времени пребывания заявки в СМО

и т. д.

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

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

Помимо абсолютной и относительной пропускной способностей при анализе СМО с отказами нас могут, в зависимости от задачи исследования, интересовать и другие характеристики, например:

· среднее число занятых каналов;

· среднее относительное время простоя системы в целом и отдельного канала

и т. д.

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

· среднее число заявок в очереди;

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

· среднее время ожидания заявки в очереди;

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

а также и другие характеристики ожидания.

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

Для анализа процесса, протекающего в СМО, существенно знать основные параметры системы: число каналов п, интенсивность потока заявок λ , производительность каждого канала (среднее число заявок μ, обслуживаемое каналом в единицу времени), условия образования очереди (ограничения, если они есть).

В зависимости от значений этих параметров выражаются характеристики эффективности работы СМО.

10.6.4. Формулы расчета характеристик СМО для случая обслуживания с одним прибором

Рисунок 0 - 6 Модель системы массового обслуживания с очередью

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

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

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

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

Рассмотрим очередь с одним прибором обслуживания. При проектировании вычислительной системы большинство очередей подобного типа рассчитывается по приведенным формулам. коэффициент вариации времени обслуживания

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

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

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

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

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

Рассмотрим следующий пример. Имеется шесть типов сообщений с временами обслуживания 15, 20, 25, 30, 35 и 300. Число сообщений каждого типа одинаково. Стандартное отклонение указанных времен несколько выше их среднего. Значение последнего времени обслуживания намного больше других. Это приведет к тому, что сообщения будут находиться в очереди значительно дольше, чем, если бы времена обслуживания были одного порядка. В таком случае при проектировании целесообразно принять меры для уменьшения длины очереди. Например, если указанные цифры связаны с длинами сообщений, то, возможно, очень длинные сообщения стоит разделить на части.

10.6.6. Пример расчета

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

Время ответа системы и его стандартное отклонение рассчитаны с учетом времени ввода данных с АРМа, печатания и оформления документа.

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

Предположим, что в часы пик приходит 30 клиентов в час. В среднем кассир тратит 1,5 мин на клиента. Тогда

ρ =(1,5 * 30) / 60 = 0,75

т. е. кассир используется на 75%.

Число людей в очереди можно быстро оценить с помощью графиков. Из них следует, что если ρ = 0,75, то среднее число nq людей в очереди у кассы лежит между 1,88 и 3,0 в зависимости от стандартного отклонения для t s .

Предположим, что измерение стандартного отклонения для t s дало величину 0,5 мин. Тогда

σ s = 0,33 t s

Из графика на первом рисунке находим, что nq = 2,0, т. е. в среднем у кассы буду ожидать два клиента.

Общее время, в течение которого клиент стоит у кассы, может быть найдено как

t ∑ = t q + t s = 2,5 мин + 1,5 мин=4мин

где t s вычисляется с помощью формулы Хинчина-Полачека.

10.6.7. Фактор усиления

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

Увеличение входного трафика на небольшое число х%. приводит к увеличению размеров очереди приблизительно на

Если коэффициент использования оборудования равен 50%, то это увеличение равно 4ts % для экспоненциального закона распределения времени обслуживания. Но если коэффициент использования оборудования равен 90%, то увеличение размера очереди равно 100ts %, что в 25 раз больше. Незначительное увеличение нагрузки при 90%-ном использовании оборудования приводит к 25-кратному увеличению размеров очереди по сравнению со случаем 50%-ного использования оборудования.

Аналогично время пребывания в очереди увеличивается на

При экспоненциально распределенном времени обслуживания эта величина имеет значение 4 t s 2 для коэффициента использования оборудования, равного 50%, и 100 t s 2 для коэффициента 90%, т. е. снова в 25 раз хуже.

Кроме того, для малых коэффициентов использования оборудования влияние изменений σs на размер очереди незначительно. Однако для больших коэффициентов изменение σ s сильно сказывается на размере очереди. Поэтому при проектировании систем с высоким коэффициентом использования оборудования желательно получить точные сведения о параметре σ s . Неточность предположения относительно экспоненциальности распределения t s наиболее ощутима при больших значениях ρ. Более того, если вдруг время обслуживания возрастет, что возможно в каналах связи при передаче длинных сообщений, то в случае большого ρ образуется значительная очередь.

Московский государственный технический университет

имени Н.Э. Баумана (Калужский филиал)

Кафедра высшей математики

Курсовая работа

по курсу «Исследование операций»

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

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

Число каналов обслуживания n; максимальная длина очереди т;

Поток поступающих в систему заявок простейший со средней интенсивностью λ и показательным законом распределения времени между поступлением заявок;

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

Сравнить найденные значения показателей с результатами. полученными путем численного решения уравнении Колмогорова для вероятностей состояний системы. Значения параметров СМО приведены в таблице.

Введение

Глава 1. Основные характеристики CМО и показатели их эффективности

1.1 Понятие марковского случайного процесса

1.2 Потоки событий

1.3 Уравнения Колмогорова

1.4 Финальные вероятности и граф состояний СМО

1.5 Показатели эффективности СМО

1.6 Основные понятия имитационного моделирования

1.7 Построение имитационных моделей

Глава 2. Аналитическое моделирование СМО

2.1 Граф состояний системы и уравнения Колмогорова

2.2 Расчет показатели эффективности системы по финальным вероятностям

Глава 3. Имитационное моделирование СМО

3.1 Алгоритм метода имитационного моделирования СМО (пошаговый подход)

3.2 Блок-схема программы

3.3 Расчет показателей эффективности СМО на основе результатов ее имитационного моделирования

3.4 Статистическая обработка результатов и их сравнение с результатами аналитического моделирования

Заключение

Литература

Приложение 1

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

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

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

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

В качестве показателей эффективности СМО используются:

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

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

Вероятность отказа обслуживания заявки (

);

Среднее число занятых каналов (k);

Среднее число заявок в СМО (

);

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

);

Среднее число заявок в очереди (

);

Среднее время пребывания заявки в очереди (

);

Среднее число заявок, обслуживаемых в единицу времени;

Среднее время ожидания обслуживания;

Вероятность того, что число заявок в очереди превысит определенное значение и т.п.

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

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

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

Процесс называется процессом с дискретными состояниями, если его состояния

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

Процесс работы СМО – это случайный процесс с дискретными состояниями и непрерывным временем.

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

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

1.2 Потоки событий

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

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

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

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

.

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

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

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