TERMINATE 6 страница

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

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

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

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

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

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

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

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

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

1. Показатели эффективности использования СМО:

· Абсолютная пропускная способность СМО - среднее число заявок, которое сможет обслужить СМО в единицу времени.

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

· Средняя продолжительность периода занятости СМО.

· Коэффициент использования СМО - средняя доля времени, в течении которого СМО занята обслуживанием заявок, и т.п.

2. Показатели качества обслуживания заявок:

· Среднее время ожидания заявки в очереди.

· Среднее время пребывания заявки в СМО.

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

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

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

· Закон распределения времени пребывания заявки в СМО.

· Среднее число заявок, пребывающих в очереди.

· Среднее число заявок, находящихся в СМО, и т.п.

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

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

Впервые задачи такого типа были решены в работах А. К. Эрланга в начале прошлого века и легли в основу «Теории массового обслуживания», которая успешно развивается в настоящее время. Большой вклад в развитие этой теории внесли российские математики А.Я.Хинчин, Б.В.Гнеденко, А.Н.Колмогоров, Е.С.Вентцель и др.

3.1.2 Классификация и способы представления СМО.

Классификация СМО осуществляется по различным признакам:

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

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

· В зависимости от числа мест в очереди:

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

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

· По способу отбора для обслуживания заявок из очереди:

Чаще всего применяется дисциплина: «первым пришел — первым обслуживается». Но возможны и другие порядки обслуживания:

ü «первым пришел — последним обслужен»,

ü случайный порядок обслуживания,

ü обслуживание с приоритетами.

· В зависимости от расположения каналов в системе обслуживания:

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

- последовательное расположение каналов обслуживания..

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

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

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

А/В/m/k/M (жирным шрифтом выделены обязательные для заполнения поля), где:

А – распределение времени между поступлением заявок,

В - распределение времени обслуживания заявок,

m – количество обслуживающих приборов,

к – ограничение на количество мест в очереди (по умолчанию − ∞),

М - ограничение на количество заявок в системе (по умолчанию − ∞),

В полях А и Вдопускаются следующие обозначения:

М – экспоненциальный (показательный) закон

распределения вероятностей соответствующей

случайной величины,

D – постоянное время обслуживания,

G – любой (произвольный) закон.

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

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

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

Рис. 3.2 Размеченный граф состояний СМО.

Система может находиться в одном из трех состояний: S₀ – канал свободен, простаивает; S₁ – канал занят обслуживанием; S₂ - канал занят обслуживанием и одна заявка в очереди.

Переход системы из состояния S0 в S1 происходит под воздействием простейшего потока заявок интенсивностью λ₀₁ , а из состояния S1 в состояние S0 систему переводит поток обслуживания с интенсивностью λ₁₀. Граф состояний системы обслуживания с проставленными интенсивностями потоков у стрелок называется размеченным. Поскольку пребывание системы в том или ином состоянии носит вероятностный характер, то вероятность рi(t) того, что система будет находиться в состоянии Si в момент времени t, называется вероятностью i-го состояния СМО и определяется числом поступивших заявок k на обслуживание.

Случайный процесс, происходящий в системе, заключается в том, что в случайные моменты времени t0, t1, t2, ….., tk ,….., tn система оказывается в том или другом заранее известном дискретном состоянии последовательно. Такая случайная последовательность событий называется Марковской цепью, если для каждого шага вероятность перехода из одного состояния Si в любое другое Sj не зависит от того, когда и как система перешла в состояние Si. Описывается Марковская цепь с помощью вероятности состояний, причем они образуют полную группу событий, поэтому их сумма равна единице. Если вероятность перехода не зависит от номера k, то Марковская цепь называется однородной. Зная начальное состояние системы обслуживания, можно найти вероятность состояний для любого значения k – числа заявок, поступивших на обслуживание.

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

3.1.3 Потоки событий СМО.

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

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

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

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

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

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

Чаще всего считается, что входной и выходной потоки могут быть отнесены к простейшим. Предположим, статистические наблюдения позволили получить величину λ­ среднего число заявок, появляющихся за единицу времени (интенсивность входного потока). Интенсивность простейшего потока постоянна в силу его стационарности. Обратная ей величина 1/ λ, — средний интервал времени между двумя соседними заявками.

