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

Введение
Во многих областях человеческой практики мы сталкиваемся с необходимостью оставаться в состоянии ожидания. Такие ситуации возникают в очередях в билетных кассах, в крупных аэропортах, когда обслуживающий персонал воздушных судов ждет разрешения на взлет или посадку, на телефонных станциях в ожидании выхода абонентской линии, в мастерских в ожидании ремонта машин и оборудования, на складах снабженческих и сбытовых организаций в ожидании разгрузки или погрузки транспортных средств. Во всех этих случаях речь идет о массовом обслуживании. Теория массового обслуживания изучает такие ситуации.
В этой работе мы рассмотрим историю систем массового обслуживания, обозначим основные определения и характеристики этой темы, а также рассмотрим на конкретном примере применение системы массового обслуживания в современном мире.
1.История зарождения и развития теории систем массового обслуживания
Теория массового обслуживания, формально входящая в теорию случайных процессов, уже несколько десятилетий является самостоятельной областью исследований со специфическим курсом проблем. Зарождение и развитие теории можно представить в виде следующей цепочки: теория вероятностей → теория случайных процессов → ТМО [2].
Теория вероятностей (как исторический предок) теории массового обслуживания родилась и начала формироваться в XVII веке. из-за необходимости изучать законы случайных явлений. Исторически сложилось так, что схемы, обеспечивающие простые и понятные модели случайных явлений, а также возможность повторения одного и того же опыта применительно к массовому возникновению этих явлений, стали азартными схемами. Слово "азарт" (от французского" le hazard") означает “случайность". До сих пор примеры из области азартных игр используются при изучении теории вероятностей как упрощенные модели случайных явлений, которые большинство людей просто и наглядно иллюстрируют основные законы теории. В середине 17-го года. столетие назад математические исследования в области азартных игр проводились такими учеными, как Ферма (1601-1665), Паскаль (1623-1662) и др. Именно трудам этих ученых современная математика обязана появлением таких категорий, как "вероятность" и "математическое ожидание". Однако вплоть до следующего столетия формирующаяся наука не приближалась к классическим определениям теории.
Значительный шаг в развитии теории вероятностей сделал Якоб Бернулли (1654-1705 гг.). Он страдал и оказался законом больших чисел (простейшая форма закона больших чисел устанавливает связь между вероятностью того или иного события и частотой его наступления, т. е. при большом количестве экспериментов относительная частота наступления того или иного исхода стабилизируется и приближается к некоторому числу, вероятность которого равна этому исходу). Позже Пуассон (1781 – 1840) оказался более общей формой больших чисел, чем Бернулли, а также впервые применил теорию вероятностей для решения задач стрельбы (и таким образом начал ее использовать в военном деле). Пуассон также вывел один из законов распределения, который играет важную роль во всех приложениях расчета вероятностей, включая теорию очередей.
В XIX веке, при заметном снижении интереса к теории вероятностей в Западной Европе, в России была создана знаменитая Санкт-Петербургская математическая школа, давшая миру важнейшие работы по теории вероятностей и разработке ряда ее программ (в том числе теории случайных процессов), большинство из которых сегодня имеют собственные направления исследований. Основу современной теории случайных процессов (которая является прародителем теории массового обслуживания) заложил А. А. Марков (1856-1922). Он значительно расширил область применения центральной краевой теоремы и закона больших чисел, расширив их как на зависимые, так и на независимые эксперименты.
Из теории случайных процессов, как уже упоминалось ранее, постепенно возникла теория массового обслуживания. Ее родоначальником считают датского ученого А. К. Эрланга.
Агнер Краруп Эрланг родился в Дании в 1878 г. В возрасте 14 лет он с отличием сдал предварительные экзамены в Копенгагенский университет. Из-за молодого возраста ему было отказано в обучении, поэтому следующие два года он работал в деревенской̆ школе, после чего добился зачисления в университет. После успешного окончания университета А. Эрланг несколько лет преподавал в школах астрономию, химию, физику (его любимым предметом с детства была астрономия). В 1908 г. А. К. Эрланг стал научным сотрудником в лаборатории Копенгагенской Телефонной компании, а позднее возглавил её. В телефонной компании Эрланг проработал двадцать лет (вплоть до смерти). Он не был женат, редко брал отпуск, все свое время посвящая работе. Его первая научная работа была издана в 1909 г. Наиболее известным научным трудом Агнера К. Эрланга считается «Решение некоторых проблем в теории вероятностей значений в автоматических телефонных станциях» именно в нем была выведена формула Эрланга, которая широко используется в теории вероятностей и других областях прикладной математики.
В настоящее время мировая наука позиционирует А. К. Эрланга как математика и инженера, основателя таких научных направлений, как теория телетрафика, теория массового обслуживания. Термин «эрланг» во всем мире используется как стандартная единица телефонного движения. Именем Эрланга названы одно из распределений вероятностей в теории вероятностей и язык программирования «Erlang» для крупномасштабных промышленных систем он-лайн, который создала одна из крупнейших компаний современности «Ericsson».
А. К. Эрланг, решая практические задачи совершенствования работы систем связи, вывел ряд формулировок и формул, являющихся базовыми в теории массового обслуживания. Развили теорию массового обслуживания уже советские учёные.
В 30-е гг. XX в. А. Я. Хинчин разработал метод «вложенных цепей Маркова», давший возможность поиска распределения времени ожидания для простейших потоков на один канал, обслуживающий очередь с произвольным распределением времени обслуживания. В 50-е гг. XX в. Б. В. Гнеденко обобщил формулы Эрланга, а также рассмотрел случаи потери заявок при отказе канала обслуживания и переход заявки на другой свободный канал. Б. В. Гнеденко является автором первого специального курса по теории массового обслуживания в СССР, и написанная им монография до сих пор занимает центральное место в изучении теории массового обслуживания как в России, так и за рубежом. Математическая теория массового обслуживания возникла для описания работы систем, предназначенных для обслуживания массового потока требований случайного характера (случайными могут быть как моменты прихода требований, так и затраты времени на их обслуживание). Задачи массового обслуживания, сформулированные математически, обычно сводятся к изучению случайных процессов. Становление теории массового обслуживания было вызвано интересом к математическим задачам, возникающим в организации телефонных сетей (датский инженер А. Эрланг, начало 20 века). Дальнейшее развитие теория массового обслуживания получила в 1940–1950 годах в трудах К. Пальма, Ф. Поллачека, А.Я. Хинчина, которому принадлежит и сам термин «теория массового обслуживания». В конце 1960-х годов были введены так называемые скрытые марковские модели [8], описывающие двойной стохастический процесс (Л. Баум). В этом случае каждое состояние системы, скрытое от наблюдателя, может ещё и проявлять себя по-разному, что также описывается в терминах теории вероятностей. С 1970-х гг. в М. о. т. разрабатываются методы анализа и оптимизации процессов обслуживания с использованием ЭВМ.
Пик своего развития теория массового обслуживания достигла в 50–70 годы прошлого века. В это время появилось большое количество монографий и статей по различным проблемам этой тематики. Наиболее завершенный вид теория массового обслуживания получила в случае простейшего потока заявок, поступающих в систему, и экспоненциально распределенного времени их обслуживания. Затем интерес к теории обслуживания несколько ослабел. Это объяснялось, в частности, тем, что задачи, допускающие простые решения, особенно в вычислительном плане, уже были решены. Однако в последнее время снова возродился интерес к теории массового обслуживания, обусловленный не только новыми проблемами, возникающими на практике, но и новыми математическими подходами к их решению. Так использование аппарата полумарковских процессов с общим фазовым пространством состояний позволило определить стационарные характеристики однолинейной и двухканальной систем обслуживания в случае рекуррентного входящего потока заявок и произвольно распределенного времени обслуживания заявок.
2.Предмет, методы и задачи теории массового обслуживания
Множество производств, бытового обслуживания, экономические и финансовых сферах главную роль играют системы теории массового обслуживания, которые реализуют многократное выполнение задач одного типа. При рассмотрении примеров необходимости систем массового обслуживания можно выделить наиболее явные. Так, в системе финансово-экономической направленности можно взять на рассмотрение пример банковского обслуживания или обслуживания страховой компании. Каждая система массового обслуживания содержит в себе каналы обслуживания, которые наиболее часто выступают в качестве единиц, линий и приборов. Также, каждая система имеет свое предназначение в качестве средства обслуживания потока требований или заявок, которые поступают в большем количестве, чем могут быть решены. Время на исполнения заявок не имеет определения и носит исключительно случайный характер. Поэтому некоторые вопросы скапливаются в виду своей нерешенности, при этом процесс приема заявок не останавливается. Каждая система имеет пропускную способность, которая обусловлена характером потоков и эффективности их решения.
Теория массового обслуживания анализирует процессы в системах обслуживания, производства и управления как однородные действия (события), многократно повторяющиеся (торговые предприятия, банки, автоматические производственные линии, медицинские учреждения, страховые организации, транспортные системы и др.) [7].
Предметом теории массового обслуживания является установление взаимосвязи между основными характеристиками сервисной системы (количеством каналов обслуживания, характером входного потока запросов, которые необходимо обслуживать, результатом работы одного канала и др.) для улучшения управления системой.
Основные задачи теории очередей заключаются в следующем:
1) Построить математическую модель сигнальной системы и рассчитать ее основные характеристики.
Рассматривается математическая модель системы математических отношений, которые являются приближенными (в абстрактном виде) к исследуемой системе. При создании математической модели отбрасываются факторы, незначимые с точки зрения исследователя, влияющие на функционирование системы.
Экономико-математическая модель — это задача, которая предназначена для изучения экономической проблемы.
Построение и расчет математической модели, позволяющей проанализировать ситуацию и выбрать оптимальное решение для управления системой.
Использование математических моделей позволяет сделать предварительный выбор оптимального решения на основе определенных критериев, предложенных поставщиком задачи или менеджером компании.
2) Установить зависимость эффективности системы очередей от ее организации.
3) Решать различные оптимизационные задачи, связанные с функционированием системы массового обслуживания.
4) Выработать рекомендаций по рациональному построению системы массового обслуживания для обеспечения высокой эффективности ее функционирования

