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

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

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

Примерами систем массового обслуживания могут служить:

• расчетно-кассовые узлы в банках, на предприятиях;
• персональные компьютеры, обслуживающие поступающие заявки или требования на решение тех или иных задач;
• станции технического обслуживания автомобилей; АЗС;
• аудиторские фирмы;
• отделы налоговых инспекций, занимающиеся приёмкой и проверкой текущей отчетности предприятий;
• телефонные станции и т. д.

	Узлы	Требования
Больница	Санитары	Пациенты
Производство
Аэропорт	Выходы на взлетно-посадочные полосы Пункты регистрации	Пассажиры

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

Рис. 1

1. Генератор заявок – объект, порождающий заявки: улица, цех с установленными агрегатами. На вход поступает поток заявок (поток покупателей в магазин, поток сломавшихся агрегатов (машин, станков) на ремонт, поток посетителей в гардероб, поток машин на АЗС и т. д.).
2. Диспетчер – человек или устройство, которое знает, что делать с заявкой. Узел, регулирующий и направляющий заявки к каналам обслуживания. Диспетчер:

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

1. Очередь – накопитель заявок. Очередь может отсутствовать.
2. Узел обслуживания состоит из конечного числа каналов обслуживания. Каждый канал имеет 3 состояния: свободен, занят, не работает. Если все каналы заняты, то можно придумать стратегию, кому передавать заявку.
3. Отказ от обслуживания наступает, если все каналы заняты (некоторые в том числе могут не работать).

Кроме этих основных элементов в СМО в некоторых источниках выделяются также следующие составляющие:

терминатор – уничтожитель трансактов;

склад – накопитель ресурсов и готовой продукции;

счет бухгалтерского учета – для выполнения операций типа «проводка»;

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

Классификация СМО

Первое деление (по наличию очередей):

• СМО с отказами;
• СМО с очередью.

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

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

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

Итак, например, рассматриваются следующие СМО:

• СМО с нетерпеливыми заявками (длина очереди и время обслуживания ограничено);
• СМО с обслуживанием с приоритетом, т. е. некоторые заявки обслуживаются вне очереди и т. д.

Типы ограничения очереди могут быть комбинированными.

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

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

Кроме этого СМО делятся на открытые СМО и замкнутые СМО.

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

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

По количеству каналов СМО делятся на:

• одноканальные;
• многоканальные.

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

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

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

Входной поток требований

Для описания входного потока требуется задать вероятностный закон, определяющий последовательность моментов поступления требований на обслуживание, и указать количество таких требований в каждом очередном поступлении. При этом, как правило, оперируют понятием «вероятностное распределение моментов поступления требований». Здесь могут поступать как единичные, так и групповые требования (количество таких требований в каждом очередном поступлении ). В последнем случае обычно речь идет о системе обслуживания с параллельно-групповым обслуживанием.

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

E(A) – среднее (МО) время поступления;

λ=1/E(A) – интенсивность поступления требований;

Характеристики входного потока:

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

Дисциплина очереди

Очередь – совокупность требований, ожидающих обслуживания.

Очередь имеет имя.

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

• первым пришел – первый обслуживаешься;

first in first out (FIFO)

самый распространенный тип очереди.

Какая структура данных подойдет для описания такой очереди? Массив плох (ограничен). Можно использовать структуру типа СПИСОК.

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

Вы как программисты должны уметь делать списки двусторонние, односторонние.

Действия со списком:

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

Структура, известная как СТЕК. Может быть описан структурой массив или список;

• случайный отбор заявок;
• отбор заявок по критерию приоритетности.

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

Характеристики очереди

• ограничение времени ожидания момента наступления обслуживания (имеет место очередь с ограниченным временем ожидания обслуживания, что ассоциируется с понятием «допустимая длина очереди»);
• длина очереди.

Механизм обслуживания

Механизм обслуживания определяется характеристиками самой процедуры обслуживания и структурой обслуживающей системы. К характеристикам процедуры обслуживания относятся:

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

