Факультет: вычислительной техники и информатики
Специальность: Экономическая кибернетика
Актуальость работы ...
Во многих областях практической деятельности человека мы сталкиваемся с необходимостью пребывания в состоянии ожидания. Подобные ситуации возникают в очередях в билетных кассах, в крупных аэропортах, при ожидании обслуживающим персоналом самолетов разрешения на взлет или посадку, на телефонных станциях в ожидании освобождения линии абонента, в ремонтных цехах в ожидании ремонта станков и оборудования, на складах снабженческо-сбытовых организаций в ожидании разгрузки или погрузки транспортных средств. Во всех перечисленных случаях имеем дело с массовостью и обслуживанием. Изучением таких ситуаций занимается теория массового обслуживания. Случайный характер потока заявок, а в общем случае и длительности обслуживания приводит к тому, что в системе массового обслуживания будет происходить какой-то случайный процесс. Чтобы дать рекомендации по рациональной организации этого процесса и предъявить разумные требования к СМО, необходимо изучить случайный процесс, протекающий в системе, описать его математически. Этим и занимается теория массового обслуживания. Конечно, объем данной работы не позволяет детально изучить эту теорию, но основные, базовые ее элементы были представлены. На их основе возможно дальнейшее рассмотрение этой довольно актуальной в современном мире темы.
Практическая ценность результатов работы
Во многих областях практической деятельности человека мы сталкиваемся с необходимостью пребывания в состоянии ожидания. Подобные ситуации возникают в очередях в билетных кассах, в крупных аэропортах, при ожидании обслуживающим персоналом самолетов разрешения на взлет или посадку, на телефонных станциях в ожидании освобождения линии абонента, в ремонтных цехах в ожидании ремонта станков и оборудования, на складах снабженческо-сбытовых организаций в ожидании разгрузки или погрузки транспортных средств. Во всех перечисленных случаях имеем дело с массовостью и обслуживанием. Изучением таких ситуаций занимается теория массового обслуживания. Случайный характер потока заявок, а в общем случае и длительности обслуживания приводит к тому, что в системе массового обслуживания будет происходить какой-то случайный процесс. Чтобы дать рекомендации по рациональной организации этого процесса и предъявить разумные требования к СМО, необходимо изучить случайный процесс, протекающий в системе, описать его математически. Этим и занимается теория массового обслуживания. Конечно, объем данной работы не позволяет детально изучить эту теорию, но основные, базовые ее элементы были представлены. На их основе возможно дальнейшее рассмотрение этой довольно актуальной в современном мире темы.Научная значимость работы ...
По теории массового обслуживания имеется несколько специальных монографий, отдельнве разделы теории изложены в ряде монографий и учебников по теории вероятностей и теории случайных процессов, но отдельные монографии сложны для первоначального изучения теории,а отдельные разделы не дают общего представления о теории в целом. Данная же работа дает базовые знания о теории массового обслуживания, в частности посвящена ее рассмотрению с точки зрения марковской теории.
Теория массового обслуживания как раздел теории вероятностей возникла сравнительно недавно. Первые работы появились в начале прошлого столетия и были вызваны потребностями практики,в частности широким развитием телефонных сетей. Поэтому и сейчас в работах по СМО широко используется терминология, заимствованная из телефонии: требования, вызовы, заявки, каналы связи,длительность обслуживания и т.п. Несколько позже было обращено внимание, что общие математические модели, исследуемые как модели телефонии, могут описывать и другие жизненные явления. В настоящее время методы и результаты теории массового обслуживания с успехом используются при решении проблем теории надежности, анализе процессов функционирования сложныхсистем, разработке автоматизированных систем управления различных видов и во многих других технических, экономических и социальных областях. Математическую теорию массового обслуживания можно охарактеризовать двумя способами: указанием области практических задач, к решению которых она применяется, и указанием класса изучаемых ею случайных процессов.Практические задачи теории массового обслуживания связаны с исследованием любых операций, состоящих из многих однородных элементарных операций, на осуществление которых влияют случайные факторы. Примером может служить магазин продовольственных товаров.
При исследовании операций очень часто приходится сталкиваться с анализом работы своеобразных систем, называемых системами массового обслуживания (СМО). Примерами таких систем могут служить: телефонные станции, ремонтные мастерские, билетные кассы, справочные бюро, магазины, парикмахерские и т. п.
Каждая СМО состоит из какого-то числа обслуживающих единиц, которые мы будем называть каналами обслуживания. В качестве «каналов» могут фигурировать: линии связи, рабочие точки, приборы, железнодорожные пути, лифты, автомашины и т. д.
Системы массового обслуживания могут быть одноканальными или многоканальными.
Каждая СМО предназначена для обслуживания (выполнения) какого-то потока заявок (или «требований»), поступающих на СМО в какие-то, вообще говоря, случайные моменты времени. Обслуживание поступившей заявки продолжается некоторое (вообще говоря, случайное) время, после чего канал освобождается и готов к принятию следующей заявки. Случайный характер потока заявок приводит к тому, что в какие-то промежутки времени на входе СМО скапливается излишне большое число заявок (они либо образуют очередь, либо покидают СМО необслуженными); в другие же периоды СМО будет работать с недогрузкой или вообще простаивать.
Каждая система массового обслуживания, в зависимости от числа каналов и их производительности, а также от характера потока заявок, обладает какой-то пропускной способностью, позволяющей ей более или менее успешно справляться с потоком заявок. Предмет теории массового обслуживания — установление зависимости между характером потока заявок, числом каналов, их производи-тельностью, правилами работы СМО и успешностью (эффективностью) обслуживания.
В качестве характеристик эффективности обслуживания, в зависимости от условий задачи и целей исследования, могут применяться различные величины и функции, например:
Случайный характер потока заявок, а в общем случае и длительности обслуживания приводит к тому, что в системе массового обслуживания будет происходить какой-то случайный процесс. Чтобы дать рекомендации по рациональной организации этого процесса и предъявить разумные требования к СМО, необходимо изучить случайный процесс, протекающий в системе, описать его математически. Этим и занимается теория массового обслуживания.
Заметим, что за последние годы область применения математических методов теории массового обслуживания непрерывно расширяется и все больше выходит за пределы задач, связанных с «обслуживающими организациями» в буквальном смысле слова. Как своеобразные системы массового обслуживания могут рассматриваться: электронные цифровые вычислительные машины; системы сбора и обработки информации; автоматизированные производственные цехи, поточные линии; транспортные системы; системы противовоздушной обороны и т. п.
Близкими к задачам теории массового обслуживания являются многие задачи, возникающие при анализе надежности технических устройств.
1. СВЯЗЬ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ И МАРКОВСКОЙ ТЕОРИИ
Математический анализ работы СМО очень облегчается, если случайный процесс, протекающий в системе, является марковским. Тогда удается сравнительно просто описать работу СМО с помощью аппарата обыкновенных дифференциальных {в предельном случае — линейных алгебраических) уравнений и выразить в явном виде основные характеристики эффективности обслуживания через параметры СМО и потока заявок.
Мы знаем, что для того, чтобы процесс, протекающий в системе, был марковским, нужно, чтобы все потоки событий, переводящие систему из состояния в состояние, были пуассоновскими (потоками без последействия). Для СМО потоки событий — это потоки заявок, потоки «обслуживании» заявок и т. д. Если эти потоки не являются пуассоновскими, математическое описание процессов, происходящих в СМО, становится несравненно более сложным и требует более громоздкого аппарата, доведение которого до явных, аналитических формул удается только в редких, простейших случаях. Однако, все же аппарат «марковской» теории массового обслуживания может пригодиться и в том случае, когда процесс, протекающий в СМО, отличен от марковского — с его помощью характеристики эффективности СМО могут быть оценены приближенно. Следует заметить, что чем сложнее СМО, чем больше в ней каналов обслуживания, тем точнее оказываются приближенные формулы, полученные с помощью марковской теории. Следует также заметить, что в ряде случаев для принятия обоснованных решений по управлению работой СМО вовсе и не требуется точного знания всех ее характеристик — зачастую достаточно и приближенного, ориентировочного.[1]
В данной работе будут изложены элементы теории массового обслуживания, главным образом в той простейшей форме, которую они приобретают в рамках марковской теории.
2.КЛАССИФИКАЦИЯ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ И ИХ ОСНОВНЫЕ ХАРАКТЕРИСТИКИ
2.1 Классификация СМО
Системы массового обслуживания вообще могут быть двух типов.
Системы с отказами. В таких системах заявка, поступившая в момент, когда все каналы заняты, получает «отказ», покидает СМО и в дальнейшем процессе обслуживания не участвует.
Системы с ожиданием (с очередью). В таких системах заявка, поступившая в момент, когда все каналы заняты, становится в очередь и ожидает, пока не освободится один из каналов. Как только освободится канал, принимается к обслуживанию одна из заявок, стоящих в очереди.
Обслуживание в системе с ожиданием может быть «упорядоченным» (заявки обслуживаются в порядке поступления) и «неупорядоченным» (заявки обслуживаются в случайном порядке). Кроме того, в некоторых СМО применяется так называемое «обслуживание с приоритетом», когда некоторые заявки обслуживаются в первую очередь, предпочтительно перед другими.Системы с-очередью делятся на системы с неограниченным ожиданием и системы с ограниченным ожиданием.
В системах с неограниченным ожиданием каждая заявка, поступившая в момент, когда нет свободных каналов, становится в очередь и «терпеливо» ждет освобождения канала, который примет ее к обслуживанию. Любая заявка, поступившая в СМО, рано или поздно будет обслужена.
В системах с ограниченным ожиданием на пребывание заявки в очереди накладываются те или другие ограничения. Эти ограничения могут касаться длины очереди (числа заявок, одновременно находящихся в очереди), времени пребывания заявки в очереди (после какого-то срока пребывания в очереди заявка покидает очередь и уходит), общего времени пребывания заявки в СМО и т. д.
В зависимости от типа СМО, при оценке ее эффективности могут применяться те или другие величины (показатели эффективности)-Например, для СМО с отказами одной из важнейших характеристик ее продуктивности является так называемая абсолютная пропускная способность — среднее число заявок, которое может обслужить система за единицу времени.
Наряду с абсолютной, часто рассматривается относительная пропускная способность СМО — средняя доля поступивших заявок, обслуживаемая системой (отношение среднего числа заявок, обслуживаемых системой в единицу времени, к среднему числу поступающих за это время заявок).
Помимо абсолютной и относительной пропускной способностей, при анализе СМО с отказами нас могут, в зависимости от задачи исследования, интересовать и другие характеристики, например:
2.2. СМО с ожиданием.
Очевидно, для СМО с неограниченным ожиданием как абсолютная, так и относительная пропускная способность теряют смысл, так как каждая поступившая заявка рано или поздно будет обслужена. Зато для такой СМО весьма важными характеристиками являются:
Для СМО с ограниченным ожиданием интерес представляют обе группы характеристик: как абсолютная и относительная пропускная способности, так и характеристики ожидания. Для анализа процесса, протекающего в СМО, существенно знать основные параметры системы: число каналов п, интенсивность потока заявок X, производительность каждого канала (среднее число заявок \it обслуживаемое каналом в единицу времени), условия образования очереди (ограничения, если они есть). В зависимости от этих параметров мы и будем в дальнейшем выражать характеристики эффективности работы СМО. Будем считать все потоки событий, переводящие СМО из состояния в состояние, пуассоновскими.[3]
Напомним, что в случае, когда пуассоновский поток стационарен (простейший поток), интервал времени Т между событиями в этом потоке есть случайная величина, распределенная по показательному закону:
В случае, когда из какого-то состояния St систему выводят сразу несколько простейших потоков, величина Т — время пребывания системы (подряд) в данном состоянии есть случайная величина, распределенная по закону (2.1).
Для описания функционирования магазина продовольственных товаров наиболее подходит СМО с ограниченным временем ожидания.
Рассмотрим СМО подобного типа, оставясь в рамках марковской схемы. Предположим, что имеется –канальная СМО с ожиданием, в которой число мест в очереди не ограничено, но время пребывания заявки в очереди ограничено некоторым случайным сроком Точ со средним значением Точ . Таким образом на каждую заявку действует как бы «поток уходов» с интенсивностью
Если этот поток пуассоновский, то процесс, протекающий в СМО, будет марковским. Найдем для него вероятности состояний.[2] Будем снова нумеровать состояния системы по числу заявок, связанных с системой – как обслуживаемых, так и стоящих в очереди
Граф состояний системы показан на рис. 2.1.
Разметим этот граф, т. е. проставим у стрелок соответствующие интенсивности. Снова, как и раньше, у всех стрелок, ведущих слева направо, будет стоять интенсивность потока заявок ?. Для состояний без очереди у стрелок, ведущих из них справа налево, будет, как и раньше, стоять суммарная интенсивность потока обслуживании всех занятых каналов. Что касается состояний с очередью, то у стрелок, ведущих из них справа налево будет стоять суммарная интенсивность потока обслуживании всех п каналов nµ плюс соответствующая интенсивность потока уходов из очереди. Если в очереди стоят r заявок, то суммарная интенсивность потока уходов будет равна rv.
Как видно из графа, перед нами опять схема гибели и размножения: применяя общие выражения для предельных вероятностей состояний в этой схеме, напишем:
Отметим некоторые особенности рассмотренной СМО с «нетерпеливыми» заявками по сравнению с ранее рассмотренной СМО с «терпеливыми» заявками.
Если длина очереди не ограничена заранее никаким числом и заявки «терпеливы» (не уходят из очереди), то стационарный предельный режим существует только в случае "р
Для СМО с «нетерпеливыми» заявками понятие «вероятность отказа» не имеет смысла — каждая заявка становится в очередь, но может и не дождаться обслуживания, уйдя раньше времени.
[2]Относительную пропускную способность q такой СМО можно подсчитать следующим образом. Очевидно, обслужены будут все заявки, кроме тех, которые уйдут из очереди досрочно. Подсчитаем, какое в среднем число заявок покидает очередь досрочно. Для этого вычислим среднее число заявок в очереди:
r = 1* pn+1 + 2*pn+2+…+r*pn+r+… .
На каждую из этих заявок действует «поток уходов» с интенсив ностью v. Значит, из среднего числа r заявок в очереди в среднем будет уходить, не дождавшись обслуживания, vr заявок в единицу времени; всего в единицу времени в среднем будет обслужено
заявок. Относительная пропускная способность СМО будет
Среднее число занятых каналов z по-прежнему получим, деля абсолютную пропускную способность на µ:
Это позволяет вычислить среднее число заявок в очереди г, не суммируя бесконечного ряда (2.2). Действительно, из (2.5) получим:
а входящее в эту формулу среднее число занятых каналов можно найти как математическое ожидание случайной величины Z, принимающей значения 0,1, 2, ..., п с вероятностями p0, p1, p2,…,[1-(p0 +p1 +…+pn-1)]:
Z= 0*p0+ 1*p1+2*p2+…+ n*[1-(p0 +p1 +…+pn-1)]=p1+2*p2+…+ n*[1-(p0 +p1 +…+pn-1)] (2.7)
Заметим, что в формуле (7.1) фигурирует сумма бесконечного ряда, не являющегося прогрессией. Однако эта сумма вычисляется приближенно, причем достаточно легко, так как члены ряда быстро убывают с увеличением их номера. В качестве приближенного значения для бесконечной суммы берется сумма конечного числа г — 1 членов, а остаток оценивается следующим образом:
Во многих областях практической деятельности человека мы сталкиваемся с необходимостью пребывания в состоянии ожидания. Подобные ситуации возникают в очередях в билетных кассах, в крупных аэропортах, при ожидании обслуживающим персоналом самолетов разрешения на взлет или посадку, на телефонных станциях в ожидании освобождения линии абонента, в ремонтных цехах в ожидании ремонта станков и оборудования, на складах снабженческо-сбытовых организаций в ожидании разгрузки или погрузки транспортных средств. Во всех перечисленных случаях имеем дело с массовостью и обслуживанием. Изучением таких ситуаций занимается теория массового обслуживания.
Случайный характер потока заявок, а в общем случае и длительности обслуживания приводит к тому, что в системе массового обслуживания будет происходить какой-то случайный процесс.[3] Чтобы дать рекомендации по рациональной организации этого процесса и предъявить разумные требования к СМО, необходимо изучить случайный процесс, протекающий в системе, описать его математически. Этим и занимается теория массового обслуживания.