книги / Прикладная теория систем массового обслуживания.-1

УДК 681.513: 681.518.3 Ю17

Рецензенты:

доктор технических наук, профессор А.В. Частиков (кафедра радиоэлектронных средств Вятского государственного университета);

кандидат технических наук С.Л. Макаренко (директор ИТЦСТ ОАО «МОРИОН», г. Пермь)

Южаков А.А.

Ю17 Прикладная теория систем массового обслуживания: Учеб, пособие / Перм. гос. техн. ун-т. - Пермь, 2005. - 60 с.

ISBN 5-88151-491-2

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

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

Предназначено для студентов специальностей 200 900 «Сети связи и системы коммутации», 210 100 «Управление и информатика в технических системах», 210 200 «Автоматизация технологических процессов и производств», 200 800 «Проектирование и технология радиоэлектронных устройств», изучающих курсы «Прикладная теория систем массового обслуживания», «Передача данных», «Проектирование информаци- онно-управляющих систем», «Сети связи», «Теория телетрафика».

1. ЭЛЕМЕНТЫ ТЕОРИИ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ

1.1.Виды распределения входящего потока

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

Для теории систем массового обслуживания (СМО) особый интерес представляют случайные процессы марковского типа. При помощи мар­ ковских процессов с конечным или счетным множеством состояний опи­ сываются процессы массового обслуживания в системах весьма широкого класса с максимальными аналитическими предпосылками: появление зая­ вок и окончание обслуживания заявок, имеющихся в системе, не должно зависеть от предшествующей истории. А если процесс, протекающий в системе, является марковским с непрерывным временем, то все потоки со­ бытий, переводящие систему из состояния в состояние, являются пуассо­ новскими [1]. Для пуассоновских систем вероятности состояний описыва­ ются с помощью обыкновенных линейных дифференциальных уравнений. Если не делать предположения, что процесс, протекающий в системе мас­ сового обслуживания, является марковским, то аналитическое исследова­ ние работы такой системы требует при вычислении более сложного мате­ матического аппарата. В большинстве задач прикладного характера замена непуассоновских потоков событий пуассоновскими с теми же интенсивно­ стями приводит к получению решения, которое мало отличается от полученного в работе [3].

Однако, как указано в работах [2, 3, 4, 5], имеются особые условия, когда погрешность может достигать значительной величины. В связи с этим приходится использовать случайные процессы более сложного харак­ тера. Общей тенденцией при этом является нахождение такого случайного процесса, связанного с процессом обслуживания, который можно было бы рассматривать как марковский процесс. Один из наиболее известных спе­ циалистов в области теории массового обслуживания Д. Кендалл предло­ жил метод вложенных цепей Маркова [6]. Вложенная цепь Маркова - это последовательность значений процесса в специально выбранные моменты времени. Вложенную цепь Маркова можно определить в том случае, если моменты времени образуют сложную статическую связь, которую нельзя описать цепью Маркова. Важным случаем является полумарковский про­ цесс [5], а развитием его - линейчатые процессы [7]. В дальнейшем рас­ смотрим решения для пуассоновских и непуассоновских систем.

В работах [1-5, 8] исследовались системы массового обслуживания, на которые поступал входной поток заявок с некоторой интенсивностью, причем эта интенсивность не зависела от состояния СМО, а сами источни­ ки находились вне системы и не рассматривались. Такие СМО называются разомкнутыми или открытыми. Значительный интерес представляют так

называемые замкнутые системы [1, 5], в которых интенсивность потока заявок зависит от состояния СМО, а сами источники заявок являются не внешними, а внутренними элементами СМО. Такие системы характерны, например, для области аналого-цифрового преобразования. В них изме­ ряемый входной сигнал канала, находясь на обслуживании (измерении), перестает подавать заявки, а после конца обслуживания снова становится источником заявок. Моделью указанного входного потока является поток Бернулли [5, 9].

1.2. Дисциплина обслуживания заявок

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

Системы с ожиданием [1, 2, 5] бывают двух видов: с бесконечной очередью («чистого» типа) и с конечной очередью («смешанного» типа). В системах с конечной очередью возможны как отказы, так и ожидание заяв­ ки в очереди. Отказы (отсутствие обслуживания) могут быть связаны или с ограниченным числом мест в очереди, или с ограниченным временем ожи­ дания, которым располагает заявка.

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

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

Выбор заявок из очереди на обслуживание и их распределение по каналам может производиться в порядке прибытия [5, 9], случайным обра­ зом [10], в зависимости от приоритета заявки [11]. Изучение систем массо­ вого обслуживания с приоритетами разного типа представляет собой важ­ ную задачу как в общетеоретическом, так и в прикладном отношении.

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

1.3. Канал обслуживания

Основным параметром любой системы массового обслуживания яв­ ляется число каналов обслуживания. Каналом обслуживания называется вся совокупность технических устройств, обеспечивающих обслуживание заявки. Обслуживающее устройство может состоять из одного прибора (однолинейные системы) или нескольких (многолинейные системы). Во­ просы изучения таких СМО достаточно полно рассмотрены, например, в работах [1, 2, 9]. При многолинейном обслуживании приборы могут со­ единяться последовательно с другими для обслуживания заявки [5] или же несколько параллельных приборов могут обслуживать одну заявку [1].