Для аналитического описания характеристик процедуры обслуживания оперируют понятием «вероятностное распределение времени обслуживания требований».

S i – время обслуживания i -го требования;

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

μ=1/E(S) – скорость обслуживания требований.

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

Коэффициент использования СМО

N ·μ – скорость обслуживания в системе, когда заняты все устройства обслуживания.

ρ=λ/(N μ) – называется коэффициентом использования СМО , показывает, насколько задействованы ресурсы системы.

Структура обслуживающей системы

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

Пример. Кассы в магазине.

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

Пример. Медицинская комиссия.

Комбинированное обслуживание – обслуживание вкладов в сберкассе: сначала контролер, потом кассир. Как правило, 2 контролера на одного кассира.

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

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

Основные критерии эффективности функционирования СМО

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

• вероятность немедленного обслуживания поступившей заявки (Р обсл =К обс /К пост);
• вероятность отказа в обслуживании поступившей заявки (P отк =К отк /К пост);

Очевидно, что Р обсл + P отк =1.

Потоки, задержки, обслуживание. Формула Поллачека–Хинчина

Задержка – один из критериев обслуживания СМО, время проведенное заявкой в ожидании обслуживания.

D i – задержка в очереди требования i ;

W i =D i +S i – время нахождения в системе требования i .

(с вероятностью 1) – установившаяся средняя задержка требования в очереди;

(с вероятностью 1) – установившееся среднее время нахождения требования в СМО (waiting).

Q(t) – число требований в очереди в момент времени t;

L(t) – число требований в системе в момент времени t (Q(t) плюс число требований, которые находятся на обслуживании в момент времени t.

Тогда показатели (если существуют)

(с вероятностью 1) – установившееся среднее по времени число требований в очереди;

(с вероятностью 1) – установившееся среднее по времени число требований в системе.

Заметим, что ρ<1 – обязательное условие существования d, w, Q и L в системе массового обслуживания.

Если вспомнить, что ρ= λ/(N μ), то видно, что если интенсивность поступления заявок больше, чем N μ, то ρ>1 и естественно, что система не сможет справиться с таким потоком заявок, а следовательно, нельзя говорить о величинах d, w, Q и L.

К наиболее общим и нужным результатам для систем массового обслуживания относятся уравнения сохранения

Следует обратить внимание, что упомянутые выше критерии оценки работы системы могут быть аналитически вычислены для систем массового обслуживания M/M/N (N >1), т. е. систем с Марковскими потоками заявок и обслуживания. Для М/G/ l при любом распределении G и для некоторых других систем. Вообще распределение времени между поступлениями, распределение времени обслуживания или обеих этих величин должно быть экспоненциальным (или разновидностью экспоненциального распределения Эрланга k-го порядка), чтобы аналитическое решение стало возможным.

Кроме этого можно также говорить о таких характеристиках, как:

• абсолютная пропускная способность системы – А=Р обсл *λ;
• относительная пропускная способность системы –

Еще один интересный (и наглядный) пример аналитического решения – вычисление установившейся средней задержки в очереди для системы массового обслуживания M/G/ 1 по формуле:

.

В России эта формула известна как формула Поллачека– Хинчина, за рубежом эта формула связывается с именем Росса (Ross).

Таким образом, если E(S) имеет большее значение, тогда перегрузка (в данном случае измеряемая как d ) будет большей; чего и следовало ожидать. По формуле можно обнаружить и менее очевидный факт: перегрузка также увеличивается, когда изменчивость распределения времени обслуживания возрастает, даже если среднее время обслуживания остается прежним. Интуитивно это можно объяснить так: дисперсия случайной величины времени обслуживания может принять большое значение (поскольку она должна быть положительной), т. е. единственное устройство обслуживания будет занято длительное время, что приведет к увеличению очереди.

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

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

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

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

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

Рис. 2. Диаграмма состояний и переходов СМО

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

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

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

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

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

1) появление заявки на входе в систему;

2) прохождение очереди;

3) процесс обслуживания, после которого заявка покидает систему.