.
Все задачи теории массового обслуживания носят оптимизационный характер и в конечном итоге направлены на определение такого варианта функционирования системы, который обеспечит минимум общих затрат от простоя сервисного телевидения, потери времени и ресурсов на техническое обслуживание и так далее.
Методология теории массового обслуживания включает в себя все наиболее важные элементы теории случайных процессов: марковские случайные процессы, потоки запросов, граф состояний, системы обыкновенных дифференциальных уравнений для вероятностей состояний и др.
Фактическая цель теории массового обслуживания представляет собой рекомендации по рациональному расставлению и составлению систем массового обслуживания. Обслуживание необходимо модернизировать до того состояния, в котором оно сможет удовлетворить наибольшее количество поступающих заявок, в лучшем случае удовлетворяет все заявки. Для того чтобы выполнить эту цель составляются задачи теории массового обслуживания. Они состоят из установления зависимостей успешного функционирования систем, характера и количества поступающихся заявок, количественного показателя числа каналов, их производительности и общих правил работы системы.
Показателями эффективности системы массового обслуживания выступают следующие параметры [5]: пропускная способность абсолютная и относительная, средняя продолжительность периода занятости, коэффициент использования системы. Представленные параметры характеризуют эффективность использования систем массового обслуживания. Показатели обслуживания заявок: среднее время пребывания в очереди и пребывания заявки в системе, вероятность отказа в рассмотрении заявки без ожидания, вероятность рассмотрения заявки без ожидания. А также, показатели законов распределения времени на ожидание и пребывание в очереди, и среднее число заявок в очереди и очереди в системе
Существует характерное случайное действие поступающих заявок и длительности по их обслуживанию, это является процессом СМО, который характеризуется как случайный процесс. В данном случае случайный процесс принято называть процессом соответствия. При нем происходит значение аргумента как промежуточный момент в процессе проводимого опыта. При этом происходит введением случайной величины, в нашем случае этой величиной выступает показатель состояния СМО. Что говорит о необходимости изучения случайных величин, при решении задач массового обслуживания. Этот процесс необходимо не только изучать, но и проводить соответствующий анализ и построить математическую модель на основании полученных данных. Математическая модель и ее дальнейший анализ позволяет упростить алгоритмы работы СМО, что представляется случайным процессом, который направлен на удовлетворение определенных условий. Ниже проведем рассмотрение условий ниже.
Сложность построения и разработки ТКС является существенным недостатком, что обусловлено необходимостью выявления достоверной информации для реализации и разработки путей решения необходимой задачи. При составлении делается расчет на создание и использование поэтому здесь необходима простота алгоритма выполнения и слаженность процесса. Модели математического характера выстраиваются на основании СМО, которое является обслуживающей требования. Данные, полученные от СМО, представляются в виде случайных интервалов временного характера продолжительностью выполнения операций СМО. При рассмотрении СМО наиболее детально можно выделить систематизацию разделения информационного потока, который принято называть системой распределения информации (СРИ). СРИ характеризуются наличием распределительной сети, подобно транспортным системам или системам энергоснабжения. Принцип передачи информации происходит посредством перераспределения потока с использованием распределительной сети. Она является и телекоммуникационной, при этом в ее составе имеются каналы передачи информации и узлы коммутации. Совокупная работа данных средств осуществляет процесс передачи информации з источников к получателю (потребителю). Также, данные каналы осуществляют передачу информации первостепенной важности, которая является средством передачи информации и распределения. Узловое соединение коммутационных передач осуществляет обеспечение соединительных каналов с передачей информации. При этом действие происходит посредством использования алгоритмов распределения. При этом обслуживание сообщения отождествляется с требованием на его передачу или обработку и примерами их могут быть вызовы телефонной станции или пакеты пакетного коммутатора.
В качестве СРИ может рассматриваться не только сеть связи в целом, но и пучок каналов или линий, отдельный коммутатор или весь коммутационный узел. Количественная сторона процессов обслуживания потоков требований (трафика) в СРИ исследуется теорией телетрафика (другое название – теория распределения информации). Предметом теории телетрафика есть установление зависимостей между характером потока требований, количеством каналов обслуживания, производительностью отдельного канала и эффективным обслуживанием с целью определения наилучших путей управления этими процессами.
В качестве СРИ можно рассматривать не полное функционирование взаимосвязей как единое целое, а также, допустимо рассмотрение каналов и линий, отдельных коммуникативных систем и структур, которые создают единый узел коммутации. Обслуживание процесса поступления потока тербований с количественной стороны, рассматривается теорией телетрафика. Предметом данной теории можно обусловить процесс установления зависимости между показателем потока требований и количественным показателем общих каналов обслуживания. При этом предусматривается разработка и анализ производительного процесса, который выступает в качестве показателя индивидуальной эффективности. Данный процесс является необходимым для определения и выявления путей управления различными процессами, которые выявляют непосредственное влияние каждого элемента структуры на общее итоговое значение. Задача теории телетрафика состоит в установлении зависимости результирующих показателей работы СРИ (например, среднего количества требований, которые обслуживаются; среднего количества требований, которые ожидают обслуживания в очереди и т.д.) от входных показателей (количества каналов в системе, параметров входного потока требований и т.д.). Результирующими показателями или исследуемыми характеристиками СРИ являются показатели эффективности, которые описывают, способная ли данная система справиться с потоком требований.
Теория телетрафика имеет свои методы решения оптимизационных вопросов, которые направлена на нахождение варианта построения системы с минимальными денежными затратами, которые будут необходимы для обеспечения обслуживания, покроют временные затраты и часть ресурсных затрат. Теория телетрафика – это набор вероятностных методов анализа, синтеза и оптимизации СРИ, т.е. проектирования новых и эксплуатации действующих сетей связи [1]. Без решения задач анализа, синтеза и на этой основе оптимизации ТКС и сетей невозможно их дальнейшее развитие. Задача анализа – это установление зависимостей и значений величин, которые характеризуют качество обслуживания, от характеристик и параметров входного потока требований, схемы и дисциплины обслуживания. Задача анализа возникает в тех случаях, когда телекоммуникационная сеть или система уже построена и функционирует.
Целью анализа является получение реальных характеристик СРИ, сравнение их с проектными характеристиками, предоставление объективных оценок качества работы системы. Анализ позволяет определить причины снижения качества обслуживания и выдать рекомендации относительно устранения этих причин. Иногда анализ делается после внесения изменений в систему или после подключения новых источников нагрузки (реконструкции). Разработка методов оценки качества функционирования ТКС и сетей является основной целью теории телетрафика. Задача синтеза – это определение структурных параметров сети или, например, схемы коммутационного узла этой сети при заданных потоках, дисциплине и качестве обслуживания. Задача синтеза в определенной мере является обратной к задаче анализа. Синтез (проектирование) телекоммуникационных сетей может состоять из нескольких этапов.
С позиций системной методологии, основными этапами решения задачи синтеза сетей и систем связи есть: анализ проблемы; определение системы; определение целей, критериев, ресурсов; определение альтернативных вариантов; оценка, сравнение и выбор вариантов; реализация решения. Задачи проектирования и планирования ТКС и сетей возникают из необходимости заблаговременного выбора технических средств, которые обеспечивают удовлетворение потребностей в передаче информационных сообщений. Целью проектирования есть оптимальная структура сети на продолжительную перспективу с учетом текущего состояния развития телекоммуникационной техники и технологий. Задачи оптимизации близки к задачам анализа и синтеза. При проектировании ТКС и сетей они формулируются так: определить структурные параметры или алгоритмы функционирования сети (системы), для которых: при заданных потоках, качестве и дисциплине обслуживания стоимость или объем сети (системы) минимальные; при заданных потоках, дисциплине обслуживания и стоимости качественные показатели функционирования сети (системы) оптимальные.
При эксплуатации ТКС и систем задача оптимизации формулируется как задача управления потоками требований или структурой сети для достижения наилучших показателей качества функционирования. Из-за больших вычислительных трудностей задачи оптимизации ТКС и сетей решаются на ЭВМ. Анализ, синтез и оптимизация СРИ выполняются с применением теории вероятностей, математической статистики, комбинаторных и алгебраических методов, теории множеств, теории графов, принципов системного подхода (системотехники) и др. Основными методами решения задач в теории телетрафика являются аналитический, числовой и метод статистического моделирования.
Аналитические методы позволяют решать задачи теории телетрафика при относительно простых структуре системы, характеристиках потока и дисциплинах обслуживания. Рассматриваются все возможные состояния системы, обусловленные, например, положением каждой точки коммутации или количеством занятых каналов. Такие состояния называются микросостояниями системы. Когда поступает новое требование, заканчивается любая из фаз работы управляющего устройства по установлению соединения или заканчивается соединение, система изменяет свое микросостояние. Для каждого микросостояния записывается уравнение статистического равновесия. Решая систему этих уравнений, находят точное решение задачи в границах принятой модели. Числовые методы используют специальные алгоритмы для нахождения приближенных решений итерационными или другими методами. Они применяются для сложных систем, где количество микросостояний настолько велико, что решить систему уравнений статистического равновесия невозможно даже с помощью быстродействующих ЭВМ. Поэтому применяется так называемый макроподход.
В сложной системе с большим количеством микросостояний по некоторому признаку микросостояния объединяются в классы – макросостояния. Путем усреднения определяются интенсивности переходов из одних макросостояний в другие