Под потоком событий понимается последовательность однородных событий, следующих одно за другим в какие-то случайные моменты времени (поток вызовов на телефонной станции, поток покупателей, поток заявок (требований) на ремонт оборудования и т.п.).
Поток характеризуется интенсивностью - л - частотой появления событий или средним числом событий, поступивших в СМО за единицу времени.
Поток событий называется регулярным, если события следуют одно за другим через определенные равные промежутки времени.
Поток событий называется стационарным, если его вероятностные характеристики не зависят от времени.
Поток событий называется потоком без последствий, если для любых двух непересекающихся участков времени τ4 и τ2 - число событий, попадающих на один из них, не зависит от числа событий, попадающих на другие (например, поток пассажиров, входящих в метро, практически не имеет последствий).
Поток событий называется ординарным, если вероятность попадания на малый (элементарный) участок времени ∆t двух или более событий является величиной бесконечно малой по сравнению с вероятностью попадания одного события, т. е. поток требований (событий). Ординарен, если они (события) появляются в нем поодиночке, а не группами.
Поток событий называется простейшим (или стационарным пуассоновским), если он одновременно стационарен, ординарен и не имеет последствий. Название "простейший" объясняется тем, что СМО с простейшими потоками имеет наиболее простое математическое описание.
Математически доказано, что для простейшего потока число т событий (требований), попадающих на произвольный участок времени t распределено по закону Пуассона
для которого математическое ожидание случайной величины равно ее дисперсии:
В частности, вероятность того, что за время т не произойдет ни одного события (m = 0), равна
В соответствии с этой формулой вероятность того, что на участке времени длиной t не появится ни одного из последующих событий, равна
а вероятность противоположного события, т. е. функция распределения случайной величины Т есть
Процессы массового обслуживания исследуются на основе двух методов:
Каждый из этих методов имеет свои особенности и сферу практического применения.
Аналитическая теория массового обслуживания предлагает достаточно простые расчетные формулы для определения важнейших характеристик функционирования СМО различных классов. Эти подходы изложены в .
Однако на практике реальные СМО часто отличаются от упрощенных систем. Обслуживающие аппараты и источники, посылающие требования, заявки могут быть неоднородными. Обслуживание может носить сложный многофазовый характер. Поток событий часто может оказаться не простейшим, а время обслуживания в реальных системах может носить любой характер распределения. Многие самые сложные задачи (особенно возникающие в производственных системах) могут быть успешно решены при помощи метода статистического моделирования случайных процессов (метод Монте-Карло).
Построение математической модели Монте-Карло состоит из следующих этапов:
Для наблюдения заходом производственного процесса используются данные фотографий, хронометража, журналов регистрации простоев оборудования, данные с АИС (автоматизированных информационных систем) и др. методы получения информации. При проведении наблюдений не следует проводить округления до равных значений времени.
При обработке первичной документации важно правильно выбрать интервалы группировок. Если ожидается, что распределение похоже на нормальное, величина интервала рассчитывается по формуле:
Рассмотрим, как происходит поиск этой кривой. Вначале собираются исходные данные, строится гистограмма и определяют закон распределения. Далее строится теоретическая кривая, параметры которой совпадают с параметрами эмпирического распределения. Для этого необходимо найти параметры эмпирического распределения и по ним построить теоретическую кривую. Выдвинуть форму гипотезы, найти параметры и построить кривую и далее проверить, насколько соответствует теоретическая кривая и эмпирическое распределение. Если они полностью совпадают, то, значит, закон найден. Но если между теоретической кривой и эмпирической гистограммой имеются различия, необходимо проверить на сколько существенны эти различия. Если они носят случайный характер, тогда можно считать, что эмпирическое распределение описывается данной теоретической кривой. Если же различия очень велики, значит, теоретический закон подобран в данном случае неверно, и нужно искать новый закон распределения. Для оценки существенности различий теоретической кривой и эмпирического распределения используется два критерия X2 (х-квадрат) Пирсона и λ лямбда Колмогорова. X2 определяется по следующей формуле:
Теоретические частоты находятся на основе, например, интегральной формы распределения путем умножения на объем совокупности.
В результате получаем теоретически накопленные частоты.
Оценка на основе критерия х2 производится следующим образом. После того, как найдено х определяют число степеней свободы К, которое равно числу интервалов минус число статистических характеристик, использованных при расчете распределения (параметров). При нормальном законе - три (x,σ,N) параметра, а при распределении Пуассона - два (λ и N) параметра. Для полученных величин X2 и числа степеней свободы К по таблицам отыскивается вероятность Рх2 того, что различие между теоретическим и эмпирическим распределениями носит случайный характер. Если Рх2 больше 0,05 или 5%, можно считать, что эта вероятность достаточно велика, чтобы не исключать случайного характера различий и поэтому распределение считают подчиняющимся данному теоретическому закону. Если же Рх2 меньше 5 %, то считается, что теоретическое и эмпирическое распределение не совпадают и тогда нужно искать новое теоретическое распределение. Значения Рх2 содержатся в специальных таблицах с двумя входами: один соответствует х2, второй - К. На их пересечении Рх2. Проверка по критерию λ. производится так: вначале определяют
После того, как найдена А, по таблицам находят Р (λ). И, если оно больше 0,05, считают, что различия распределения носят случайный характер, если меньше, то не случайный. Критерий λ по сравнению х2 являются менее жестким, т. е. обычно он показывает большую вероятность того, что различие между распределениями носит случайный характер. Это объясняется тем, что для использования критерия λ нужно дополнительное условие, а именно, теоретический анализ должен показать, что эмпирическое распределение должно подчиняться данному закону.
Рис.6.3.
После того как построена математическая модель производственного процесса, можно переходить к проведению случайных испытаний и моделированию на их основе хода производственного процесса. Случайные испытания производятся обычно на основе равновероятного распределения. Далее необходимо от равновероятного распределения перейти к распределению, которое описывается математической моделью. Наконец, построение графика Эпроизводственного процесса на основе случайных испытаний. Для проведения случайных испытаний используются различные методы. Теоретически наиболее простой, но практически наиболее трудоемкий метод жеребьевки: случайный отбор по схеме повторного отбора (шары из урны), моделирование случайных испытаний с помощью ЭВМ, использование таблиц случайных чисел, составленных на основе одного из первых двух способов. Пользоваться таблицей можно в любом, но заранее оговоренным порядке (или по диагонали, сверху вниз и т.д.).
Имеется несколько переходов от нормально распределенных чисел к случайным числам.
Первый способ связан с закреплением за каждым значением определенного количества номеров, оно пропорционально вероятности каждого времени (например, телефонный разговор).
Этот способ хорош для дискретных значений. Если же значения непрерывные, то используем функцию нормального распределения.
Поскольку вероятность любого значения от 0 до 1, т. е. 0 ≤ F(t) < 1, может быть рассчитано с любой точностью до 2, 3 и т.д. знаков. Найдя по таблице случайных чисел значения случайных чисел, можно приравнять их к величинам F(t)t и известным значениям x и σ значения χ. Эти значения χ и представляют собой случайные величины промежутков между обслуживанием или длительность обслуживания, подчиняющимся закону нормального распределения С параметрами σ и χ. Такой метод очень трудоемкий, и поэтому на практике употребляется графический метод как наиболее удобный.
Установив на основе случайных испытаний возможные длительности времени обслуживания, либо длительности промежутков между поступлением заявок, строят график движения процесса производства во времени. На таком графике проставляют время работы оборудования и время обслуживания, простои и ожидания обслуживания. Суммирование времени простоев дает возможность оценить затем каждый вариант с точки зрения уровня обслуживания основного производственного процесса. Эта оценка представляет третью стадию решения задачи, а именно: оценку и анализ результатов моделирования. В ходе такой оценки строится график экономичности различных вариантов обслуживания. При оценке учитывают, что:
Для определения того, достаточно ли проведено испытаний, используется следующий прием. Общее количество испытаний делится на две части. Для каждой половины подсчитывается средняя арифметическая и дисперсия. Далее они сравниваются друг с другом. Оценка расхождения между средними производится по критерию Стьюдента
Затем сравниваем tрасч с табличным значением. Если tрасч больше табличного, значит, расхождения между средними велики. Это говорит о том, что испытаний в таком случае недостаточно. Испытания продолжают и затем делают снова проверку.
Величина t находится по таблицам Стьюдента в зависимости от вероятности возможной ошибки. Обычно в пределах 5 % и от числа степеней свободы.
Расчет численности вспомогательных рабочих (расчет норм обслуживания): наладчиков, электриков, дежурных слесарей. Расчет необходимого числа кранов. Определение страховых заделов. Определение страховых запасов. Расчет необходимой площади материальных складов.
Марковские случайные процессы
Названы по имени выдающегося русского математика А.А.Маркова, впервые начавшего изучение вероятностной связи случайных величин и создавшего теорию, которую можно назвать "динамикой вероятностей". В настоящее время теория марковских процессов и ее приложения широко применяются в самых различных областях и, в том числе, в исследовании операций и теории принятия оптимальных решений.
Марковский процесс - дискретный или непрерывный случайный процесс X (t ), который можно полностью задать с помощью двух величин:
· вероятности P (x ,t ) того, что случайная величина x (t ) в момент времени t равна x , и
· вероятности P (x 2 , t 2 |x 1 ,t 1) того, что если x при t = t 1 равен x 1 , то при t = t 2 он равен x 2 .
Вторая из этих величин называется вероятностью перехода из состояния x 1 при t = t 1 в состояние x 2 при t = t 2 .
Цепями Маркова называют дискретные по времени и значению Марковские
процессы.
Пример 1
Предположим, что речь идет о последовательных бросаниях монеты при игре "в орлянку "; монета бросается в условные моменты времени t = 0, 1, ... и на каждом шаге игрок может выиграть ±1 с одинаковой вероятностью 1/2, таким образом в момент t его суммарный выигрыш есть случайная величина ξ(t) с возможными значениями j = 0, ±1, ... При условии, что ξ(t) = k, на следующем шаге выигрыш будет уже равен ξ(t+1) = k ± 1, принимая указанные знчения j = k ± 1 c одинаковой вероятностью 1/2. Условно можно сказать, что здесь с соответствующей вероятностью происходит переход из состояния ξ(t) = k в состояние ξ(t+1) = k ± 1.
19.5.1. Формулы и определения Марковских цепей
Обобщая этот пример, можно представить себе "систему" со счетным числом возможных "фазовых" состояний, которая с течением дискретного времени t = 0, 1, ... случайно переходит из состояния в состояние.
Пусть ξ(t) есть ее положение в момент t в результате цепочки случайных переходов ξ(0) - ξ(1) - ... - ξ(t) - ... ... (1)
Формально обозначим все возможные состояния целыми i = 0, ±1, ... Предположим, что при известном состоянии ξ(t) = k на следующем шаге система переходит в состояние ξ(t+1) = j с условной вероятностью
p kj = P(ξ(t+1) = j|ξ(t) = k) ... (2)
независимо от ее поведения в прошлом, точнее, независимо от цепочки переходов (1) до момента t:
P(ξ(t+1) = j|ξ(0) = i, ..., ξ(t) = k) = P(ξ(t+1) = j|ξ(t) = k) при всех t, k, j ... (3) - марковское свойство.
Такую вероятностную схему называют однородной цепью Маркова со счетным числом состояний - ее однородность состоит в том, что определенные в (2) переходные вероятности p kj , ∑ j p kj = 1, k = 0, ±1, ..., не зависят от времени, т.е.
P(ξ(t+1) = j|ξ(t) = k) = P ij - матрица вероятностей перехода за один шаг не зависит от n. Ясно, что P ij - квадратная матрица с неотрицатель-ными элементами и единичными суммами по строкам. Такая матрица (конечная или бесконечная) называется стохастической матрицей. Любая стохастическая матрица может служить матрицей переходных вероятностей.
Практический пример 1.
Предположим, что некая фирма осуществляет доставку оборудования по Москве: в северный округ (обозначим А), южный (В) и центральный (С). Фирма имеет группу курьеров, которая обслуживает эти районы. Понятно, что для осуществления следующей доставки курьер едет в тот район, который на данный момент ему ближе. Статистически было определено следующее:
1) после осуществления доставки в А следующая доставка в 30 случаях осуществляется в А, в 30 случаях - в В и в 40 случаях - в С;
2) после осуществления доставки в В следующая доставка в 40 случаях осуществляется в А, в 40 случаях - в В и в 20 случаях - в С;
3) после осуществления доставки в С следующая доставка в 50 случаях осуществляется в А, в 30 случаях - в В и в 20 случаях - в С.
Таким образом, район следующей доставки определяется только предыдущей доставкой.
Матрица вероятностей перехода будет выглядеть следующим образом:
Например, р 12 = 0.4 - это вероятность того, что после доставки в район В следующая доставка будет производиться в районе А. Допустим, что каждая доставка с последующим перемещением в следующий район занимает 15 минут. Тогда, в соответствии со статистическими данными, через 15 минут 30% из курьеров, находившихся в А, будут в А, 30% будут в В и 40% - в С. Так как в следующий момент времени каждый из курьеров обязательно будет в одном из округов, то сумма по столбцам равна 1. И поскольку мы имеем дело с вероятностями, каждый элемент матрицы 0<р ij <1. Наиболее важным обстоятельством, которое позволяет интерпретировать данную модель как цепь Маркова, является то, что местонахождение курьера в момент времени t+1 зависит только от местонахождения в момент времени t.
Теперь зададим простой вопрос: если курьер стартует из С, какова вероятность того, что осуществив две доставки, он будет в В, т.е. как можно достичь В в 2 шага? Итак, существует несколько путей з С в В за 2 шага:
1) сначала из С в С и потом из С в В;
2) С-->B и B-->B;
3) С-->A и A-->B.
Учитывая правило умножения независимых событий, получим, что искомая вероятность равна:
P = P(CA)*P(AB) + P(CB)*P(BB) + P(CC)*P(CB)
Подставляя числовые значения:
P = 0.5*0.3 + 0.3*0.4 + 0.2*0.3 = 0.33
Полученный результат говорит о том, что если курьер начал работу из С, то в 33 случаях из 100 он будет в В через две доставки. Ясно, что вычисления просты, но если Вам необходимо определить вероятность через 5 или 15 доставок - это может занять довольно много времени.
Рассмотрим более простой способ вычисления подобных вероятностей. Для того, чтобы получить вероятности перехода из различных состояний за 2 шага, возведем матрицу P в квадрат:
Тогда элемент (2, 3) - это вероятность перехода из С в В за 2 шага, которая была получена выше другим способом. Заметим, что элементы в матрице P 2 также находятся в пределах от 0 до 1, и сумма по столбцам равна 1.
Т.о. если Вам необходимо определить вероятности перехода из С в В за 3 шага:
1 способ. p(CA)*P(AB) + p(CB)*P(BB) + p(CC)*P(CB) = 0.37*0.3 + 0.33*0.4 + 0.3*0.3 = 0.333, где p(CA) - вероятность перехода из С в А за 2 шага (т.е. это элемент (1, 3) матрицы P 2).
2 способ. Вычислить матрицу P 3:
Матрица переходных вероятностей в 7 степени будет выглядеть следующим образом:
Легко заметить, что элементы каждой строки стремятся к некоторым числам. Это говорит о том, что после достаточно большого количества доставок уж не имеет значение в каком округе курьер начал работу. Т.о. в конце недели приблизительно 38,9% будут в А, 33,3% будут в В и 27,8% будут в С. Подобная сходимость гарантировано имеет место, если все элементы матрицы переходных вероятностей принадлежат интервалу (0, 1).
Теория массового обслуживания
Это раздел исследования операций , который рассматривает разнообразные процессы в экономике, а также в телефонной связи, здравоохранении и других областях, как процессы обслуживания, т. е. удовлетворения каких-то запросов, заказов (напр., обслуживание кораблей в порту - их разгрузка и погрузка, обслуживание токарей в инструментальной кладовой цеха - выдача им резцов, бслуживание клиентов в прачечной - стирка белья и т. д.).
При всем разнообразии эти процессы имеют общие черты: требования на обслуживание нерегулярно (случайно) поступают в канал обслуживания (место у причала, окно в раздаточной) и в зависимости от его занятости, продолжительности обслуживания и других факторов образуют очередьтребований .
Теория массового обслуживания изучает статистические закономерности поступления требований и на этой основе вырабатывает решения , т. е. такие характеристики, при которых затраты времени на ожидание в очереди, с одной стороны, и на простой каналов обслуживания - с другой, были бы наименьшими. Всю систему производства и потребления товаров можно трактовать как систему массового обслуживания, где встречаются люди (клиенты) и товары. Сумма потерь времени на ожидание в очередях и на простои каналов обслуживания (хранение товаров на складах) рассматривается как мера эффективности изучаемой экономической системы .
Методы анализа систем массового обслуживания
Методы и модели, применяемые в теории массового обслуживания, можно условно разделить на аналитические и имитационные.
Аналитические методы теории массового обслуживания позволяют получить характеристики системы как некоторые функции параметров ее функционирования. Благодаря этому появляется возможность проводить качественный анализ влияния отдельных факторов на эффективность работы СМО.
Имитационные методы основаны на моделировании процессов массового обслуживания на ЭВМ и применяются, если невозможно применение аналитических моделей.
В настоящее время теоретически наиболее разработаны и удобны в практических приложениях методы решения задач массового обслуживания, в которых входящий поток требований является простейшим (пуассоновским).
Для простейшего потока частота поступлений требований в систему подчиняется закону Пуассона, т.е. вероятность поступления за время t ровно к требований задается формулой:
Простейший поток обладает тремя основными свойствами:
1) ординарностью,
2) стационарностью и
3) отсутствием последействия.
Ординарность потока означает практическую невозможность одновременного поступления двух и более требований. Например, достаточно малой является вероятность того, что из группы станков, обслуживаемых бригадой ремонтников, одновременно выйдут из строя несколько станков.
Стационарным называется поток, для которого математическое ожидание числа требований, поступающих в систему в единицу времени (обозначим А, - параметр распределения Пуассона), не меняется во времени. Таким образом, вероятность поступления в систему определенного количества требований в течение заданного промежутка времени At зависит от его величины и не зависит от начала его отсчета на оси времени.
Отсутствие последействия означает, что число требований, поступивших в систему до момента t, не определяет того, сколько требований поступит в систему за промежуток времени от t до t + Dt
Например, если на ткацком станке в данный момент времени произошел обрыв нити и он устранен ткачихой, то это не определяет, произойдет новый обрыв на данном станке в следующий момент или нет, тем более это не влияет на вероятность возникновения обрыва на других станках.
Важная характеристика СМО - время обслуживания требований в системе. Время обслуживания одного требования является, как правило, случайной величиной и, следовательно, может быть описано законом распределения. Наибольшее распространение в теории и особенно в практических приложениях получил экспоненциальный закон распределения времени обслуживания. Функция распределения для этого закона имеет вид:
т.е. вероятность того, что время обслуживания не превзойдет некоторой величины t, определяется формулой (5.2), где µ - параметр экспоненциального закона распределения времени обслуживания требований в системе, т.е. величина, обратная среднему времени обслуживания
Системы массового обслуживания классифицируются:
1. В зависимости от условий ожидания начала обслуживания:
· СМО с потерями (отказами)
· СМО с ожиданием
В СМО с отказами требования, поступающие в момент, когда все каналы обслуживания заняты, получают отказ и покидают систему. Классическим примером системы с отказами является телефонная станция. Если вызываемый абонент занят, то требование на соединение с ним получает отказ и покидает систему.
В СМО с ожиданием требование, застав все обслуживающие каналы занятыми, становится в очередь и ожидает, пока освободится [ один из обслуживающих каналов.
СМО, допускающие очередь, но с ограниченным числом требований в ней, называются системами с ограниченной длиной очереди.
СМО, допускающие очередь, но с ограниченным сроком пребывания каждого требования в ней, называются системами с ограниченным временем ожидания.
2. По числу каналов обслуживания СМО делятся на:
Одноканальные;
Многоканальные.
3. По месту нахождения источника требований СМО подразделяются на:
разомкнутые, когда источник требования находится вне системы;
замкнутые, когда источник находится в самой системе.
19.7. Задачи анализа замкнутых и разомкнутых систем массового обслуживания
Замкнутые и разомкнутые системы,в зависимости от времени ожидания могут быть и системами массового обслуживания с ожиданием. Это наиболее распространенные СМО. Они изучаются с помощью аналитических моделей.
Системой массового обслуживания сожиданием называется система, в которой требования, поступившие в момент, когда все обслуживающие каналы заняты, ставятся в очередь и обслуживаются по мере освобождения каналов.
Примером разомкнутой системы может служить ателье по ремонту телевизоров. Здесь неисправные телевизоры - это источник требований на их обслуживание, они находятся вне самой системы, поэтому число требований можно считать неограниченным. К замкнутым СМО относится, например, станочный участок, в котором станки являются источником неисправностей, а следовательно, источником требований на их обслуживание, например, бригадой наладчиков.
Общая постановка задачи состоит в следующем. Система имеет п обслуживающих каналов, каждый из которых может одновременно обслуживать только одно требование.
В систему поступает простейший (пуассоновский) поток требований с параметром А.. Если в момент поступления очередного требования в системе на обслуживании уже находится не менее п требований, т.е. все каналы заняты, то это требование становится в очередь и ждет начала обслуживания. Время обслуживания каждого требования - случайная величина, которая подчиняется экспоненциальному закону распределения с параметром µ .
СМО с ожиданием можно разбить на две большие группы: замкнутые и разомкнутые. К замкнутым относятся системы, в которых поступающий поток требований возникает в самой системе и ограничен. Например, мастер, задачей которого является наладка станков в цехе, должен периодически их обслуживать. Каждый налаженный станок становится потенциальным источником требований на наладку. В подобных системах общее число циркулирующих требований конечно и чаще всего постоянно.
Если питающий источник обладает бесконечным числом требований и находится вне системы, то системы называют разомкнутыми. Примерами разомкнутых систем могут служить магазины, кассы вокзалов, портов и др. Для этих систем поступающий поток требований можно считать неограниченным. Кроме того, довольно распространены разомкнутые СМО с ожиданием и ограниченной длиной очереди, с ограниченным временем пребывания требования в очереди и др.
Отмеченные особенности функционирования СМО с ожиданием, обусловленные их видами, накладывают определенные условия на используемый математический аппарат. Расчет характеристик работы всех таких СМО может быть проведен на основе расчета вероятностей состояний СМО (так называемые формулы Эрланга).
Рассмотрим порядок расчета характеристик работы разомкнутых систем с ожиданием и ограниченной длиной очереди.
Такие СМО состоят из п обслуживающих каналов, каждый из которых может одновременно обслуживать только одно требование. В систему поступает простейший поток требований с параметром А., а время обслуживания требования является случайной величиной, которая подчиняется экспоненциальному закону распределения с параметром ц. Если в момент поступления очередного требования все п каналов заняты, а в очереди стоит не меньше т требований, то требование становится в очередь. Если же в очереди уже стоит т требований, то поступившее требование покидает СМО. Другими словами, требование получает отказ, если в системе находится п + т требований. Из уравнений, описывающих состояние таких систем, могут быть получены следующие формулы для расчета их основных характеристик.
1. Вероятность того, что все обслуживающие каналы свободны,
(5.14)
2. Вероятность того, что в системе находится к требований при условии, что общее число этих требований не превосходит числа обслуживающих каналов; другими словами, вероятность того, что занято к каналов,
 |
3. Вероятность того, что в системе находится к требований, когда число этих требований больше числа обслуживающих каналов,
(5.16)
4. Вероятность того, что все обслуживающие каналы заняты,
(5.17)
5. Вероятность отказа
(5.18)
6. Средняя длина очереди
7. Среднее число свободных от обслуживания каналов
Пример 2. Фирма занимается доставкой грузов по заказам и имеет четыре машины, которые работают круглосуточно. Поток заказов является простейшим, и в среднем за час поступает одна заявка. Время перевозки грузов подчиняется экспоненциальному закону распределения, и в среднем перевозка одного груза занимает один час. При количестве заказов на перевозки, равном 10, фирма прекращает прием заявок до тех пор, пока очередь не уменьшится.
Требуется определить характеристики работы фирмы.
Решение. Данная система относится к типу СМО с ожиданием и ограниченной длиной очереди. Найдем параметры системы, приняв за единицу времени один час:
Вероятность того, что все машины свободны от перевозки грузов, находится по формуле (5.14):
Вероятность того, что в се машины заняты, определяется по формуле (5.17) и составляет
Тогда вероятность отказа в принятии заказа на перевозку, рассчитываемая по формуле (5.18) будет равна
, а средняя длина очереди в соответствии с формулой (5.19) составит
Тогда вероятность отказа в принятии заказа на перевозку, рассчитываемая по формуле (5.18), будет равна
а средняя длина очереди в соответствии с формулой (5.19) составит
Таким образом, заказчик практически никогда не получит отказа в принятии заявки на перевозку, однако загрузка машин будет достаточно мала. Так например, лишь в двух случаях из ста будут заняты все четыре машины.
Перейдем к рассмотрению алгоритмов расчета характеристик функционирования замкнутых СМО с ожиданием. Поскольку система замкнутая, то к постановке задачи следует добавить условие: поток поступающих требований ограничен, т.е. в системе обслуживания одновременно не может находиться больше т требований (т - число обслуживаемых объектов). Такие СМО называются также системами с ожиданием и ограниченным потоком требований.
За критерий, характеризующий качество функционирования рассматриваемой системы, примем отношение средней длины очереди к наибольшему числу требований, находящихся одновременно в обслуживающей системе, или коэффициент простоя обслуживаемых объектов. В качестве другого критерия возьмем отношение среднего числа незанятых обслуживающих каналов к их общему числу, или коэффициент простоя обслуживающих каналов.
Первый из критериев характеризует потери времени из-за ожидания начала обслуживания. Второй критерий показывает полноту загрузки обслуживающей системы и имеет важное значение в задачах организации труда.
Очевидно, что очередь может возникнуть только в том случае, когда число каналов меньше наибольшего числа требований, находящихся одновременно в обслуживающей системе (п < т).
Приведем последовательность расчетов характеристик замкнутых СМО с ожиданием и необходимые формулы.
1. Параметр α=α/µ. -
показатель загрузки системы, т.е. математическое ожидание числа требований, поступающих в систему за время, равное средней длительности обслуживания 
2. Вероятность того, что занято к обслуживающих каналов при условии, что число требований, находящихся в системе, не превосходит числа обслуживающих каналов системы,
Теория СМО посвящена разработке методов анализа, проектирования и рациональной организации систем, относящихся к различным областям деятельности, таким как связь, вычислительная техника, торговля, транспорт, военное дело. Несмотря на все свое разнообразие, приведенные системы обладают рядом типичных свойств, а именно.
4 – Основы теории массового обслуживания.
Определение 1. Пусть имеется некоторая физическая система S , которая с течением времени меняет свое состояние (переходит из одного состояния в другое), причем заранее неизвестным, случайным образом. Тогда мы будем говорить, что в системе S протекает случайный процесс.
Под «физической системой» можно понимать что угодно: техническое устройство, предприятие, живой организм и т.д.
Пример. S – техническое устройство, состоящее из ряда узлов, которые время от времени выходят из строя, заменяются или восстанавливаются. Процесс, протекающий в системе, – случайный. Вообще, если подумать, труднее привести пример «неслучайного» процесса, чем случайного. Даже процесс хода часов – классический пример точной, строго выверенной работы («работают как часы») подвержен случайным изменениям (уход вперед, отставание, остановка).
Определение 2. Случайный процесс, протекающий в системе, называется марковским, если для любого момента времени t 0 вероятностные характеристики процесса в будущем зависят только от его состояния в данный момент t 0 и не зависят от того, когда и как система пришла в это состояние.
Пусть в настоящий момент t 0 система находится в определенном состоянии S 0 . Мы наблюдаем процесс со стороны и в момент t 0 знаем состояние системы S 0 и всю предысторию процесса, все, что было при t < t 0 . Нас, естественно. Интересует будущее: t > t 0 . Можем ли мы его предугадать? В точности – нет. Наш процесс случайный, следовательно – непредсказуемый. Но какие-то вероятностные характеристики процесса в будущем мы найти можем. Например, вероятность того, что через некоторое время t система S окажется в состоянии S 1 или сохранит состояние S 0 и т.д.
Если процесс марковский, то предсказывать можно, только учитывая настоящее состояние системы S 0 и забыв о его «предыстории» (поведение системы при t < t 0 ). Само состояние S 0 , разумеется, зависит от прошлого, но как только оно достигнуто, о прошлом можно забыть. Т.е. в марковском процессе «будущее зависит от прошлого только через настоящее» .
Пример. Система S – счетчик Гейгера, на который время от времени попадают космические частицы; состояние системы в момент времени t характеризуется показаниями счетчика – числом частиц, пришедших до данного момента. Пусть в момент t 0 счетчик показывает S 0 . Вероятность того, что в в момент t > t 0 счетчик покажет то или другое число частиц S 1 (или менее S 1 ) зависит от S 0 , но не зависит от того, в какие именно моменты приходили частицы до момента t 0 .
На практике часто встречаются процессы, которые если не в точности марковские, то могут быть в каком-то приближении рассмотрены как марковские. Например, S – группа самолетов, участвующих в воздушном бою. Состояние системы характеризуется числом самолетов «красных» – x и «синих» – y , сохранившихся (не сбитых) к какому-то моменту. В момент t 0 нам известны численности сторон x 0 и y 0 . Нас интересует вероятность того, что в какой-то момент времени t 0 + t численный перевес будет на стороне «красных». От чего зависит эта вероятность? В первую очередь от того, в каком состоянии находится система в данный момент времени t 0 , а не от того, когда и в какой последовательности погибали сбитые до момента времени t 0 самолеты.
В сущности любой процесс можно рассматривать как марковский, если все параметры из «прошлого», от которых зависит «будущее», перенести в «настоящее». Например, пусть речь идет о работе какого-то технического устройства; в какой-то момент времени t 0 оно ещё исправно, и нас интересует вероятность того, что оно проработает ещё время t . Если за настоящее время считать просто «система исправна», то процесс безусловно не марковский, потому что вероятность, что она не откажет за время t , зависит, в общем случае, от того, сколько времени она уже проработала и когда был последний ремонт. Если оба эти параметра (общее время работы и время после ремонта) включить в настоящее состояние системы. То процесс можно будет считать марковским.
Определение 3. Процесс называется с дискретными состояниями, если его возможные состояния S 1 , S 2 ,... можно заранее перечислить (перенумеровать), и переход системы из состояния в состояние происходит «скачком», практически мгновенно.
Определение 4. Процесс называется процессом с непрерывным временем, если моменты возможных переходов из состояния в состояние не фиксированы заранее, а неопределенны, случайны, если переход может осуществиться, в принципе, в любой момент.
Мы будем рассматривать только процессы с дискретными состояниями.
Пример. Техническое устройство S состоит из двух узлов. Каждый из которых в случайный момент времени может выйти из строя (отказать), после чего мгновенно начинается ремонт узла, тоже продолжающийся заранее неизвестное, случайное время.
| Рис.4.1 |
Возможные состояния системы:
S 0 – оба узла исправны;
S 1 – первый узел ремонтируется, второй исправен;
S 2 – второй узел ремонтируется, первый исправен;
S 3 – оба узла ремонтируются.
Стрелка, направленная из S 0 в S 1 означает момент отказа первого узла и т. д. На рисунке нет стрелки из состояния S 0 в состояние S 3 , поскольку вероятность того, что два прибора откажут одновременно, стремится к нулю.
Определение 5. Потоком событий называется последовательность однородных событий, следующих одно за другим в какие-то случайные моменты времени (например, поток сбоев на ЭВМ, поток вызовов на телефонной станции).
Важнейшей характеристикой потока событий является его интенсивность l – среднее число событий, приходящееся на единицу времени. интенсивность потока может быть постоянной (l = const ), так и переменной, зависящей от времени. Например, поток автомашин, движущихся по улице, днем интенсивнее, чем ночью, а поток автомашин с 14-ти до 15-ти часов дня можно считать постоянным.
Определение 6. Поток событий называется регулярным, если события следуют одно за другим через определенные, равные промежутки времени.
Определение 7. Поток событий называется стационарным, если его вероятностные характеристики не зависят от времени. В частности, интенсивность l стационарного потока должна быть постоянной. Это отнюдь не означает, что фактическое число событий, появляющееся в единицу времени, постоянно, – нет, поток неизбежно (если только он не регулярный) имеет какие-то случайные сгущения и разрежения. Важно, что для стационарного потока эти сгущения и разрежения не носят закономерного характера: на один участок длины 1 может попасть больше, а на другой – меньше событий, но среднее число событий, приходящееся на единицу времени, постоянно и от времени не зависит.
Например, поток вызовов, поступающих на АТС между 13 и 14 часами. Практически стационарен, но тот же поток в течение суток уже не стационарен.
Определение 8. Поток событий называется потоком без последействия, если для любых двух непересекающихся участков времени t 1 и t 2 число событий, попадающих на один из них, не зависит от того, сколько событий попало на другой. По сути это означает, что события, образующие поток, появляются в те или другие моменты независимо друг от друга, вызванные каждое своими собственными причинами.
Например, поток пассажиров, входящих в метро, практически не имеет последействия. А вот поток покупателей, отходящих от прилавка с купленными товарами, уже имеет последействие (хотя бы потому, что интервал времени между отдельными покупателями не может быть меньше, чем минимальное время обслуживания каждого из них).
Определение 9. Поток событий называется ординарным, если события в нем появляются поодиночке, а не группами сразу.
Например поток клиентов к зубному врачу – обычно ординарный. Поток поездов, подходящих к станции – ординарен, а поток вагонов – неординарен.
Определение 10.
Поток событий называется простейшим (или стационарным Пуассоновским), если он обладает сразу тремя свойствами: стационарен, ординарен и не имеет последействия, а сам входной поток распределен по закону Пуассона (
).
Для описания случайного процесса, протекающего в системе с дискретными состояниями S 1 , S 2 , ..., S n часто пользуются вероятностями состояний p 1 ( t ),..., p n ( t ) , где p k ( t ) – вероятность того, что в момент времени t система находится в состоянии S k . Вероятности p k ( t ) удовлетворяют условию: .
Если процесс, протекающий в системе с дискретными состояниями и непрерывным временем является марковским, то для вероятностей состояний p 1 ( t ), ..., p n ( t ) можно составить систему линейных дифференциальных уравнений. При составлении этих уравнений удобно пользоваться графом состояний системы, на котором против каждой стрелки, ведущей из состояния в состояние, проставлена интенсивность потока событий, переводящего систему по стрелке (рис.4.2):
|
Рис.4.2 l ij – интенсивность потока событий, переводящего систему из состояния S i в состояние S j . Правило создания системы линейных дифференциальный уравнений для нахождения вероятностей состояний. Для каждого состояния выписывается собственное уравнение. В левой части каждого уравнения стоит производная , а в правой – столько членов, сколько стрелок связано непосредственно с данным состоянием; если стрелка ведет в данное состояние, то член имеет знак «+», иначе - знак «–». Каждый член равен интенсивности потока событий, переводящего систему по данной стрелке, умноженной на вероятность того состояния, из которого стрелка выходит. Т.о. система линейных дифференциальных уравнений в нашем случае имеет вид:
|
Начальные условия для интегрирования такой системы отражают состояние системы в начальный момент времени. Если, например, система при t =0 была в состоянии S k , то . Эти уравнения можно решать аналитически, но это удобно только тогда, когда число уравнений не превышает двух (иногда трех). В случае, когда уравнений оказывается больше, применяют численные методы.
Что будет происходить с вероятностями состояний при ? Будут ли
p
1
(
t
), ...,
p n
(
t
)
стремиться к каким-то пределам? Если эти пределы существуют и не зависят от начального состояния системы, то они называются финальными вероятностями состояний: 
.
p i
– среднее относительное время пребывания системы в
i
-ом состоянии.
Как найти финальные вероятности? Поскольку все p i = const , то производные, стоящие в левой части каждого уравнения равны нулю. Т.о. мы получили систему линейных алгебраических уравнений. Поскольку ни одно уравнение в этой системе не имеет свободного члена, то система является вырожденной (т.е. все переменные будут выражены через одну). Чтобы этот избежать, необходимо воспользоваться нормировочным условием (), при этом любое уравнение можно отбросить.
Классификация систем массового обслуживания
По количеству обслуживающих приборов СМО делятся на одноканальные и многоканальные. Многоканальные СМО состоят из нескольких приборов, и каждый них может обслуживать заявку.
Также СМО подразделяются на системы без ожидания и с ожиданием. В первых заявка покидает очередь, если к моменту её прихода отсутствует хотя бы один канал, способный немедленно приступить к обслуживанию данной заявки. Вторые, в свою очередь, делятся на системы без ограничения и с ограничениями по длине очереди.
Также СМО делятся на системы с приоритетами и без них. В свою очередь системы с приоритетом делятся на СМО с прерыванием и без.
Одноканальная СМО с неограниченной очередью
Рис.4.3
Найдем вероятности p k :
Для состояния
S
0
: 
, отсюда ;
Для состояния
S
1
n
:
, подставляем полученное значение для
p
1
: 
. Аналогично, .
Вероятность p 0 найдем из нормировочного условия :
, 
– геометрическая прогрессия, при
r
<1
сходится. 
– вероятность того, что нет заявок.
– вероятность того, что прибор занят обслуживанием заявки. r = l / m – мера загрузки одноканальной СМО.
В текущий момент времени в системе может быть 0, 1, 2, ..., k , ... заявок с вероятностями p 0 , p 1 p 2 , ... Математическое ожидание количества заявок:
учитывая, что 
, получим:
Средняя длина очереди равна разности между средним числом заявок в системе и средним числом заявок, находящихся под обслуживанием: 
.
Формулы Литтла
|
Рис.4.4 |
Первая формула Литтла позволяет определить время реакции СМО (время пребывания заявки в системе).
Пусть
X
(
t
)
– число заявок, поступивших в СМО до момента времени
t
,
Y
(
t
)
– покинувших СМО до
t
. Обе функции случайны и увеличиваются скачком на единицу в моменты прихода и ухода заявок. Тогда число заявок в системе в момент времени
t
можно определить как: 
. Рассмотрим очень большой промежуток времени
T
и вычислим среднее число заявок в системе:
.
Интеграл равен площади ступенчатой фигуры, ограниченной функциями
X
(
t
)
и
Y
(
t
)
, эта сумма состоит из прямоугольников, ширина которых равна единице, а длина – времени пребывания
i
-ой заявки в системе. Сумма распространяется на все заявки, поступившие в систему за время
T
. Правую часть домножим и разделим на
l
: .
T
l
– среднее количество заявок, пришедших за время
T
. Поделив сумму всех времен
t i
на среднее число заявок, получим среднее время пребывания заявки в системе: 
.
Совершенно аналогично можно получить среднее время пребывания заявки в очереди: .
Многоканальная СМО с неограниченной очередью
Рис.4.5
Найдем вероятности p k :
Для состояния
S
0
: ;
Для состояний S 1 – S n : ;
Для S n +1 : ; ...
Для S n+s-1 : ;
Для S n+s : .
Из первых
n
+1 уравнений получаем: 
Из последнего уравнения выражаем: 
и подставляем в предпоследнее: , 
. Тогда 
.
Продолжая аналогию: 
.
Теперь найдем
p
0
, подставив полученные выражения в нормировочное условие (): 
. Отсюда 
.
Показатели эффективности СМО
– Вероятность потери требования в СМО. Особенно часто ею пользуются при исследовании военных вопросов. Например, при оценке эффективности противовоздушной обороны объекта она характеризует вероятность прорыва воздушных целей к объекту. Применительно к СМО с потерями она равна вероятности занятости обслуживанием требований всех n приборов системы. Чаще всего эту вероятность обозначают p n или p отк .
– Вероятность того, что обслуживанием требований в системе занято k приборов, равна p k .
– Среднее число занятых приборов: 
характеризует степень загрузки обслуживающей системы.
– Среднее число свободных от обслуживания приборов:
.
– Коэффициент простоя приборов: .
– Коэффициент занятости оборудования: .
– Средняя длина очереди: 
,
p k
- вероятность того, что в системе находится
k
требований.
– Среднее число заявок, находящихся в сфере обслуживания: 
.
– Вероятность того, что число заявок в очереди, ожидающих начала обслуживания, больше некоторого числа
m
: 
. Этот показатель особенно необходим при оценке возможностей размещения требований при ограниченности времени для ожидания.
Кроме перечисленных критериев при оценке эффективности СМО могут быть использованы стоимостные показатели:
q об – стоимость обслуживания каждого требования в системе;
q ож – стоимость потерь, связанных с простаиванием заявок в очереди в единицу времени;
q у – убытки, связанные с уходом из системы заявки;
q k – стоимость эксплуатации каждого прибора в единицу времени;
q k пр – стоимость простоя единицы времени k -го прибора системы.
При выборе оптимальных параметров СМО по экономическим показателям можно использовать функцию стоимости потерь в системе (для СМО с ожиданием): T – интервал времени.
Для СМО с отказами: .
Для смешанных: .
Критерий экономической эффективности СМО: 
, с
– экономический эффект, получаемый при обслуживании каждой заявки.
СМО замкнутого типа
|
|
Пример. С1, С2, С3 – станки; НЦ – центральный накопитель; B – манипулятор. Транспортная тележка (манипулятор) транспортирует отработанную деталь от станка к накопителю и укладывает ее там, забирает новую деталь (заготовку), транспортирует ее к станку и устанавливает в рабочую позицию для зажима. Во время всего периода, необходимого для выгрузки–загрузки, станок простаивает. Время T з смены заготовки и есть время обслуживания.
Интенсивность обслуживания станков определяется как , – среднее время обслуживания станка, которое вычисляется как 
, где
n
– число заявок. Интенсивность подачи станком заявки на обслуживание определяется как (где – среднеее время обработки детали станком).
Станочная система с однозахватным манипулятором представляет собой СМО с ожиданием с внутренней организацией FIFO : каждая заявка станка на обслуживание удовлетворяется, в случае когда манипулятор занят, заявка становится в очередь и станок ожидает когда манипулятор освободится. Данный процесс марковский, т.е. случайная выдача заявки на обслуживание в определенный момент времени t 0 не зависит от предыдущих заявок, т.е. от течения процесса в предшествующий период. Продолжительность исполнения заявки может быть различной и является случайной величиной, не зависящей от числа поданных заявок. Весь процесс не зависит от того, что произошло ранее момента времени t 0 .
В станочной системе число заявок на обслуживание может быть равно 0, 1, 2, ... m , где m – общее число станков. Тогда возможны следующие состояния:
S 0 – все станки работают, манипулятор стоит.
S 1 – все станки, кроме одного, работают, манипулятор обслуживает станок, от которого поступила заявка на смену заготовок.
S 2 – работают m -2 станка, на одном станке идет смена заготовки, другой ожидает.
S 3 – работают m -2 станка, один станок обслуживается манипулятором, два станка ожидают в очереди.
S m – все станки стоят, один обслуживается манипулятором, остальные ожидают очереди исполнения заказа.
Рис.4.6.
Вероятность перехода в состояние S k из одного из возможных состояний S 1 , S 2 , ... S m зависит от случайного поступления заявок на обслуживание и вычисляется как:
p 0 – вероятность того, что все станки работают.
Манипулятор работает при состояниях системы от S 1 до S m . Тогда вероятность его загрузки равна: .
Число станков, находящихся в очереди связано с состояниями
S
2
, –
S m
, при этом один станок обслуживается, а (k
-1) – ожидают. Тогда, среднее число станков в очереди: 
.
Коэффициент простоя одного станка (из-за ожидания при многостаночном обслуживании): 
.
Среднее использование одного станка:
Применение метода Монте-Карло для решения задач,
связанных с теорией массового обслуживания
Для того, чтобы описать поток однородных событий, достаточно знать закон распределения моментов времени t 1 , t 2 , ..., t k , ..., в которые поступают события.
Для удобства дальнейших рассмотрений целесообразно от величин t 1 , t 2 , ..., перейти к случайным величинам z 1 , z 2 , ..., z m , ... , таким образом, что:
Случайные величины z k являются длинами интервалов времени между последовательными моментами t k .
Совокупность случайных величин z i считается заданной, если определена совместная функция распределения: . Обычно рассматриваются только непрерывные случайные величины z k , поэтому часто пользуются соответствующей функцией плотности f ( z 1 , z 2 ,..., z k ) .
Обычно в теории СМО рассматриваются потоки однородных событий без последействия, для которых случайные величины z k независимы. Поэтому . Функции f i ( z i ) при i >1 представляют собой условные функции плотности при условии, что в начальный момент интервала z k ( i >1) поступила заявка. В отличие от этого функция f 1 ( z 1 ) является безусловной функцией плотности, т.к. относительно появления или непоявления заявки в начальный момент времени не делается никаких предположений.
Широкое применение имеют так называемые стационарные потоки, для которых вероятностный режим их во времени не изменяется (т.е. вероятность появления k заявок за промежуток времени (t 0 , t 0 + t ) не зависит от t 0 , а зависит только от t и k ). Для стационарных потоков без последействия имеют место соотношения:
где l – плотность стационарного потока.
Поступившая в систему заявка может занимать только свободные линии. Относительно порядка занятия линий могут быть сделаны различные предположения:
а) линии занимаются в порядке их номеров. Линия с большим номером не может быть привлечена к обслуживанию заявки, если имеется свободная линии с меньшим номером;
б) линии занимаются в порядке очереди. Освободившаяся линия поступает в очередь и не начинает обслуживания заявок до израсходования всех ранее освободившихся линий;
в) линии занимаются в случайном порядке в соответствии с заданными вероятностями. Если в момент поступления очередной заявки имеется
n
св
свободных линий, то в простейшем случае вероятность занять некоторую определенную линию может быть принята равной . В более сложных случаях вероятности
считаются зависящими от номеров линий, моментов их освобождения и других параметров.
Аналогичные предположения можно сделать и относительно порядка принятия заявок к обслуживанию в том случае, когда в системе образуется очередь заявок:
а) заявки принимаются к обслуживанию в порядке очереди. Освободившаяся линия приступает к обслуживанию той заявки, которая ранее другой поступила в систему;
б) заявки принимаются к обслуживанию по минимальному времени получения отказа. Освободившаяся линия приступает к обслуживанию той заявки, которая в кратчайшее время может получить отказ;
в) заявки принимаются к обслуживанию в случайном порядке в соответствии с заданными вероятностями. Если в момент освобождения линии имеется m заявок в очереди, то в простейшем случае вероятность выбрать для обслуживания некоторую определенную заявку может быть принята равной q =1/ m . В более сложных случаях вероятности q 1 , q 2 ,..., q m считаются зависящими от времени пребывания заявки в системе, времени, остающегося до получения отказа и других параметров.
· Для решения ряда прикладных задач оказывается необходимым учитывать такой важный фактор, как надежность элементов обслуживающей системы. Будем предполагать, что с точки зрения надежности каждая линия в данный момент времени может быть либо исправной, либо неисправной. Надежность линии определяется вероятностью безотказной работы R = R ( t ) , задаваемой как функция времени. Будем также предполагать, что линия, вышедшая из строя по причине неполной надежности, может быть введена в строй (отремонтирована), для чего требуется затратить время t p . Величину t p будем считать случайной величиной с заданным законом распределения.
Относительно судьбы заявки, при обслуживании которой линия выходит из строя, могут быть сделаны различные предположения: заявка получает отказ; заявка остается в системе (с общим временем пребывания в системе не более t n ) как претендент на обслуживание вне очереди; заявка поступает в очередь и обслуживается на общих основаниях и т.д.
Сущность метода статистических испытаний применительно к задачам массового обслуживания состоит в следующем. Строятся алгоритмы, при помощи которых можно вырабатывать случайные реализации заданных потоков однородных событий, а также «моделировать» процессы функционирования обслуживающих систем. Эти алгоритмы используются для многократного воспроизведения реализаций случайного процесса обслуживания при фиксированных условиях задачи. Получаемая при этом информация о состояниях процесса подвергается статистической обработке с целью оценки, являющихся показателями качества обслуживания.
Метод статистических испытаний позволяет более полно, по сравнению с асимптотическими формулами, исследовать зависимость качества обслуживания от характеристик потока заявок и параметров обслуживающей системы.
Это достигается благодаря двум обстоятельствам. Во-первых, при решении задач теории массового обслуживания методом статистических испытаний может быть использована более обширная информация о процессе, чем это обычно удается сделать, применяя аналитические методы.
С другой стороны, значения показателей качества обслуживания, получаемые из асимптотических формул, строго говоря, относятся к моментам времени, достаточно удаленным от начала процесса. Реально, для моментов времени, близких к началу процесса, когда еще не наступил стационарный режим, значения показателей качества обслуживания в общем случае существенно отличаются от асимптотических значений. Метод статистических испытаний позволяет достаточно обстоятельно изучать переходные режимы.
Для многих прикладных задач предположения, при которых справедливы аналитические формулы, оказываются слишком стеснительными. При решении задач методом статистических испытаний некоторые предположения могут быть существенно ослаблены.
В первую очередь это относится к многофазному обслуживанию (т.е. рассматриваются обслуживающие системы, состоящие из нескольких последовательно действующих в общем случае неоднотипных агрегатов).
Другим важным обобщением задачи является предположение о характере потока заявок, поступающих на обслуживание. Допускается рассмотрение потоков однородных событий с практически произвольным законом распределения. Последнее обстоятельство оказывается существенным по следующим двум причинам. Во-первых, реальные потоки заявок в некоторых случаях заметно отличаются от простейшего. Для пояснения второй причины предположим, что исходный поток заявок достаточно точно аппроксимируется простейшим потоком. При этом поток заявок, обслуженных на первой фазе, уже, строго говоря не будет простейшим. Поскольку поток, являющийся выходным для первой фазы, будет входным потоком для агрегата, обслуживающего заявки на второй фазе, мы снова приходим к задаче обслуживания потоков, не являющимися простейшими.
· Структура алгоритма, моделирующего
процесс обслуживания заявок
Рассмотрим однофазную СМО, имеющую n линий, на которые поступают заявки в случайные моменты времени t i . Если вмомент поступления заявки оказываются в наличии свободные линии (их число n св ), заявка занимает одну из них на время t p . В противном случае заявка находится в системе до момента t n , ожидая обслудивания. В т t чение времени ожидания некоторые линии могут освободиться (их число m ), и в этом случае будет возможность обслужить заявку. Если до момента времени t n ни одна из линий не освобождается (m =0 ), заявка получает отказ.
Будем считать, что в силу недостаточно высокой надежности системы, линии обслуживающие заявку, могут выходить из строя, тогда заявка получает отказ, а линия может быть отремонтирована и через промежуток времнеи t pem введена в строй.
Для исследования качества обслуживания заявок предусматривается N * кратное моделирование процесса функционирования системы в интервале (0, T ) . В процессе моделирования число обследованных реализаций обозначим через N .
Алгоритм:
1. Определяется момент t i поступления очередной заявки в систему.
2. Если t i < T , то переход на шаг 3, иначе – на шаг 11.
3. Проверка возможности обслужить поступившую заявку: если n св >0 , то переход на шаг 4, иначе – на шаг 12. (Значение времени поступления заявки t i сравнивается с t осв для всех линий, т.о. выявляются свободные линии.)
4.Если n св >1 , то переход на шаг 5, иначе – на шаг 6.
5. Выбирается номер свободной линии по специальным правилам.
6. Назначается выбранная линия.
7. Проверка: имеет ли место срыв обслуживания по причине недостаточной надежности? Если да, то переход на шаг 8, иначе – на шаг 10.
8. Определение времени t рем ремонта линии, вышедшей из строя (t рем имеет определенный закон распределения).
9. N отк = N отк +1 . Переход на шаг 1.
10. Определение времени занятости t з линии, которая назначена обслуживать заявку (некая случайная величина с определенным законом распределения) и времени освобождения линии: t осв = t i + t з . Переход к очередной заявке (шаг 1).
11. Проверка: если N < N * , то N = N +1 и переход на шаг 1, иначе – обработка результатов опыта и конец.
12. Определить:
А) времени t n пребывания заявки в системе;
Б) число освободившихся каналов m за время t n .
13. Если m >0 , то переход на шаг 14, иначе – на шаг 9.
14. Если m >1 , то переход на шаг 15, иначе – на шаг 6.
15. Выбирается определенная линия в соответствии с принятыми правилами и переход на шаг 6.
Федеральное агентство по образованию Т. А. Радченко, А. В. Дылевский Методы анализа систем массового обслуживания Учебное пособие для вузов Воронеж 2007 2 Утверждено Научно-методическим советом факультета прикладной ма- тематики, информатики и механики 27 декабря 2006 г., протокол № 4 Учебное пособие подготовлено на кафедре технической кибернетики и автоматического регулирования факультета прикладной математики, ин- форматики и механики Воронежского государственного университета. Рекомендуется для студентов 4 курса д/о и 5 курса в/о. Для специальности: 010200 (010501) - Прикладная математика и ин- форматика 3 Содержание Введение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1. Теоретическая часть 4 1. Теория массового обслуживания, ее математический аппарат и приложения. . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Случайные процессы. . . . . . . . . . . . . . . . . . . . . . . 5 3. Многомерные функции распределения, плотности вероятно- стей, вероятности случайного процесса. . . . . . . . . . . . . 6 4. Условные вероятности и плотности вероятностей. . . . . . . . 7 5. Классификация случайных процессов. . . . . . . . . . . . . . 8 6. Марковские случайные процессы. . . . . . . . . . . . . . . . 9 7. Цепи Маркова. . . . . . . . . . . . . . . . . . . . . . . . . . . 10 8. Уравнения Колмогорова–Чепмена. . . . . . . . . . . . . . . . 11 9. Классификация состояний марковской цепи. . . . . . . . . . 12 10. Циклические подклассы и матрица вероятности перехода для периодической цепи. . . . . . . . . . . . . . . . . . . . . 15 11. Стационарные и эргодические цепи Маркова. . . . . . . . . 16 12. Дискретные марковские процессы (цепи Маркова с непрерывным временем) . . . . . . . . . . . . . . . . . . . . 19 13. Уравнения Колмогорова. . . . . . . . . . . . . . . . . . . . . 20 14. Стационарное распределение вероятностей. . . . . . . . . . 24 15. Случайный поток событий. . . . . . . . . . . . . . . . . . . . 25 16. Классификация потоков событий. . . . . . . . . . . . . . . . 25 17. Пуассоновский поток событий. . . . . . . . . . . . . . . . . 26 18. Пуассоновский случайный процесс. . . . . . . . . . . . . . . 26 19. Системы массового обслуживания. . . . . . . . . . . . . . . 28 20. Одноканальная система массового обслуживания с отказами 29 21. Характеристики одноканальной системы массового обслу- живания с отказами. . . . . . . . . . . . . . . . . . . . . . . . 31 22. Многоканальная система массового обслуживания с отказами 32 23. Многоканальная система с отказами и полной взаимопомо- щью между каналами. . . . . . . . . . . . . . . . . . . . . . . 34 24. Многоканальная СМО с ожиданием (с очередью конечной длины) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 25. СМО с неограниченной очередью. . . . . . . . . . . . . . . . 38 26. Замкнутые системы массового обслуживания. . . . . . . . . 39 4 2. Лабораторные работы 41 1. Цепи Маркова. . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2. Дискретные марковские процессы. . . . . . . . . . . . . . . . 44 3. Исследование СМО. . . . . . . . . . . . . . . . . . . . . . . . 47 3. Mathcad 49 1. Арифметические вычисления. . . . . . . . . . . . . . . . . . . 51 2. Использование формул в Mathcad . . . . . . . . . . . . . . . . 51 3. Работа с векторами и матрицами. . . . . . . . . . . . . . . . . 52 4. Построение графиков в среде Mathcad . . . . . . . . . . . . . 54 5. Решение обыкновенных дифференциальных уравнений. . . . 56 6. Чтение и запись данных. . . . . . . . . . . . . . . . . . . . . . 59 Приложение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 Литература. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 Введение Системы массового обслуживания (СМО) в настоящее время широ- ко используются во многих прикладных областях. Данное пособие имеет цель - оказать помощь студентам в овладении теоретическими осно- вами и приобретении элементарных навыков в решении задач по теории массового обслуживания на персональном компьютере. Первая глава пособия содержит краткие сведения из теории случай- ных процессов и потоков событий, их применение к анализу типичных систем массового обслуживания с простейшим потоком заявок. Во второй главе содержатся задания для лабораторных работ и за- дачи для самостоятельного решения. В третьей главе представлены сведения о пакете Mathcad, необходи- мые для выполнения лабораторных работ по данному курсу. Глава 1. Теоретическая часть 1. Теория массового обслуживания, ее математический аппарат и приложения В науке, производстве, практической деятельности человека и даже в быту имеет место спрос на выполнение тех или иных операций (об- служивание). Заявки на обслуживание могут поступать в виде потока, и практически всегда существует ограничение на количество, скорость, качество обслуживающих единиц. Возникает задача синтеза систем (си- стем массового обслуживания), которые обеспечивали бы обслуживание 5 с учетом случайного характера потока заявок, времени обслуживания и других параметров. Для решения задач анализа и синтеза таких систем разработана теория массового обслуживания. Определение 1. Теория массового обслуживания - прикладная теоретико- вероятностная дисциплина, изучающая случайные процессы в системах обслуживания различного назначения с целью рационального построе- ния и анализа этих систем . Теория массового обслуживания возникла сравнительно недавно. Пер- вые работы по ТМО были выполнены в 20-х годах ХХ-го в. А. Эрлангом и были посвящены расчетам телефонных сетей. Проектирование различ- ных систем связи (в том числе компьютерных сетей, подвижных систем, АТС) и сейчас является основным приложением ТМО. Но современная область приложения ТМО гораздо шире, она включает в себя: производство (расчет количества оборудования и обслуживающе- го персонала, требуемой производительности при заданной рента- бельности и т.п.); экономику и бизнес (расчет числа торговых точек, распределение товаров, финансовых ресурсов с учетом потока клиентов и их по- требительской возможности и т.п.); сферу обслуживания (создание рентабельных и удобных для кли- ентов кафе, магазинов, ателье, автозаправочных станций, портов и т.п.) и многое другое. Процессы, протекающие в системах массового обслуживания, но- сят случайный характер, поэтому ТМО базируется на теории случайных процессов, элементы которой изложены ниже. 2. Случайные процессы Определение 2. Пусть для некоторого опыта задано вероятностное про- странство Ω, A, P , где Ω - пространство элементарных событий, A - алгебра его подмножеств, P - вероятностная мера на A. Случайным процессом ξ(t), заданным на данном вероятностном пространстве, на- зывается измеримая функция двух переменных ξ(t, ω), где ω ∈ Ω, а t - действительная переменная (t ∈ R), которая часто имеет смысл времени . 6 При фиксированном значении t = ti случайный процесс представля- ет собой измеримую функцию ξi = ξi (ω), т.е. случайную величину. При фиксированном элементарном событии ωi получаем некоторую детерминированную (неслучайную) функцию xi (t), называемую реали- зацией (траекторией) случайного процесса. Случайный процесс можно задавать или как множество реализаций с заданной на нем вероятностной мерой, или как последовательность (упо- рядоченную совокупность) случайных величин, соответствующих опре- деленным значениям t. В последнем случае его можно рассматривать как случайный вектор и задать с помощью многомерных законов распреде- ления. 3. Многомерные функции распределения, плотности вероятностей, вероятности случайного процесса Определение 3. Многомерной функцией распределения случайного про- цесса для фиксированных моментов времени t1 , t2 , . . . , tn называется функ- ция 2n переменных, определяемая следующим образом: F (x1 , x2 , . . . , xn , t1 , t2 , . . . , tn) = = P (ξ(t1) < x1 , ξ(t2) < x2 , . . . , ξ(tn) < xn). (1) Для непрерывнозначного процесса можно определить многомерную плотность вероятностей ∂ n F (x1 , . . . , xn , t1 , . . . , tn) f (x1 , x2 , . . . , xn , t1 , t2 , . . . , tn) = . (2) ∂ x1 . . . ∂xn Если случайный процесс дискретного типа (множество возможных значений дискретно), то можно определить многомерные вероятности P (x1 , x2 , . . . , xn , t1 , t2 , . . . , tn) = = P (ξ(t1) = x1 , ξ(t2) = x2 , . . . , ξ(tn) = xn). (3) Случайный процесс считается заданным, если заданы многомерные функции распределения (плотности вероятностей или многомерные ве- роятности) любой размерности. Замечание 1. Если t изменяется непрерывно, то для полного описания случайного процесса необходимо в многомерных законах распределения 7 (1)–(3) устремить n к бесконечности (n → ∞). Но этот предельный пе- реход представляет определенные математические трудности. Кроме то- го, работать с многомерными функциями (1)–(3) при конечном, но боль- шом значении n тоже не всегда удобно. Существуют классы процессов, для полного описания которых до- статочно знать двумерные законы распределения. К таким процессам относятся марковский и гауссовский процессы, которые наиболее часто используются в приложениях. 4. Условные вероятности и плотности вероятностей Для процесса дискретного типа можно определить условные веро- ятности (вероятность того, что в момент времени t2 значение процесса равно x2 , если в момент времени t1 оно равнялось x1): P (x1 , x2 , t1 , t2) P (x2 , t2 | x1 , t1) = . (4) P (x1 , t1) Для непрерывнозначного процесса условные плотности вероятностей имеют вид f (x1 , x2 , t1 , t2) f (x2 , t2 | x1 , t1) = . (5) f (x1 , t1) В n-мерном случае условные вероятности и плотности вероятностей определяютcя аналогично: P (x1 , . . . xn , t1 , . . . , tn) P (xn , tn | x1 , . . . xn−1 , t1 , . . . , tn−1) = , P (x1 , . . . , xn−1 , t1 , . . . , tn−1) f (x1 , . . . , xn , t1 , . . . , tn) f (xn , tn | x1 , . . . , xn−1 , t1 , . . . , tn−1) = . f (x1 , . . . , xn−1 , t1 , . . . , tn−1) Замечание 2. Условные вероятности (4) и плотности вероятностей (5) в теории случайных процессов называют переходными. Определение 4. Случайный процесс называется однородным, если услов- ные вероятности или условные плотности вероятностей зависят не от мо- ментов времени, а от разности моментов времени, т.е. P (x2 , t2 | x1 , t1) = P (x2 , x1 , t2 − t1), (6) f (x2 , t2 | x1 , t1) = f (x2 , x1 , t2 − t1). 8 5. Классификация случайных процессов Как отмечается в , строгой классификации случайных процессов нет, поэтому можно говорить лишь о выделении по тому или иному при- знаку типов процессов, которые не обязательно в своей совокупности исчерпывают всевозможные типы и не являются несовместимыми друг с другом. Случайные процессы можно классифицировать по: 1) характеру реализаций случайных процессов (характеру простран- ства состояний случайного процесса и параметра t); 2) виду закона распределения вероятностей; 3) характеру статистической связи между значениями случайного про- цесса в различные моменты времени. Классификация по характеру реализаций. 1. Дискретная последовательность (дискретный процесс с дискрет- ным временем) - это случайный процесс, у которого областью определения и областью возможных значений реализаций являют- ся дискретные множества. Примеры: процессы в цифровых систе- мах связи, компьютерных сетях, цифровой радиоаппаратуре и т.п. 2. Случайная последовательность, или временной ряд (непрерывно- значный процесс с дискретным временем) - это случайный про- цесс, область возможных значений реализаций которого - непре- рывное множество, а область определения - дискретное множе- ство. Примеры: метеорологические наблюдения, телеметрические данные состояния космонавтов и т.п. 3. Дискретный процесс (дискретный процесс с непрерывным време- нем) - это случайный процесс, множество возможных значений реализаций которого - дискретное множество, а область опреде- ления - непрерывное множество. Примеры: число абонентов те- лефонной станции, разговаривающих по телефону, количество ав- томобилей на автозаправочной стации и т.п. 4. Непрерывнозначный случайный процесс - это случайный процесс, у которого область возможных значений и область определения - непрерывные множества. Примеры: различные физические, хи- мические, биологические процессы, протекающие в природе, орга- низме человека. 9 Замечание 3. Случайные процессы с дискретным множеством возмож- ных значений (типы 1 и 3) называются цепями (последовательно перехо- дят от одного состояния к другому, образуя цепочку состояний). Если рассматривать классификацию случайных процессов по харак- теру статистической связи между значениями в отдельные моменты вре- мени, можно выделить наиболее простой и хорошо изученный тип - мар- ковский процесс. 6. Марковские случайные процессы Марковский случайный процесс - такой случайный процесс, эво- люция которого после любого фиксированного момента t (в будущем) и до момента t (в прошлом) является независимой при известном состо- янии в момент t (в настоящем) . Это основное свойство марковского процесса, которое можно математически записать по-разному. Определение 5. Случайный процесс ξ(t) называется марковским, если для любых моментов времени, связанных условием tk < tj < ti , спра- ведливо соотношение P (ξ(tk) < xk , ξ(ti) < xi | ξ(tj) = xj) = = P (ξ(tk) < xk | ξ(tj) = xj)P (ξ(ti) < xi | ξ(tj) = xj). (7) Для дискретного случайного процесса можно записать P (ξ(tk) = xk , ξ(ti) = xi | ξ(tj) = xj) = = P (ξ(tk) = xk | ξ(tj) = xj)P (ξ(ti) = xi | ξ(tj) = xj). (8) Можно дать эквивалентное определение марковского процесса в несколь- ко иной математической форме. Определение 6. Случайный процесс ξ(t) называется марковским, если P (ξ(tn) < xn | ξ(t1) = x1 , . . . , ξ(tn−1) = xn−1) = = P (ξ(tn) < xn | ξ(tn−1) = xn−1). (9) Для дискретного случайного процесса имеем P (ξ(tn) = xn | ξ(t1) = x1 , . . . , ξ(tn−1) = xn−1) = = P (ξ(tn) = xn | ξ(tn−1) = xn−1). (10) В обширном классе марковских случайных процессов можно выде- лить различные типы по характеру реализаций. 10 1. Дискретная последовательность (цепь Маркова). 2. Случайная (марковская) последовательность. 3. Дискретный случайный процесс (дискретный марковский процесс). 4. Непрерывнозначный случайный процесс (непрерывнозначный мар- ковский процесс). В теории массового обслуживания наиболее часто используются мар- ковские цепи и дискретные марковские процессы, последние иногда на- зывают марковскими цепями с непрерывным временем. 7. Цепи Маркова Определение 7. Цепь Маркова - это марковский случайный процесс с дискретными множествами возможных значений (состояний цепи) E1 , . . . , En и значений аргумента t0 , t1 , t2 , t3 , . . .. Если число возможных состояний n конечно, то цепь называется ко- нечной. Вместо значений аргумента можно указывать их номер. Разность меж- ду двумя соседними значениями аргумента tk+1 − tk называется шагом. Цепь Маркова задается множеством значений (E1 , . . . , En) и следу- ющими вероятностями. 1. Начальные вероятности Pj0 = P (ξ(0) = Ej), которые удовлетво- ряют условию нормировки Pj0 = 1. j 2. P (ξ(n + 1) = Ej | ξ(n) = Ei) - вероятность перехода из одного состояния в другое за один шаг. Если марковская цепь однород- на, то P (ξ(n + 1) = Ej | ξ(n) = Ei) = Pij . Условие нормировки Pij = 1. j 3. Вероятность перехода из одного состояния в другое за k шагов P (ξ(n+ k) = Ej | ξ(n) = Ei). Если марковская цепь однородна, то P (ξ(n + k) = Ej | ξ(n) = Ei) = Pij (k). Условие нормировки Pij (k) = 1. j 4. Вероятность состояния Ej в k-й момент времени: P (ξ(k) = Ej) = Pj (k). Условие нормировки Pj (k) = 1. j