На каждом этапе используются определенные характеристики, которые следует обсудить прежде, чем строить математические модели.

Характеристики входа:

1) число заявок на входе (размер популяции);

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

3) поведение клиентов.

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

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

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

дискретное распределение Пуассона описывается следующей фор­мулой:

Где Р (х) - вероятность поступления Х заявок в единицу вре­мени;

Х - число заявок в единицу времени;

L - среднее число заявок в единицу времени (темп по­ступления заявок);

Е = 2,7182 - основание натурального логарифма.

Соответствующие значения вероятностей Р(х) нетрудно опре­делить с помощью таблицы пуассоновского распределения. Если, например, средний темп поступления заявок - два клиента в час, то вероятность того, что в течение часа в систему не поступит ни одной заявки, равна 0,135, вероятность появления одной заявки - около 0,27, двух - также около 0,27, три заявки могут появиться с вероятностью 0,18, четыре - с вероятностью около 0,09 и т. д. Вероятность того, что за час в систему поступят 9 заявок или бо­лее, близка нулю.

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

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

Жизнь значительно сложнее. На практике клиенты могут по­кинуть очередь

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

Характеристики очереди:

2) правило обслуживания.

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

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

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

В моделях СМО рассматривают следующие объекты:

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

2) обслуживающие аппараты (ОА), или приборы.

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

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

Заявка может находиться либо в состоянии обслуживания, либо в состоянии ожидания обслуживания.

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

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

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

Важнейшие выходные параметры СМО

Производительность

Пропускная способность

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

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

Коэффициент загрузки оборудования (ОА).

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

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

Простейшие модели СМО

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

М о д е л ьо б с л у ж и в а н и я с о т к а з а м и (рис.5.1)

Рис. 5.1. Модель СМО с отказами:

0 – источник заявок;

1 – обслуживающий прибор;

а – входной поток заявок на обслуживание;

в – выходной поток обслуженных заявок;

с – выходной поток необслуженных заявок.

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

М о д е л ь о б с л у ж и в а н и я с о ж и д а н и е м (рис. 5.2)

Рис. 5.2. Модель СМО с ожиданием

(N– 1) – количество заявок, которое может поместиться в накопителе

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

М о д е л ь о б с л у ж и в а н и я с о г р а н и ч е н н ы м в р е м е н е м

о ж и д а н и я (рис. 5.3)

Рис. 5.4. Многоканальная модель СМО с отказами:

n – количество одинаковых обслуживающих аппаратов (приборов)

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

в р е м е н е м о ж и д а н и я (рис. 5.5)

Рис. 5.6. Многоканальная модельСМО с ожиданием и восстановлением ОА:

e – обслуживающие аппараты, вышедшие из строя;

f – восстановленные обслуживающие аппараты

Данная модель обладает свойствами моделей, представленных на рис. 5.2 и 5.4, а кроме того свойствами, позволяющими учитывать возможные случайные отказы ОА, которые в этом случае поступают в ремонтный блок 2, где пребывают в течение случайных промежутков времени, затрачиваемых на их восстановление, а затем вновь возвращаются в обслуживающий блок 1.

М н о г о к а н а л ь н а я м о д е л ь СМО с о г р а н и ч е н н ы м

в р е м е н е м о ж и д а н и я и в о с с т а н о в л е н и е м ОА (рис. 5.7)

Рис. 5.7. Многоканальная модель СМО с ограниченным временем ожидания и восстановлением ОА

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

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

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

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

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

Таблица 30.1. Примеры систем массового обслуживания

Заявки Каналы Автобусный маршрут и перевозка пассажиров Пассажиры Автобусы Производственный конвейер по обработке деталей Детали, узлы Станки, склады Влетающая на чужую территорию эскадрилья самолетов, которая «обслуживается» зенитками ПВО Самолеты Зенитные орудия, радары, стрелки, снаряды Ствол и рожок автомата, которые «обслуживают» патроны Ствол, рожок Электрические заряды, перемещающиеся в некотором устройстве Каскады технического устройства