λ ­ параметр потока, может быть выражен в разных единицах:

Плотность вероятности входного потока описывается функцией:

f (t) = λ e^-λτ, t≥0. (3.1)

Математическое ожидание ­1/ λ, (3.2)

Дисперсия ­ 1/ λ2, (3.3)

Среднеквадратичное отклонение ­ 1/ λ. (3.4)

Поток с такими свойствами называется потоком с показательным (экспоненциальным) законом распределения.

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

Обратная величина 1/ μ определяет среднее время обслуживания одной заявки.

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

Обозначив отношение λ/μ через р, можно показать, что стационарный режим устанавливается при р < 1. Величину р называют нагрузкой системы.

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

• коэффициент простоя системы

Е₁ = 1-р, (3.5)

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

Е₂ = p/(1-p), (3.6)

• средняя длина очереди

Е₃= p²(1-p), (3.7)

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

Е₄ =l /(μ-λ), (3.8)

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

Е₅ = р/(μ-λ). (3.9)

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

3.1.4 Пример простой СМО.

В качестве примера применения системы массового обслуживания рассмотрим задачу проектирования автозаправочной станции (АЗС).

Пример 3.1 Пусть необходимо выбрать один из нескольких вариантов строительства АЗС. Автомобили прибывают на станцию случайным образом и, если не могут быть обслужены сразу, становятся в очередь. Дисциплина очереди: «первым пришел — первым обслужен». Предположим для простоты, что во всех вариантах рассматривается только одна бензоколонка, а вариант от варианта отличается лишь ее мощностью. Средний интервал времени между прибытием автомобилей ( ) составляет 4 минуты и не зависит от варианта строительства.

Величина среднего времени обслуживания одного автомобиля ( )зависит от выбранного варианта строительства АЭС и составляет (соответственно вариантам): 5 мин, 3,5 мин, 2 мин, 1 мин, 0,5 мин. Результаты расчетов по исследованию раз­личных вариантов строительства АЗС по формулам (3.5 ÷3.9) сведены в табл. 3.1:

Таблица 3.1

Из анализа результатов расчетов следует.

Первый вариант строительства АЗС не годен из-за того, что очередь в этом случае будет расти до бесконечности (р>1).

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

р = 0,88 и, следовательно, малой средней доли простоя оборудо­вания Е₁ = 0,13, но при этом варианте возникают большие очереди и, следовательно, большие средние времена простоя автомобилей Е₄ ≈ 27 мин.

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

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

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

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

Вопросы по теме

1. Каковы основные составляющие систем массового обслуживания? Каковы могут быть устройства блоков обслуживания?

2. Каковы могут быть порядки обслуживания очередей?

3. Какими показателями характеризуются системы массового обслуживания?

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

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

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

3.2 Имитационное моделирование

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

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

3.2.1 Общие сведения о GPSSW (язык имитационного моделирования GPSS в среде ОС WINDOWS).

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

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

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

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

Рисунок 3.3 Процесс моделирования в GPSSW.

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

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

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

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

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

· Аппаратные объекты GPSSW — соответствуют обслуживающим приборам (устройствам) в СМО. К ним относятся одноканальные и многоканальные устройства. Одноканальное устройство, которое для краткости далее будем называть просто устройством, может обслуживать одновременно только один транзакт. Многоканальное устройство (МКУ) может обслуживать одновременно несколько транзактов. Многоканальное устройство иногда называют памятью.

· Статистические объекты GPSSW служат для сбора и обработки статистических данных о функционировании модели. К ним относятся очереди и таблицы. Каждая очередь обеспечивает сбор и обработку данных о транзактах, задержанных в какой-либо точке модели, например перед одноканальным устройством.

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

· Запоминающие объекты GPSS/PC обеспечивают хранение в памяти ПК отдельных величин, используемых в модели, а также массивов таких величин. К ним относятся так называемые сохраняемые величины и матрицы сохраняемых величин.

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

3.2.2 Управление последовательностью выполнения программы GPSS: понятие симулятора и таймера модельного времени.

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

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

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