1 Антюхов В.И.

2 Тема 3. Теория массового обслуживания Лекция: Классификация систем массового обслуживания (СМО) и решаемые ими задачи Учебные вопросы: 1.Классификация СМО 2.Показатели эффективности работы СМО 3.Характеристики входного потока заявок и времени обслуживания

3 Учебный вопрос 1 Классификация систем массового обслуживания (СМО)

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

5 Учебный вопрос 1. Классификация СМО Системы массового обслуживания рассматриваются в теории массового обслуживания Теория массового обслуживания – это теория математического моделирования обширного класса случайных процессов - процессов массового обслуживания со счётным числом состояний и непрерывным временем переходов Целью применения моделей массового обслуживания является раскрытие закономерностей этого класса случайных процессов для обоснования решений

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

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

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

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

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

11 Учебный вопрос 1. Классификация СМО В качестве таких показателей, в зависимости от обстановки и целей исследования, могут применяться различные величины: - среднее число заявок, обслуживаемых СМО в единицу времени; - среднее число занятых каналов; - среднее число заявок в очереди; - среднее время ожидания обслуживания; - вероятность того, что число заявок в очереди не превысит какое-то значение и т.д.

12 Учебный вопрос 1. Классификация СМО Системы массового обслуживания различаются видом закона распределения заявок, поступающих в них: - законом распределения числа заявок, поступающих в систему за заданное время; - законом распределения промежутка времени между поступлениями в систему очередных заявок

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

14 Учебный вопрос 1. Классификация СМО 2. По характеру обслуживания заявок: - замкнутые СМО; - разомкнутые СМО В замкнутых СМО обслуживаются ограниченное число потребителей и обслуженная заявка через некоторое время вновь возвращается на обслуживание В разомкнутых СМО поток, поступающих на обслуживание заявок, практически нескончаем

15 Учебный вопрос 1. Классификация СМО 3. По числу каналов обслуживания различают: - одноканальные СМО; - многоканальные СМО 4. По производительности каналов обслуживания выделяют: - СМО с каналами одинаковой производительности; - СМО с каналами различной производительности

16 Учебный вопрос 1. Классификация СМО 5. По необходимости восстановления каналов обслуживания: - СМО с восстановлением вышедших из строя каналов; - СМО без восстановления вышедших из строя каналов

17 Учебный вопрос 1. Классификация СМО 6. По дисциплине ожидания заявками обслуживания различают: 1. СМО с отказами. В таких системах заявка, поступившая в момент, когда все каналы обслуживания заняты, получает «отказ» и покидает систему не обслуженной 2. СМО с бесконечным (неограниченным) ожиданием. Заявка, нашедшая все каналы занятыми, становится в очередь и сколь угодно долго ожидает своего обслуживания 3. СМО смешанного типа. В системах смешанного типа накладываются ограничения либо на длину очереди, либо на время пребывания заявки в очереди

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

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

20 Учебный вопрос 2 Показатели эффективности работы СМО

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

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

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

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

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

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

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

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

29 Учебный вопрос 3 Характеристики входного потока заявок и времени обслуживания

30 Учебный вопрос 3. Характеристики входного потока заявок и времени обслуживания При анализе процесса функционирования системы в целях установления её наилучшей организации первым шагом в исследовании является рассмотрение входящего потока объектов обслуживания Входящий поток может быть: - регулярным; - случайным Регулярным называется такой поток, при котором заявки поступают в систему через строго одинаковые интервалы времени Для регулярного потока dt 1 =dt 2 =dt 3...=dt i =dt

31 Учебный вопрос 3. Характеристики входного потока заявок и времени обслуживания Случайным считается такой поток, при котором заявки поступают в СМО одна за другой в произвольные моменты времени Для случайного потока dt 1 dt 2 dt 3... dt i dt Простейшим потоком заявок считается поток, одновременно обладающий свойствами стационарности, ординарности и отсутствия последействия

32 Учебный вопрос 3. Характеристики входного потока заявок и времени обслуживания Функционирование систем может протекать в стационарном или нестационарном режиме Случайный поток заявок считается стационарным, если вероятность попадания того или иного числа заявок на интервал времени длиной t зависит только от длины этого интервала и не зависит от того, где именно на оси времени расположен этот интервал Иными словами характер стационарного потока не зависит от времени

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

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

35 Учебный вопрос 3. Характеристики входного потока заявок и времени обслуживания Определим для простейшего потока вероятность p m того, что за время t в систему поступит ровно m заявок Обозначим через математическое ожидание числа заявок, поступающих в систему за единицу времени Параметр называют интенсивностью (плотностью) потока заявок

36 Учебный вопрос 3. Характеристики входного потока заявок и времени обслуживания Разобьем промежуток времени t на n элементарных промежутков времени: dt = t /n При ординарном потоке и n можно с точностью до бесконечно малых высших порядков считать, что за время dt в систему поступит одна заявка или ни одной Если обозначить вероятности этих событий p 1 и p 0, получим, что p 1 +p 0 = 1

37 Учебный вопрос 3. Характеристики входного потока заявок и времени обслуживания При стационарном потоке математическое ожидание числа заявок, поступающих за время dt, равно m * = dt С другой стороны эта же величина определяется по формуле: m * =1*p 1 +0*p 0 = p 1 Отсюда следует, что p 1 = dt, т.е. вероятность поступления в систему заявки за элементарный промежуток времени dt численно равна математическому ожиданию числа заявок, поступающих в систему за этот промежуток, а p 0 =1- dt

38 Учебный вопрос 3. Характеристики входного потока заявок и времени обслуживания Так как рассматривается поток без последействия, то вероятность поступления m заявок за n элементарных промежутков времени определится по формуле биноминального закона:

39 Учебный вопрос 3. Характеристики входного потока заявок и времени обслуживания Искомая вероятность p m поступления ровно m заявок может быть найдена из условия стремления n к бесконечности: При стремлении n к бесконечности, первый сомножитель C n 1

40 Учебный вопрос 3. Характеристики входного потока заявок и времени обслуживания Аналогично, При этом: В результате получим выражение (закон Пуассона): где: a = t - математическое ожидание числа заявок, поступающих в систему за время t

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

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

43 Учебный вопрос 3. Характеристики входного потока заявок и времени обслуживания Для нахождения функции распределения определим для начала вероятность противоположного события не поступления в СМО за время t ни одной заявки При пуассоновском потоке заявок эта вероятность равна (m = 0): p 0 =exp(- t) Поэтому функция распределения равна: F(t)=1-exp(- t), а плотность распределения определяется соотношением: F(t)=F'(t)=exp(- t)

44 Учебный вопрос 3. Характеристики входного потока заявок и времени обслуживания Математическое ожидание времени между поступлениями заявок равно: Полученный закон распределения является показательным

45 Учебный вопрос 3. Характеристики входного потока заявок и времени обслуживания Показательный закон обладает следующим свойством: - как бы долго ни длился промежуток времени, распределенный по показательному закону, закон оставшийся части промежутка является также показательным Таким образом, при простейшем потоке число поступающих за время t заявок подчиняется закону Пуассона, а распределение промежутка времени между поступлениями очередных заявок показательному закону распределения

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

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