Но все эти системы объединены в один класс СМО, поскольку подход к их изучению един. Он состоит в том, что, во-первых, с помощью генератора случайных чисел разыгрываются случайные числа, которые имитируют СЛУЧАЙНЫЕ моменты появления заявок и время их обслуживания в каналах. Но в совокупности эти случайные числа, конечно, подчинены статистическим закономерностям.

К примеру, пусть сказано: «заявки в среднем приходят в количестве 5 штук в час». Это означает, что времена между приходом двух соседних заявок случайны, например: 0.1; 0.3; 0.1; 0.4; 0.2, как это показано на рис. 30.1, но в сумме они дают в среднем 1 (обратите внимание, что в примере это не точно 1, а 1.1 - но зато в другой час эта сумма, например, может быть равной 0.9); и только за достаточно большое время среднее этих чисел станет близким к одному часу.

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

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

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

Перечислим некоторые основные понятия СМО.

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

Очереди характеризуются правилами стояния в очереди (дисциплиной обслуживания), количеством мест в очереди (сколько клиентов максимум может находиться в очереди), структурой очереди (связь между местами в очереди). Бывают ограниченные и неограниченные очереди. Перечислим важнейшие дисциплины обслуживания. FIFO (First In, First Out - первым пришел, первым ушел): если заявка первой пришла в очередь, то она первой уйдет на обслуживание. LIFO (Last In, First Out - последним пришел, первым ушел): если заявка последней пришла в очередь, то она первой уйдет на обслуживание (пример - патроны в рожке автомата). SF (Short Forward - короткие вперед): в первую очередь обслуживаются те заявки из очереди, которые имеют меньшее время обслуживания.

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

Пусть имеется два магазина. В магазине № 1 обслуживание осуществляется в порядке очереди, то есть здесь реализована дисциплина обслуживания FIFO (см. рис. 30.3).

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

В магазине № 2 реализована дисциплина SF (см. рис. 30.4), означающая, что штучный товар можно купить вне очереди, так как время обслуживания t обслуж. такой покупки невелико.

Как видно из обоих рисунков, последний (пятый) покупатель собирается приобрести штучный товар, поэтому время его обслуживания невелико - 0.5 минут. Если этот покупатель придет в магазин № 1, он будет вынужден выстоять в очереди целых 8 минут, в то время как в магазине № 2 его обслужат сразу же, вне очереди. Таким образом, среднее время обслуживания каждого из покупателей в магазине с дисциплиной обслуживания FIFO составит 4 минуты, а в магазине с дисциплиной обслуживания КВ - лишь 2.8 минуты. А общественная польза, экономия времени составит: (1 – 2.8/4) · 100% = 30 процентов! Итак, 30% сэкономленного для общества времени - и это лишь за счет правильного выбора дисциплины обслуживания.

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

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

Судить о результатах работы СМО можно по показателям. Наиболее популярные из них:

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

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

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

вероятность занятости каждого из канала и всех вместе;

среднее время занятости каждого канала;

вероятность занятости всех каналов;

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

вероятность простоя каждого канала;

вероятность простоя всей системы;

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

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

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

среднее время нахождения заявки в системе.

Судить о качестве полученной системы нужно по совокупности значений показателей. При анализе результатов моделирования (показателей) важно также обращать внимание на интересы клиента и интересы владельца системы, то есть минимизировать или максимизировать надо тот или иной показатель, а также на степень их выполнения. Заметим, что чаще всего интересы клиента и владельца между собой не совпадают или совпадают не всегда. Показатели будем обозначать далее H = { h 1 , h 2 , …} .

Параметрами СМО могут быть: интенсивность потока заявок, интенсивность потока обслуживания, среднее время, в течение которого заявка готова ожидать обслуживания в очереди, количество каналов обслуживания, дисциплина обслуживания и так далее. Параметры - это то, что влияет на показатели системы. Параметры будем обозначать далее как R = { r 1 , r 2 , …} .

Пример. Автозаправочная станция (АЗС).

