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

Министерство образования и науки Украины

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

Кафедра ИТ

Курсовой проект

По дисциплине: "Математические методы исследования операций"

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

Выполнил: студентка группы 3ПР2

Могилева У.С.

Проверил: доцент Соколова Н.А.

Нормоконтроллер Соколова Н.А.

Аннотация

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

Объём данной пояснительной записки к курсовому проекту по дисциплине: «Математические методы исследования операций» на тему: «Практическое применение теории массового обслуживания» составляет 39 страниц, количество используемых источников - 4.

Количество приложений - 1.

Данная пояснительная записка содержит следующие разделы: основные элементы ТМО, виды систем массового обслуживания, системы массового обслуживания при наличии входного и выходного потоков, (M/M/1):(GD//), (M/M/1):(GD/N/), (M/M/c):(GD//), принятие решений с использованием моделей массового обслуживания, методы разработки математических моделей в СМО, подготовка исходных данных и проверка статистических гипотез, модели со стоимостными характеристиками, оптимальная скорость обслуживания , оптимальное число обслуживающих приборов, моделирование с учетом предпочтительности уровня обслуживания, линейный способ решения СМО.

Содержание

Введение

1. Основные элементы ТМО

2. Виды систем массового обслуживания

2.1 Системы массового обслуживания при наличии входного и выходного потоков

2.1.1 Система массового обслуживания типа (M/M/1):(GD//)

2.1.2 Система массового обслуживания типа (M/M/1):(GD/N/)

2.1.3 Система массового обслуживания типа (M/M/c):(GD//)

3. Принятие решений с использованием моделей массового обслуживания

3.1 Методы разработки математических моделей в СМО

3.2 Подготовка исходных данных и проверка статистических гипотез

3.3 Модели со стоимостными характеристиками

3.3.1 Оптимальная скорость обслуживания

3.3.2 Оптимальное число обслуживающих приборов

3.4 Моделирование с учетом предпочтительности уровня обслуживания

3.5 Линейный способ решения СМО

Заключение

Список использованной литературы

Приложение А. Решение СМО методом ЗЛП

Список сокращений

Введение

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

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

Для того чтобы понять необходимость ТМО и те последствия, к которым приводит игнорирование случайностей при расчете показателей обслуживания СМО, рассмотрим простейший пример. Пусть на некоторое обслуживающее устройство или обслуживающий прибор поступает поток заявок. Допустим, путем длительных наблюдений мы установили, что среднее число поступающих на прибор заявок постоянно и равно 6 в час. Спрашивается, какую производительность должен иметь прибор, чтобы успешно справляться с поступающим на него потоком заявок? Сам собой напрашивается ответ: прибор должен обслуживать в среднем 6 заявок в час или каждую заявку за 10 мин. Конечно, осторожный проектировщик всегда сделает небольшой запас, скажем, в 10% на всякие непредвиденные обстоятельства и предложит производительность прибора, соответствующую обслуживания одной заявки за 9 мин. Дальнейшее увеличение производительности прибора вряд ли целесообразно, поскольку тогда он будет большую долю времени простаивать. Итак, ответ готов: прибор должен обслуживать заявку в среднем за 9 мин. При этом заявки перед прибором не должны накапливаться, а сам прибор в среднем 6 мин каждый час будет простаивать.

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

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

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

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

1. Основные элементы ТМО

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

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

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

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

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

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

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

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

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

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

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

2. Виды систем массового обслуживания

2.1 Системы массового обслуживания при наличии входного и выходного потоков

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

Рисунок 1

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

(a/b/c): (d/e/f),

где символы a, b, c, d, e и f ассоциированны с конкретными наиболее существенными элементами модельного представления процессов массового обслуживания и интерпретируются следующим образом:

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

b- распределение времени обслуживания (или выбытий обслуженных клиентов)

с - число параллельно функционирующих узлов обслуживания (с=1, 2… );

d- дисциплина очереди;

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

f- емкость источника, генерирующего заявки на обслуживание.

Для конкретизации a и b приняты следующие стандартные обозначения:

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

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

Ek- распределение Эрланга или гамма-распределение интервалов времени между моментами последовательных поступлений требований в обслуживающую систему или продолжительностей обслуживания (при этом под k понимается параметр распределения);

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

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

Для иллюстрации рассмотрим структуру (M/D/10):(GD/N/). В соответствии с принятыми обозначениями здесь речь идет о СМО с пуассоновским входным потоком, фиксированным временем обслуживания и десятью параллельно функционирующими узлами обслуживания. Дисциплина очереди не регламентирована, что подчеркивается парой символов GD. Кроме того, независимо от того, сколько требований поступает на вход обслуживающей системы, данная система (очередь+обслуживаемые клиенты) не может вместить более N требований (клиентов), т.е. клиенты, не попавшие в блок ожидания, вынуждены обслуживаться в другом месте. Наконец, источник, порождающий заявки на обслуживание, имеет неограниченную (бесконечно большую) емкость.

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

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

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

Ls- среднее число находящихся в системе клиентов (заявок на обслуживание);

Lq- среднее число клиентов очереди на обслуживание;

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

Wq - средняя продолжительность пребывания клиента (заявки на обслуживание) в очереди.

По определению

Между Ls и Ws (как и между Lq и Wq) существует строгая взаимосвязь, так что, зная числовые значения одной из этих величин, можно легко найти значение другой величины. В частности, если частота поступлений в систему заявок на обслуживание равняется (интенсивность поступления требований), то мы имеем

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



будем иметь

В общем случае

Это означает, что только часть поступающих заявок на обслуживание действительно "проникает" в систему. Но в любом случае можно установить зависимость ЭФФ от LS Lq следующим образом. По определению

Если средняя скорость обслуживания равняется и, следовательно, средняя продолжительность обслуживания равняется 1/, то справедливо следующее соотношение:

Умножая левую и правую части этого соотношения на , получаем



Последнее соотношение остается справедливым и в том случае, если заменить на ЭФФ. При этом для ЭФФ можно записать

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

Отметим, что в большинстве случаев при вычислении значений рn в рамках соответствующей математической модели особые трудности не встречаются. Что же касается распределений продолжительностей ожидания, то их численная оценка может оказаться далеко не простой. Таким образом, в большинстве случаев удобнее вычислять WS и Wq через LS и Lq.

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

n	0	1	2	3	4	5	6	7	8
рn	0.625	0.234	0.088	0.033	0.012	0.005	0.002	0.001	0

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

На основе приведенных выше исходных данных можно вычислить LS, WS, Wq и Lq. Начнем с определения среднего числа требований, находящихся в обслуживающей системе:

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

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

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

Используя в качестве исходных данных, приведенные в предыдущем примере, вычислим:

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

По определению

Подставляем соответствующие значения

(б) Среднее количество клиентов, которые обслуживаются системой.

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

При увеличении параметра будет увеличиваться LS и Lq, а при увеличении параметра будет уменьшаться WS и Wq.

2.1.1 Система массового обслуживания типа (M/M/1):(GD//)

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

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

Уравнения в конечных разностях для рn(t) выводятся на основе тех же соображений, которые приводились в связи с рассмотрением моделей чистого рождения и чистой гибели. Для достаточно малого, но не равного нулю h(>0) запишем

Вероятность поступления в систему n(n>0) требований в интервале t+h [обозначим эту вероятность через рn(t+h)] складывается из следующих вероятностей:

а) в конце временного интервала t в системе находится n требований, а Р в интервале h не происходит ни поступлений, ни выбытий

б) в конце временного интервала t в системе находится (n-1) требований, а Р в интервале h происходит одно поступление, но не происходитвыбытий

в) в конце временного интервала t в системе находится (n+1) требований, а Р в интервале h не происходит не одного поступления, но происходит одно выбытие.

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



Для n=0 вероятность того, что в интервале h не произойдет ни одного выбытия, естественно, равняется единице. Следовательно,

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

Заметим, что при выводе этой системы дифференциально-разностных уравнений не было сделано никаких аппроксимаций. В этой связи подчеркнем, что аппроксимацию, которая заключается в замене е-h величиной (1-h), не следует принимать в расчет, поскольку при предельном переходе h0 все слагаемые высоко порядка (h2 и выше) все равно обратились бы в нуль.

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

Можно доказать, что стационарное решение существует при t, когда . В предложение, что условие действительно выполняется, нетрудно получить уравнения для стационарного процесса; в этом случае при t необходимо иметь в виду, что р'n(t)0, а рn(t) рn для любого n=0, 1, 2 …. В результате будем иметь

Решение приведенной выше системы уравнений имеет следующий следующий вид:

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

Выражение для LS получается путем элементарных преобразований:

Заметим, что сходимость n обеспечивается за счет выполнения неравенства <1. Используем теперь выведенные ранее формулы, получаем

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

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

В рассматриваемом случае =5 студентов в час, а =60/10=6 студентов в час. Поскольку ==5/6, т.е. меньше единицы, система может функционировать в стационарном режиме. Чтобы иметь представление о том, какое количество ЭВМ необходимо организовать в дисплейном классе, требуется вычислить Lq по формуле

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

где s- подлежащее определению количество ЭВМ.

Используя формулу для рn, можно записать



Учитывая, что

получаем S+10,2. Прологарифмировав обе части данного неравенства (при =5/6), будем иметь

Поскольку значение log(5/6) отрицательное, деление на log(5/6) правой и левой частей приведенного выше неравенства изменяет знак неравенства, т.е. s получаем

Таким образом, для одновременного размещения по крайней мере 80% студентов минимальное число ЭВМ должно быть приблизительно в два раза больше найденного выше значения Lq.

Можно получить и другую важную информацию о функционировании дисплейного класса. Нетрудно вычислить долю времени, в течение которого дисплейный класс вынуждено бездействует. Для этого достаточно определить вероятность такого события равняется р0=1-0,17; т.е. можно утверждать, что доля времени, в течение которого дисплейный класс будет простаивать, составляет 17%. С другой стороны, для оценки времени размещения студента в дисплейном классе необходимо знать сколько времени студент ожидает освобождение компьютера. В данном случае значение этого показателя, обозначенного через WS, равняется



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

Найдем вероятность того, что пришедший студент будет вынужден ждать, пока его не обслужат. Так как вероятность того, что дисплейный класс будет пустовать равно 0,17, то необходимая вероятность равна 1-р0=0,83.

Если параметр будет 12 мин, то система перейдет из стационарной в неустановившуюся, так как очередь со временем будет увеличиваться. Такое же явление будет получено, если интенсивность потока будет больше 5, а скорость обслуживания останется равной 10 мин. По этому нужно стремиться к уменьшению времени обслуживания.

2.1.2 Система массового обслуживания типа (M/M/1):(GD/N/)

Разница между моделью типа (M/M/1):(GD/N/) и моделью типа (M/M/1):(GD//) заключается только в том, что требований, допускаемых в блок ожидания обслуживающей системы, равняется N. Это означает, что при наличии в системе N требований ни одна из дополнительных заявок на обслуживание не может присоединяться к очереди в блоке ожидания. В результате эффективная частота поступлений требований ЭФФ для системы указанного типа становятся меньше частоты , с которой заявки на обслуживание генерируются соответствующим источником.

Дифференциально-разностные уравнения как для n=0, так и 0<n<N имеют такой же вид, как в модели (M/M/1):(GD//). Для n>N имеем pn(t)-0, а для n=N

Таким образом, уравнения для стационарного процесса в случае модели (M/M/1):(GD/N/) записываются следующим образом:

Решение приведенной выше системы уравнений для модели (M/M/1):(GD/N/) имеет вид

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

С учетом приведенной выше формулы для рn выражение для среднего числа находящихся в системе требований принимает следующий вид:

Выражения для Lq,Ws и Wq можно получить из формулы для Ls, если предварительно вывести формулу для ЭФФ. Поскольку вероятность того, что требование не имеет возможности присоединится к очереди, равняется рN, доля требований , которым разрешено войти в блок ожидания, равняется Р{n<N}=1- рN. Отсюда следует, что



Таким образом, нетрудно еще раз убедиться, что

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

Не исключено, что инженеров класса прежде всего интересует количество студентов, которые покидают класс из-за ограниченности мест. Практически это эквивалентно нахождению разности между и ЭФФФ:

В рассматриваемом примере N=5+1=6, =5/6, а

Отсюда следует, что частота возникновения ситуации, когда прибывающий в класс студент не имеет возможности присоединиться к очереди, равняется 5*0,0774=0,387 студента в час; при 8-часовом рабочем дне это эквивалентно тому, что дисплейный класс в среднем за день будет терять три студента.

Пусть требуется определить среднее время пребывания студента в дисплейном классе. Сначала вычислим LS, что позволит затем найти WS: С учетом того, что ЭФФФ=(1-6)=5(1-0,0774)=4,613, получаем

Таким образом, при введение ограничения на количество мест для работы (N=6) среднее время ожидания по сравнению со случаем, когда в дисплейный класс могли попасть все нуждающиеся студенты, сократилось примерно на полчаса. Это было достигнуто за счет "потери" в среднем трех студентов в день из-за недостаточности мест для работы прибывших студентов.

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

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

При увеличении количества ЭВМ на одно количество студентов, которое теряет дисплейный класс, при =5 равно ЭФФрN=1,16 (N=6+1=7). Таким образом в течение 8-ми часового дня класс теряет только одного студента. При увеличении количества ЭВМ уже до 9 класс будет терять 0,00225 студента в час или 0,01125 студента в день (т.е. практически 0). При увеличении параметра , для того чтобы не терять студентов необходимо прямо пропорционально увеличивать количество ЭВМ.

2.1.3 Система массового обслуживания типа (M/M/c):(GD//)

Процесс массового обслуживания, описываемый моделью (M/M/c):(GD//), характеризуется интенсивностью входного потока и тем обстоятельством, что параллельно обслуживаются может не более с клиентов. Средняя продолжительность обслуживания одного клиента равняется 1/. Входной и выходной потоки являются пуассоновскими. Конечная цель использования с параллельно включенных обслуживающих приборов заключается в повышении (по сравнению с одноканальной системой) скорости обслуживания требований за счет обслуживания одновременно с клиентов. Таким образом, если n=c, то интенсивность входного (выходного) потока равняетсяс. С другой стороны, если n<c, то интенсивность входного (выходного) потока равняется n<c (поскольку при этом занятыми обслуживанием окажутся не все обслуживающие приборы, а лишь n(<c) приборов). По существу, использование нескольких обслуживающих приборов эквивалентно использованию одного обслуживающего прибора, быстродействие которого варьируется, увеличиваясь при наличии в системе n требований ровно в n раз.

Таким образом, для анализа модели (M/M/c) требуется построить обобщенную одноканальную модель, в которой как интенсивность входного потока, так и скорость обслуживания зависели бы от n, так что вместо безиндексных параметров и нужно было бы использовать величины n и n. Нужно вывести формулу для вычисления стационарных значений значений р n. Полагая n =, а n =n при n<c или n =с при nc, можно получить числовые оценки для функциональных характеристик системы, описываемой (М/М/с)- моделью. При заданных значениях n и n после нахождения значения р n окажется также возможным получить результаты для СМО других типов.

Для модели (М/М/1):(GD//) справедливы следующие утверждения:

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

Для стационарного режима, получим следующие уравнения:

Эти уравнения можно привести к следующему (более удобному) виду:

Рассматривая последовательно уравнения для р1, р2, р3, … и рассуждая по обычной схеме, реализующей метод индукции, приходим к формулам:

Выражения для р0 получено из условия рn=1.

Таким образом, если СМО относится к типу (M/M/c):(GD//), то для оценки ее операционных характеристик мы исходим из того, что

Из выражения для рn,выведенного для модели (Mn/Mn/1):(GD//) при nc

В случае, когда nс, формула принимает следующий вид:

Полагая , находим



где с<1 (или с<1).

Теперь нетрудно показать, что при приближенный методе нахождения р0 и Lq получаем: при <<1 можно записать

Тогда как для значений /с, близких к единице,

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

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

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

Для анализа задачи улучшения использования библиотек необходимо сравнение двух вариантов, а именно:

(а) варианта с независимыми обслуживающими системами типа (М/М/2): (GD//) при =10 студентов в час и =5,217 обслуживаний студентов в час

(б) варианта с одной очередью типа (М/М/4): (GD//) при =2*10=20 студентов в час и =5,217 обслуживаний студентов в час.

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

Коэффициент загруженности во втором случае будет таким же, как и в первом случае, а именно

Объединение всех четырех библиотек в рамках одной системы не приводит на первый взгляд к эффекту. Если, однако, рассмотреть другие показатели, это первое впечатление не подтвердится. Вычислим Wq (среднее время ожидания студентом обслуживания от момента прихода в библиотеку до момента выдачи книг) в первом и втором случаях. Тогда для с=2 будем иметь

Таким образом,

С другой стороны, для с=4 будем иметь =20/5,217=3,83 и

Следовательно,

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

3. Принятие решений с использованием моделей массового обслуживания

3.1 Методы разработки математических моделей в СМО

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

3.2 Подготовка исходных данных и проверка статистических гипотез

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

Когда осуществлять наблюдение за системой?

Каким образом систематизировать данные?

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

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

а) путем регистрации временных интервалов между последовательными поступлениями заявок на обслуживание и последовательными выходами обслуженных "клиентов" из системы;

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

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

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

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

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

Таблица 1

Порядковый номер прибытия	Время прибытия, мин	Порядковый номер прибытия	Время прибытия, мин	Порядковый номер прибытия	Время прибытия, мин	Порядковый номер прибытия	Время прибытия, мин
1	2	3	4	5	6	7	8
1	5,2	16	67,6	31	132,7	46	227,8
2	6,7	17	69,3	32	142,3	47	233,5
3	9,1	18	78,6	33	145,2	48	239,8
4	12,5	19	86,6	34	154,3	49	243,6
5	18,9	20	91,3	35	155,6	50	250,5
6	22,6	21	97,2	36	166,2	51	255,8
1	2	3	4	5	6	7	8
7	27,4	22	97,9	37	169,2	52	256,5
8	29,9	23	111,5	38	169,5	53	256,9
9	35,4	24	116,7	39	172,4	54	270,3
10	35,7	25	117,3	40	175,3	55	275,1
11	44,4	26	118,2	41	180,1	56	277,1
12	47,1	27	124,1	42	188,8	57	278,1
13	47,5	28	127,4	43	201,2	58	283,6
14	49,7	29	127,6	44	218,4	59	299,8
15	67,1	30	127,8	45	219,9	60	300,0

Данные, приведенные в табл 1. можно использовать для нахождения распределения числа прибытий в единицу времени. Для этого прежде всего выбирается единица измерения времени. В рассматриваемом примере за единицу времени принимается 1ч. из табл 1. видно, что в течение первого часа зарегистрировано 14 прибытий, второго часа - 12 прибытий, третьего часа - 14 прибытий, в течение четвертого часа - 8 прибытий, в течение пятого часа - 12 прибытий. Это означает, что в рассматриваемом пятичасовом интервале число прибытий в 1 ч оказалось равным 8с с частотой 1, 12 с частотой 2 и 14 с частотой 2.

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

Таблица 2

n fn	0	1	2	3	4	5	6	7	8
	0	0	0	0	0	1	0	3	3
n fn	9	10	11	12	13	14	15	16	17
	6	5	9	10	11	8	6	1	0

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

Таблица 3

n	pn	N	pn	N	pn
0	0.0000	6	0.0303	12	0.1138
1	0.0001	7	0.0504	13	0.1020
2	0.0006	8	0.0734	14	0.0848
3	0.0023	9	0.0950	15	0.0659
4	0.0067	10	0.1106	16	0.0479
5	0.0156	11	0.1172	17	0.0834

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

Затем вычистим вероятности pn для пуассоновского распределения со средним значением n=11,65 автомобиля в 1 ч. результаты вычислений приведены в табл 3. заметим, что

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

Теперь нетрудно вычислить значения 2 по формуле

Потребуем, чтобы fn были не менее пяти. В противном случае образуем группы последовательных значений fn, для которых это условие окажется выполненным. Так, например, в табл 3. Следует объединить в одну группу последовательность значений n от нулю до восьми, в результате чего для наблюдаемой частоты будем иметь значение, равное 7=(1+3+3); образуя группу для всех n, превышающих 14, получим для fn значение, также равное 7=(6+1). Теперь обратимся к таблице 4 , иллюстрирующей полученные значения 2.

Таблица 4

n	Fn	en	(fn-en)2 en
0-4	0
5	1
6	0 7	11,3	1,636
7	3
8	3
9	6	5,99	0,000
10	5	6,97	0,557
11	9	7,17	0,356
12	10	6,43	1,117
13	11	5,34	3,248
14	8		1,325
15	6
16	1 7	12,42	2,365
17	0
Суммарные значения	63	63	10,6(значения 2)

Сравним теперь полученные значения 2 с критическим значением для 2-распределения. Для этого требуется задать уровень значимости и число степеней свободы . Величина задается соотношением

В рассматриваемом примере мы имеем восемь составных интервалов. Поскольку среднее значение для пуассоновского распределения вероятностей оценивалось на заданной выборке, имеем =8-1-1=6. Положив уровень значимости равным 0,05, из таблицы значений 2 получаем критическое значение

При использовании 2-критерия выдвигаемая гипотеза относительно характера распределения при заданном уровне значимости принимается, если значение 22(). Поскольку это условие в нашем примере выполняется, принимается гипотеза о том, что приведенная выше выборка соответствует пуассоновскому закону распределения со средним n, равным 11,65 прибытий в 1ч.

3.3 Модели со стоимостными характеристиками

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

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

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

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

3.3.1 Оптимальная скорость обслуживания

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

С1 - выражения в стоимостной форме выигрыш за счет увеличения на единицу значения в течение единичного интервала времени;

С2 - "цена" ожидания (т.е. обусловленные вынужденным ожиданием экономические потери) в единицу времени и в расчете на одно требование;

ТС() - стоимостный показатель, определяемый формулой

ТС ()=С1+ С2LS

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

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

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

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

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

Нетрудно убедиться, что скорость считывания, равная 100 перфокартам в минуту, эквивалентна 100*8*60=48000 перфокарт в день, или 48000/1000=48 программно-вычислительных реализаций в день. Полагая, что количество рабочих дней в одном месяце равняется 22, устанавливаемое на месяц указанное выше повышение быстродействия считывающего устройства обходится клиентуре 100 долл./22=4,55 долл. В день. Поскольку именно такое повышение быстродействия считывающего устройства позволяет ежедневно реализовать на ЭВМ на 48 процедур больше. Плата за реализацию одной дополнительной процедуры равняется 4,55 долл./48=0,0948 долл. Используя введенные выше обозначения, имеем С1 =0,0948 долл. Поскольку С2=10 долл. За одну процедуру в день, а =50 процедур день, получаем оптимальное значение : процедуры в день.

...