Материал. Лекции теория массового обслуживания для студентов экономических специальностей очной, заочной и дистанционной форм обучения Шахты 2006
 Скачать 0.66 Mb.
|
|
Министерство Образования Российской Федерации ЮЖНО-РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ЭКОНОМИКИ И СЕРВИСА (ЮРГУЭС) Саакян ГР. ЛЕКЦИИ ТЕОРИЯ МАССОВОГО ОБСЛУЖИВАНИЯ для студентов экономических специальностей очной, заочной и дистанционной форм обучения Шахты 2006 ТЕОРИЯ МАССОВОГО ОБСЛУЖИВАНИЯ Введение Сложный характер рыночной экономики и современный уровень предъявляемых к ней требований стимулируют использование более серьезных методов анализа ее теоретических и практических проблем. В последние десятилетия значительный вес в экономических исследованиях приобрели математические методы. Математическое моделирование все более и более становится одним из основных и наиболее плодотворных методов изучения экономических процессов и объектов. Математический анализ экономических задач органично превращается в часть экономики. Положительная оценка этого подтверждается и тем, что начиная с 1969 г. Нобелевские премии в области экономики присуждаются, как правило, за экономико-математические исследования. Одним из важных разделов экономико-математического моделирования является теория массового обслуживания, представляющая собой теоретические основы эффективного конструирования и эксплуатации систем массового обслуживания. Системы массового обслуживания (СМО) встречаются во многих областях экономики (производство, техника, военная область, быт и др) и предназначены для многократного использования при выполнении однотипных задач. В борьбу за клиента в современной экономике вкладываются огромные средства. По оценкам западных экономистов, завоевание фирмой нового клиента обходится ей враз дороже, чем удержание существующих покупателей. А если клиент ушел неудовлетворенным, тона его возвращение приходится потратить враз больше средств. Во многих случаях неудовлетворенность клиента вызвана неудачной организацией его обслуживания (слишком долгое ожидание в очереди, отказ в обслуживании и т.д.). Использование теории массового обслуживания позволяет фирме избежать подобных неприятностей. Основоположником теории массового обслуживания считается датский ученый А. К. Эрланг. Являясь сотрудником Копенгагенской телефонной компании, он опубликовал в 1909 году работу Теория вероятностей и телефонные переговоры, в которой решил ряд задач по теории систем массового обслуживания с отказами. Значительный вклад в создание и разработку общей теории массового обслуживания внес выдающийся советский математик Александр Яковлевич Хинчин (1984 – 1959), который предложил сам термин теория массового обслуживания. В зарубежной литературе чаще используется название теория очередей. Предмет, цель и задачи теории массового обслуживания Во многих областях производства, бытового обслуживания, экономики и финансов важную роль играют системы специального вида, реализующие многократное выполнение однотипных задач. Подобные системы называют системами массового обслуживания (СМО). В качестве примеров СМО в финансово-экономической сфере можно привести системы, представляющие собой банки, страховые организации, налоговые инспекции, аудиторские службы. В сфере производства и обслуживания примерами СМО могут служить различные системы связи (в том числе телефонные станции, погрузочно-разгрузочные комплексы (порты, товарные станции, автозаправочные станции, магазины, парикмахерские, билетные кассы, пункты обмена валюты, ремонтные мастерские, больницы и т.д. Такие системы как компьютерные сети, системы сбора, хранения и обработки информации, транспортные системы, автоматизированные производственные участки ив военной области, системы противовоздушной или противоракетной обороны также могут рассматриваться как своеобразные СМО. 1 Теоретически в общем случае система определяется как целостное множество взаимосвязанных элементов, которое нельзя расчленить на независимые подмножества. Каждая СМО включает в свою структуру некоторое число обслуживающих устройств единиц, приборов, линий, которые называют каналами обслуживания. Роль каналов могут играть лица, выполняющие те или иные операции (кассиры, операторы, продавцы, парикмахеры и т.д.), линии связи, автомашины, краны, ремонтные бригады, железнодорожные пути, бензоколонки и т.д. Каждая СМО предназначена для обслуживания (выполнения) некоторого потока 2 заявок или требований, поступающих на вход системы большей частью нерегулярно, а в случайные моменты времени. Обслуживание заявок, в общем случае, также длится непостоянное, заранее известное, а случайное время. После обслуживания заявки канал освобождается и готов к приему следующей заявки. Случайный характер потока и времени их обслуживания приводит к неравномерной загруженности СМО: в некоторые промежутки времени на входе СМО могут скапливаться необслуженные заявки (они либо становятся в очередь, либо покидают СМО необслуженными), в другие же периоды при свободных каналах на входе СМО заявок не будет, что приводит к недогрузке СМО, тек простаиванию каналов. Схема СМО изображена на рисунке 1. Рисунок 1. Таким образом, во всякой СМО можно выделить следующие основные элементы 1) входящий поток заявок 2) очередь 3) каналы обслуживания 4) выходящий поток обслуженных заявок. Каждая СМО в зависимости от своих параметров характера потока заявок, числа каналов обслуживания и их производительности, а также отправил организации работы, обладает определенной эффективностью функционирования (пропускной способностью, позволяющей ей более или менее успешно справляться с потоком заявок. Предметом изучения теории массового обслуживания являются СМО. Цель теории массового обслуживания – выработка рекомендаций по рациональному построению СМО, рациональной организации их работы и регулированию потока заявок для обеспечения высокой эффективности функционирования СМО. Для достижения этой цели ставятся задачи теории массового обслуживания, состоящие в установлении зависимостей эффективности функционирования СМО от ее организации (параметров характера потока заявок, числа каналов и их производительности и правил работы СМО. 2 Потоком событий (в данном случае, заявок) называют последовательность событий, наступающих одно за другим в какие-то заранее неизвестные, случайные моменты времени. Входящий поток заявок Вход Поток необслуженных (покинувших очередь заявок Выход Поток обслуженных заявок В качестве характеристик эффективности функционирования СМО можно выбрать три основные группы (обычно средних) показателей 1. Показатели эффективности использования СМО: 1.1. Абсолютная пропускная способность СМО – среднее число заявок, которое сможет обслужить СМО в единицу времени. 1.2. Относительная пропускная способность СМО – отношение среднего числа заявок, обслуживаемых СМО в единицу времени, к среднему числу поступивших за это же время заявок. 1.3. Средняя продолжительность периода занятости СМО. 1.4. Коэффициент использования СМО – средняя доля времени, в течение которого СМО занята обслуживанием заявок, и т.п. 2. Показатели качества обслуживания заявок 2.1. Среднее время ожидания заявки в очереди. 2.2. Среднее время пребывания заявки в СМО. 2.3. Вероятность отказа заявке в обслуживании без ожидания. 2.4. Вероятность того, что вновь поступившая заявка немедленно будет принята к обслуживанию. Закон распределения времени ожидания заявки в очереди. 2.6. Закон распределения времени пребывания заявки в СМО. 2.7. Среднее число заявок, находящихся в очереди. 2.8. Среднее число заявок, находящихся в СМО, и т.п. 3. Показатели эффективности функционирования пары «СМО – клиент, где под клиентом понимают всю совокупность заявок или некий их источник. К числу таких показателей относится, например, средний доход, приносимый СМО в единицу времени, и т.п. Случайный характер потока заявок и длительности их обслуживания порождает в СМО случайный процесс. Определение. Случайным процессом (или случайной функцией) называется соответствие, при котором каждому значению аргумента (в данном случае – моменту из промежутка времени проводимого опыта) ставится в соответствие случайная величина (в данном случае – состояние СМО). Поэтому для решения задач теории массового обслуживания необходимо изучить случайный процесс, протекающий в СМО, те. необходимо построить и проанализировать его математическую модель. Математический анализ работы СМО существенно упрощается, если этот случайный процесс удовлетворяет определенным условиям, которые будут рассмотрены ниже. Классификация систем массового обслуживания Системы массового обслуживания делятся на типы (или классы) по ряду признаков. По числу каналов СМО подразделяют на одноканальные (когда имеется один канал обслуживания) и многоканальные, точнее канальные (когда количество каналов 2 ≥ n ). Здесь и далее будем полагать, что каждый канал одновременно может обслуживать только одну заявку и, если не оговорено специально, каждая находящаяся под обслуживанием заявка обслуживается только одним каналом. Многоканальные СМО могут состоять из однородных каналов, либо из разнородных, отличающихся длительностью обслуживания одной заявки. Практически время обслуживания каналом одной заявки об является непрерывной случайной величиной. Однако при условии абсолютной однородности поступающих заявок и каналов время обслуживания может быть и величиной постоянной (об. По дисциплине обслуживания СМО подразделяют натри класса 4 1. СМО с отказами, в которых заявка, поступившая на вход СМО в момент, когда все каналы заняты, получает отказ и покидает СМО (пропадает. Чтобы эта заявка все же была обслужена, она должна снова поступить на вход СМО и рассматриваться при этом как заявка, поступившая впервые. Примером СМО с отказами может служить работа АТС если набранный телефонный номер (заявка, поступившая на вход) занят, то заявка получает отказ, и, чтобы дозвониться поэтому номеру, следует его набрать еще раз (заявка поступает на вход как новая. 2. СМО с ожиданием (неограниченным ожиданием или очередью. В таких системах заявка, поступившая в момент занятости всех каналов, становится в очередь и ожидает освобождения канала, который примет ее к обслуживанию. Каждая заявка, поступившая на вход, в конце концов будет обслужена. Такие СМО часто встречаются в торговле, в сфере бытового и медицинского обслуживания, на предприятиях (например, обслуживание станков бригадой наладчиков. 3. СМО смешанного типа (с ограниченным ожиданием. Это такие системы, в которых на пребывание заявки в очереди накладываются некоторые ограничения. Эти ограничения могут накладываться на длину очереди, те. максимально возможное число заявок, которые одновременно могут находиться в очереди. В качестве примера такой системы можно привести мастерскую по ремонту автомобилей, имеющую ограниченную по размерам стоянку для неисправных машин, ожидающих ремонта. Ограничения ожидания могут касаться времени пребывания заявки в очереди, по истечению которого она выходит из очереди и покидает систему, либо касаться общего времени пребывания заявки в СМО (те. суммарного времени пребывания заявки в очереди и под обслуживанием. В СМО с ожиданием ив СМО смешанного типа применяются различные схемы обслуживания заявок из очереди. Обслуживание может быть упорядоченным, когда заявки из очереди обслуживаются в порядке их поступления в систему, и неупорядоченным, при котором заявки из очереди обслуживаются в случайном порядке. Иногда применяется обслуживание с приоритетом, когда некоторые заявки из очереди считаются приоритетными и поэтому обслуживаются в первую очередь. По ограничению потока заявок СМО делятся на замкнутые и открытые. Если поток заявок ограничен и заявки, покинувшие систему, могут в нее возвращаться, то СМО является замкнутой, в противном случае – открытой. Классическим примером замкнутой СМО служит работа бригады наладчиков в цеху. Станки являются источниками заявок на обслуживание, и их количество ограничено, наладчики – каналы обслуживания. После проведения ремонтных работ вышедший из строя станок снова становится источником заявок на обслуживание. В открытой СМО характеристики потока заявок не зависят оттого, в каком состоянии сама СМО (сколько каналов занято. В замкнутой СМО – зависят. Так, в рассмотренном выше примере интенсивность потока заявок со стороны станков (те. количество заявок в единицу времени) зависит оттого, сколько их неисправно и ждет наладки. По количеству этапов обслуживания СМО делятся на однофазные и многофазные системы. Если каналы СМО однородны, те. выполняют одну и туже операцию обслуживания, то такие СМО называются однофазными. Если каналы обслуживания расположены последовательно и они неоднородны, так как выполняют различные операции обслуживания те. обслуживание состоит из нескольких последовательных этапов или фаз, то СМО называется многофазной. Примером работы многофазной СМО является обслуживание автомобилей на станции технического обслуживания (мойка, диагностирование и т.д.). Далее будем рассматривать только однофазные СМО. Случайные процессы с дискретными состояниями Случайный процесс, протекающий в СМО, состоит в том, что система в случайные моменты времени переходит из одного состояния в другое меняется число занятых каналов, число заявок, стоящих в очереди, и т.п. Это означает, что СМО представляет собой физическую систему дискретного типа с конечным (или счетным) множеством состояний, а переход системы из одного состояния в другое происходит скачком, в момент, когда осуществляется какое-то событие (приход новой заявки, освобождение канала, уход заявки из очереди и т.п.). Рассмотрим физическую систему X сне более, чем счетным множеством состояний ,... ,..., , 2 В любой момент времени t система X может быть водном из этих состояний. Обозначим ) (t p k ,...) ,..., 2 , 1 ( n k = вероятность того, что в момент t система будет находиться в состоянии. Очевидно, для любого Случайные процессы с дискретными состояниями (не более, чем счетным множеством состояний) бывают двух типов с дискретным или непрерывным временем. Первые отличаются тем, что переходы из состояния в состояние могут происходить только в строго определенные, разделенные конечными интервалами моменты времени ,... , 2 1 t t Случайные процессы с непрерывным временем отличаются тем, что переход системы из состояния в состояние возможен в любой момент времени В качестве примера дискретной системы X , в которой протекает случайный процесс с непрерывным временем, рассмотрим группу из n самолетов, совершающих налет натер- риторию противника, обороняемую системой ПВО. Ни момент обнаружения группы, ни момент начала работы пусковых установок системы ПВО заранее неизвестны. Различные состояния системы соответствуют различному числу пораженных самолетов в составе группы 0 x – не уничтожено ни одного самолета, 1 x – уничтожен ровно один самолет, ……………………………………. n x – уничтожены все n самолетов. Схема возможных состояний системы и возможных переходов из состояния в состояние показана на рисунке 2 (такая схема называется графом состояний. Рисунок 2. Стрелками показаны возможные переходы системы из состояния в состояние. Закругленная стрелка, направленная из состояния k x в негоже, означает, что система может не только перейти в соседнее состояние 1 + k x , но и остаться в прежнем. Для данной системы характерны необратимые переходы (уничтоженные самолеты не восстанавливаются в связи с этим из состояния n x никакие переходы в другие состояния уже невозможны. Отметим, что граф состояний на рис. 2 показывает только переходы из состояния в соседнее состояние и не показывает перескоки через состояние эти перескоки отброшены 3 В математике счетным называется бесконечное множество, элементы которого можно перенумеровать, те. записать в виде последовательности ,... ,..., , 2 1 n a a a . Если множествоконечное или счетное, то его называют не более, чем счетным. ... 0 x 1 x 2 x n x как практически невозможные. Действительно, для того чтобы система перескочила через состояние, нужно, чтобы строго одновременно были поражены два или более самолета, а вероятность такого события равна нулю. Случайные процессы, протекающие в СМО, как правило, представляют собой процессы с непрерывным временем. Это связано со случайностью потока заявок. В противоположность системе с необратимыми переходами, рассмотренной в предыдущем примере, для СМО характерны обратимые переходы занятый канал может освободиться. В качестве примера рассмотрим одноканальную СМО (например, одну телефонную линию, в которой заявка, заставшая канал занятым, не становится в очередь, а покидает систему (получает отказ. Это – дискретная система с непрерывным временем и двумя возможными состояниями 0 x – канал свободен, 1 x – канал занят. Переходы из состояния в состояние обратимы. Граф состояний показан на рисунке 3. Рисунок 3. Для того чтобы описать случайный процесс, протекающий в дискретной системе с непрерывным временем, прежде всего нужно проанализировать причины, вызывающие переход системы из состояния в состояние. Для СМО основным фактором, обусловливающим протекающие в ней процессы, является поток заявок. Поэтому математическое описание любой СМО начинается с потока заявок. Потоки событий Под потоком событий понимается последовательность однородных событий, следующих одно за другим в какие-то случайные моменты времени (например, поток вызовов на телефонной станции, поток покупателей, поток заказных писем, поступающих в почтовое отделение и т.п.). Поток характеризуется интенсивностью λ – частотой появления событий или средним числом событий, поступающих в СМО в единицу времени. Поток событий называется регулярным, если события следуют одно за другим через определенные равные промежутки времени. Например, поток изделий на конвейере сборочного цеха (с постоянной скоростью движения) является регулярным. Такой поток сравнительно редко встречается в реальных системах, но представляет интерес как предельный случай. Типичным для системы массового обслуживания является случайный поток заявок. В этом пункте мы рассмотрим потоки событий, обладающие некоторыми особенно простыми свойствами. Для этого введем ряд определений. 1. Поток событий называется стационарным, если его вероятностные характеристики не зависят от времени. В частности, интенсивность стационарного потока есть величина постоянная λ λ = ) ( t . Это отнюдь не значит, что фактическое число событий, появляющееся в единицу времени, постоянно, – нет, поток неизбежно (если только он нерегулярный) имеет какие-то случайные сгущения и разрежения. Важно, что для стационарного потока эти сгущения и разрежения не носят закономерного характера на один участок длины 1 может попасть больше, на другой – меньше событий, но среднее число событий, приходящееся на единицу времени, постоянно и от времени не зависит. 0 x 1 x 7 2. Поток событий называется потоком без последействия, если для любых двух не- пересекающихся участков времени 1 τ и 2 τ число событий, попадающих на один из них, не зависит от числа событий попавших на другой. По сути, это означает, что события, образующие поток, появляются в те или иные моменты времени независимо друг от друга, вызванные каждое своими собственными причинами. Например, поток пассажиров, входящих в метро, практически не имеет последействия. А вот поток покупателей, отходящих с покупками от прилавка, уже имеет последействие (хотя бы потому, что интервал времени между отдельными покупателями не может быть меньше, чем минимальное время обслуживания каждого из них. 3. Поток событий называется ординарным, если вероятность попадания на малый элементарный) участок времени t Δ двух и более событий пренебрежимо мала по сравнению с вероятностью попадания одного события. Другими словами, поток событий ординарен, если события появляются в нем поодиночке, а не группами. Например, поток поездов, подходящих к станции, ординарен, а поток вагонов – неординарен. Поток событий называется простейшим (или стационарным пуассоновским, если он одновременно стационарен, ординарен и не имеет последействия. Название простейший объясняется тем, что СМО с простейшими потоками имеет наиболее простое математическое описание. Между прочим, самый простой, на первый взгляд, регулярный поток не является простейшим, так как обладает последействием моменты появления событий в таком потоке связаны жесткой, функциональной зависимостью. Без специальных усилий по поддержанию его регулярности такой поток обычно не создается. Простейший поток в качестве предельного возникает в теории случайных процессов столь же естественно, как в теории вероятностей нормальное распределение получается в качестве предельного для суммы случайных величин при наложении (суперпозиции) достаточного большого числа n независимых, стационарных и ординарных потоков (сравнимых между собой по интенсивностям i λ ) ,..., 2 , 1 ( n i = ) получается поток, близкий к простейшему с интенсивностью λ , равной сумме интенсивностей входящих потоков, те. Название пуассоновский связано стем, что при соблюдении 1 – 3 число событий, попадающих на любой фиксированный интервал времени, будет распределено по закону Пуассона. Покажем это с помощью элементарных рассуждений. Рассмотрим на оси времени Ot простейший поток событий как неограниченную последовательность случайных точек (рис. 4). Рисунок 4. Пусть случайная величина X выражает число событий (точек, попадающих на произвольный промежуток времени τ . Покажем, что случайная величина X распределена по закону Пуассона □ Разобьем мысленно временной промежуток τ на n равных элементарных отрезков n t τ = Δ . Математическое ожидание числа событий, попадающих на элементарный отрезок t Δ , очевидно, равно t Δ ⋅ λ , где λ – интенсивность потока (т.к. на единицу длины попадает в среднем λ точек. Согласно свойству ординарности потока можно пренебречь вероятностью попадания на элементарный (те. малый) отрезок двух и более событий. Поэтому математическое ожидание t Δ ⋅ λ числа точек, попадающих на участок t Δ , будет приближенно с точностью до бесконечно малых высшего порядка при 0 → Δ t ) равно вероятности попадания на него одной точки (или, что в наших условиях равнозначно, хотя бы одной. Будем считать элементарный отрезок t Δ занятым, если в нем появилось событие потока, и свободным, если не появилось. Вероятность того, что отрезок n t τ = Δ окажется занятым, равна n t λτ λ = Δ ; вероятность того, что он окажется пустым, равна n λτ − 1 (чем меньше t Δ , тем точнее равенства. Число занятых элементарных отрезков, те. число X событий на всем временном промежутке τ , можно рассматривать как случайную величину, имеющую биномиальный закон распределения (с параметрами n и n p λτ = ), а, следовательно, по формуле Бернулли m n m m n n n C m X P − ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ Необходимое для возникновения биномиального закона условие независимости испытаний, в данном случае – независимость n элементарных отрезков относительно события отрезок занят, обеспечивается свойством отсутствия последействия потока. Известно, что при неограниченном увеличении числа элементарных отрезков t Δ , те. при ∞ → n , 0 → = n p λτ и постоянном значении произведения λτ λτ = = n n np биномиальное распределение стремится к распределению Пуассона с параметром λτ = a : λτ λτ τ − = e m P m m ! ) ( ) ( . (1) От этого свойства закона Пуассона – выражать биномиальное распределение при большом числе опытов и малой вероятности события – происходит его название, часто применяемое в учебниках статистики закон редких явлений. В частности, вероятность того, что за время τ не произойдет ни одного события ( 0 = m ), равна λτ τ − = e P ) ( 0 . ■ (2) Пример. На автоматическую телефонную станцию поступает простейший поток вызовов с интенсивностью 2 , 1 = λ вызовов в минуту. Найти вероятность того, что за две минуты а) не придет ни одного вызова б) придет ровно один вызов в) придет хотя бы один вызов. Решение. а) Случайная величина X – число вызовов за две минуты – распределена по закону Пуассона с параметром 4 , 2 2 2 , 1 = ⋅ = λτ . Вероятность того, что вызовов не будет ( 0 = m ), по формуле (2): 091 , 0 ) 2 ( 4 , 2 б) Вероятность одного вызова ( 1 = m ) по формуле (1): 218 , 0 091 , 0 в) Вероятность хотя бы одного вызова 909 , 0 091 , 0 Найдем распределение интервала времени T между двумя произвольными соседними событиями простейшего потока. В соответствии с формулой (2) вероятность того, что на участке времени длиной t не появится ни одного из последующих событий, равна 9 t e t T P λ − = ≥ ) ( , а вероятность противоположного события, те. функция распределения случайной величины T , есть t e t T P t F λ − − = < = 1 ) ( ) ( . (3) Функция распределения (3) определяет показательный (экспоненциальный) закон распределения. Таким образом, интервал времени между двумя произвольными соседними событиями простейшего потока имеет показательное распределение, для которого математическое ожидание равно среднему квадратичному отклонению случайной величины λ σ 1 = = a , и обратно по величине интенсивности потока Для простейшего потока с интенсивностью λ вероятность попадания на элементарный (малый отрезок времени t Δ хотя бы одного события потока равна согласно (3): t e t T P P t t Δ ≈ − = Δ < = Δ − Δ λ λ 1 ) ( . (4) Эта приближенная формула, получаемая заменой функции t e Δ − λ лишь двумя первыми членами ее разложения вряд по степеням t Δ , тем точнее, чем меньше Понятие марковского случайного процесса Математический анализ работы СМО существенно упрощается, если процесс этой работы марковский. Случайный процесс, протекающий в системе S , называется марковским или процессом без последействия, если он обладает следующим свойством для каждого момента времени 0 t вероятность любого состояния системы в будущем (при 0 t t > ) зависит только от ее состояния в настоящем (при 0 t t = ) и не зависит оттого, когда и каким образом система перешла в это состояние, те. не зависит от ее поведения в прошлом (при 0 t t < ). Ранее мы уже упоминали об аналогичном свойстве некоторых потоков событий (отсутствии последействия. Не надо понимать марковское свойство случайного процесса как полную независимость будущего от прошлого нет, в общем случае будущее зависит от настоящего, те. вероятности ) ( t p i при 0 t t > зависят оттого, в каком состоянии i s находится система в настоящем (при 0 t t = ); само же это настоящее зависит от прошлого, оттого, как вела себя система S при 0 t t < . Это можно сформулировать следующим образом для марковского случайного процесса будущее зависит от прошлого только через настоящее (рис. 5). При фиксированном настоящем условные вероятности всех состояний системы в будущем не зависят от предыстории процесса, те. оттого, когда и как система к моменту 0 t пришла в состояние Рисунок 5. |