1. Постановка задачи . На рис. 30.5 приведен план АЗС. Рассмотрим метод моделирования СМО на ее примере и план ее исследования. Водители, проезжая по дороге мимо АЗС по дороге, могут захотеть заправить свой автомобиль. Хотят обслужиться (заправить машину бензином) не все автомобилисты подряд; допустим, что из всего потока машин на заправку в среднем заезжает 5 машин в час.

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

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

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

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

В этой формуле величина потока λ должна быть задана (до этого она должна быть определена экспериментально на объекте как статистическое среднее), r - случайное равномерно распределенное число от 0 до 1 из ГСЧ илитаблицы , в которой случайные числа нужно брать подряд (не выбирая специально).

Задача. Сгенерируйте поток из 10 случайных событий с интенсивностью появления событий 5 шт/час.

Решение задачи. Возьмем случайные числа, равномерно распределенные в интервале от 0 до 1 (см. таблицу ), и вычислим их натуральные логарифмы (см. табл. 30.2).

Таблица 30.2. Фрагмент таблицы случайных чисел и их логарифмов

r рр ln(r рр )

Формула пуассоновского потока определяет расстояние между двумя случайными событиями следующим образом: t = –Ln(r рр)/ λ . Тогда, учитывая, что λ = 5 , имеем расстояния между двумя случайными соседними событиями: 0.68, 0.21, 0.31, 0.12 часа. То есть события наступают: первое - в момент времени t = 0 , второе - в момент времени t = 0.68 , третье - в момент времени t = 0.89 , четвертое - в момент времени t = 1.20 , пятое - в момент времени t = 1.32 и так далее. События - приход заявок отразим на первой линейке (см. рис. 30.7).

Рис. 30.7. Временная диаграмма работы СМО

Берется первая заявка и, так как в этот момент каналы свободны, устанавливается на обслуживание в первый канал. Заявка 1 переносится на линейку «1 канал».

Время обслуживания в канале тоже случайное и вычисляется по аналогичной формуле:

где роль интенсивности играет величина потока обслуживания μ 1 или μ 2 , в зависимости от того, какой канал обслуживает заявку. Находим на диаграмме момент окончания обслуживания, откладывая сгенерированное время обслуживания от момента начала обслуживания, и опускаем заявку на линейку «Обслуженные».

Заявка прошла в СМО весь путь. Теперь можно, согласно принципу последовательной проводки заявок, также проимитировать путь второй заявки.

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

Если все места в очереди в момент, когда придет очередная заявка, будут заняты, то заявку следует отправить на линейку «Отказанные». На рис. 30.7 это заявка с номером 6.

Процедуру имитации обслуживания заявок продолжают некоторое время наблюдения T н. Чем больше это время, тем точнее в дальнейшем будут результаты моделирования. Реально для простых систем выбирают T н, равное 50-100 и более часов, хотя иногда лучше мерить эту величину количеством рассмотренных заявок.

За последние десятилетия в самых разных областях народного хозяйства возникла необходимость решения вероятностных задач, связанных с работой систем массового обслуживания. Примерами таких систем служат телефонные станции, ремонтные мастерские, торговые предприятия, билетные кассы и т.д. работа любой системы массового обслуживания состоит в обслуживании поступающего в нее потока требований (вызовы абонентов, при ход покупателей в магазин, требования на выполнение работы в мастерской и т. д.).
Математическая дисциплина, изучающая модели реальных систем массового обслуживания, получила название теории массового обслуживания. Задача теории массового обслуживания - установить зависимость результирующих показателей работы системы массового обслуживания (вероятности того, что требование будет обслужено; математического ожидания числа обслуженных требований и т. д.) от входных показателей (количество приборов в системе, параметров входящего потока требований и т. д.) установить такие зависимости в формульном виде можно только для простых систем массового обслуживания. Изучение же реальных систем проводится путем имитации, или моделирования их работы на ЭВМ с привлечением метода статистических испытаний.
Система массового обслуживания считается заданной, если определены:
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 остановками. Определите показатели эффективности использования СМО.