Исследование СМО с приборами разной производительности [1, 3,4, 6, 8] позволяет решать вопросы синтеза с использованием различных об­ рабатывающих приборов. В рассматриваемых в работах [1,3, 4, 6, 8] СМО число обслуживающих приборов и интенсивности обслуживания постоян­ ны. Основной же особенностью ряда приложений является переменное число приборов, требуемых для обслуживания заявок, и изменение интен­ сивности обслуживания заявки [5, 12]. Например, требование входной за­ явки /-го канала на qj разрядов означает, что для обслуживания этой заявки в данный момент времени требуется j обслуживающих приборов. Для решения вопросов разработки СМО с переменным числом обслуживающих приборов и изменяющейся интенсивностью обслуживания необходимы дополнительные исследования.

В многолинейных системах [1,8] большое внимание уделяется во­ просам взаимодействия приборов и заявок. Если в момент поступления требования имеется несколько свободных приборов, то необходимо уточ­ нить, каким образом выбирается прибор (или группа приборов), который будет обслуживать данную заявку. Как правило, рассматриваются два слу­ чая: интенсивности обслуживания всех приборов одинаковы; интенсивно­ сти обслуживания приборов различны (приборы неоднородны). В первом случае нет необходимости различать приборы обслуживания и правило выбора не влияет [8] на число требований в очереди или в системе, но су­ щественно влияет на занятие приборов. Во втором случае от правила вы­ бора зависит функционирование всей системы. В общем случае построе­ ние модели СМО с учетом всех нюансов - задача очень важная и сложная.

На рис. 2.1 прописной буквой обозначена группа источников, а строчными буквами - соответствующие им аппараты. Заметим, что если абоненту А нужно установить связь, то это может быть сделано с помощью свободной линии а ,Ь ,с и т.д. Если же все линии заняты, то абонент либо ожидает включения, либо его вызов теряется, т.е. в этом случае он получа­ ет сигнал, что линия занята. В любом случае важной величиной является вероятность ожидания включения в течение определенного времени или вероятность потери вызова.

Эрланг [2] предположил, что для ограниченного источника, состоя­ щего из N абонентов, п из которых уже обслуживаются, вероятность по­ ступления нового вызова в промежутке времени (/, t + At) равна {N - n)Xdt, где X - средняя интенсивность вызовов в единицу времени. Если число об­ служиваемых независимых абонентов неизвестно, то обычно предполага­ ют, что вероятность поступления в интервале (t, t + А/) одного вызова рав­ на Xdt. В этом случае интервалы между последовательными вызовами имеют экспоненциальное распределение с плотностью ^е_Х/. Это приводит к пуассоновскому распределению потока вызовов, для которого вероят-

(Х/)ле"х'

ность поступления л вызовов за время / составляет -— ------ , где Xt - Ma­ rt!

тематическое ожидание числа вызовов за время /. Это распределение под­ твердилось на практике для периодов интенсивной нагрузки. Оно удовле­ творительно описывает распределение входящего потока. Аналогично, ес­ ли 1/р - средняя продолжительность разговора, то вероятность того, что разговор окончится в промежутке (t, t + At), равна \iAt и не зависит от дли­ тельности разговора и других вызовов. Это свидетельствует о том, что длительности разговора распределены в соответствии с законом ре_ц/.

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

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

2.2.Математические модели полнодоступных систем

2.2.1.Классическая система массового обслуживания с отказами

Анализ работы СМО начнем с рассмотрения возможных состояний системы и составления размеченного графа состояний.

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

jt0 - все каналы свободны, ни одна заявка не обслуживается;

- занят ровно один канал (какой - не важно), обслуживается одна

заявка; Хк- занято ровно к каналов (каких именно - не важно), обслуживает­

ся к заявок; хп- все п каналов заняты, обслуживается п заявок.

Граф возможных состояний системы изображен на рис. 2.2.

*0

Рис. 2.2. Граф состояний полнодоступной системы с отказами

Система уравнений стационарного режима имеет следующий вид:

'-Х/>0+ ц Р |= 0 ,

-{X + k\i)Pk + ХРк.1+ (к + 1)ц Рк+| = 0,

-Щ1Р„+ХР„. i = 0,

2 ^ = 1. I, i=0

где р - интенсивность потока обслуживания прибора; Р, - вероятность /-го состояния системы.

Вероятности состояний могут быть найдены по следующим форму­

лам:

*Л(п9р )9

где р = -X

Р

соновского распределения.

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

1.Вероятность того, что занято ровно к каналов,

р_ Р (к, Р)

*Л(я,р)

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

R (n - 1,р)

к

Л(и,р)

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

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

4. Вероятность того, что канал (любой) занят,

п

5. Вероятность того, что система полностью загружена,

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

-= *

1 X

Пример 2.1. Рассматривается работа районной автоматической теле­ фонной станции (АТС), которая обеспечивает не более 120 переговоров одновременно. Средняя длительность переговоров 1/р = 1 мин. Вызовы на

станцию поступают в среднем через 0,5 с, т.е. 1Л, = 0,5 с. Требуется найти характеристики работы АТС: к ,Р обсу язк, Гзк, Гпк, гнз, /пз, I

Решение. АТС представляет собой 120-канальную систему массового обслуживания с отказами. Параметры системы следующие:

Вероятность того, что канал занят,

к

п 0,931.

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

/ , = —= 1 мин = 60с.

ц

Среднее время простоя канала

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

Вероятность полной загрузки системы

^п .з= 1 -'Р0бс = 0.069.

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

/п.з — —0,5 с. n\i