Рефотека.ру / Математика

Курсовая работа: Система массового обслуживания с ограниченным временем ожидания

Федеральное агентство по образованию РФ

ФГОУ СПО «Перевозский строительный колледж»


Курсовая работа

по дисциплине «Математические методы»

на тему «СМО с ограниченным временем ожидания. Замкнутые СМО»


Перевоз

2008

Содержание


Введение 3

1. Основы теории массового обслуживания 4

1.1 Понятие случайного процесса 4

1.2 Марковский случайный процесс 5

1.3 Потоки событий 7

1.4 Уравнения Колмогорова для вероятностей состояний. Финальные вероятности состояний 9

1.5 Задачи теории массового обслуживания 13

1.6 Классификация систем массового обслуживания 15

2. Системы массового обслуживания с ожиданием 17

2.1 Одноканальная СМО с ожиданием 17

2.2 Многоканальная СМО с ожиданием 24

3. Замкнутые СМО 33

Решение задачи 41

Заключение 45

Список литературы 46


Введение


В данном курсе мы будем рассматривать различные системы массового обслуживания (СМО) и сети массового обслуживания (СеМО).

Под системой массового обслуживания (СМО) понимают динамическую систему, предназначенную для эффективного обслуживания потока заявок (требований на обслуживание) при ограничениях на ресурсы системы.

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

Совокупность взаимосвязанных СМО называется сетью массового обслуживания (стохастической сетью).

Для начала мы рассмотрим основы теории СМО, затем перейдем к ознакомлению в подробном содержании к СМО с ожиданием и замкнутым СМО. Также в курс включена практическая часть, в которой мы подробно познакомимся с тем, как применить теорию на практике.

1. Основы теории массового обслуживания


Теория массового обслуживания составляет один из разделов теории вероятностей. В этой теории рассматриваются вероятностные задачи и математические модели (до этого нами рассматривались детерминированные математические модели). Напомним, что:

Детерминированная математическая модель отражает поведение объекта (системы, процесса) с позиций полной определенности в настоящем и будущем.

Вероятностная математическая модель учитывает влияние случайных факторов на поведение объекта (системы, процесса) и, следовательно, оценивает будущее с позиций вероятности тех или иных событий.

Т.е. здесь как, например, в теории игр задачи рассматриваются в условияхнеопределенности.

Рассмотрим сначала некоторые понятия, которые характеризуют «стохастическую неопределенность», когда неопределенные факторы, входящие в задачу, представляют собой случайные величины (или случайные функции), вероятностные характеристики которых либо известны, либо могут быть получены из опыта. Такую неопределенность называют еще «благоприятной», «доброкачественной».


1.1 Понятие случайного процесса


Строго говоря, случайные возмущения присущи любому процессу. Проще привести примеры случайного, чем «неслучайного» процесса. Даже, например, процесс хода часов (вроде бы это строгая выверенная работа – «работает как часы») подвержен случайным изменениям (уход вперед, отставание, остановка). Но до тех пор, пока эти возмущения несущественны, мало влияют на интересующие нас параметры, мы можем ими пренебречь и рассматривать процесс как детерминированный, неслучайный.

Пусть имеется некоторая система S (техническое устройство, группа таких устройств, технологическая система – станок, участок, цех, предприятие, отрасль промышленности и т.д.). В системе S протекает случайный процесс, если она с течением времени меняет свое состояние (переходит из одного состояния в другое), причем, заранее неизвестным случайным образом.

Примеры:

1. Система S – технологическая система (участок станков). Станки время от времени выходят из строя и ремонтируются. Процесс, протекающий в этой системе, случаен.

2. Система S – самолет, совершающий рейс на заданной высоте по определенному маршруту. Возмущающие факторы – метеоусловия, ошибки экипажа и т.д., последствия – «болтанка», нарушение графика полетов и т.д.


1.2 Марковский случайный процесс


Случайный процесс, протекающий в системе, называется Марковским, если для любого момента времени t0 вероятностные характеристики процесса в будущем зависят только от его состояния в данный момент t0 и не зависят от того, когда и как система пришла в это состояние.

Пусть в настоящий момент t0 система находится в определенном состоянии S0. Мы знаем характеристики состояния системы в настоящем Система массового обслуживания с ограниченным временем ожиданияи все, что было при t<t0 (предысторию процесса). Можем ли мы предугадать (предсказать) будущее, т.е. что будет при t>t0? В точности – нет, но какие-то вероятностные характеристики процесса в будущем найти можно. Например, вероятность того, что через некоторое время Система массового обслуживания с ограниченным временем ожиданиясистема S окажется в состоянии S1 или останется в состоянии S0 и т.д.

Пример. Система S – группа самолетов, участвующих в воздушном бою. Пусть x – количество «красных» самолетов, y – количество «синих» самолетов. К моменту времени t0 количество сохранившихся (не сбитых) самолетов соответственно – x0, y0. Нас интересует вероятность того, что в момент времени Система массового обслуживания с ограниченным временем ожиданиячисленный перевес будет на стороне «красных». Эта вероятность зависит от того, в каком состоянии находилась система в момент времени t0, а не от того, когда и в какой последовательности погибали сбитые до момента t0 самолеты.

На практике Марковские процессы в чистом виде обычно не встречаются. Но имеются процессы, для которых влиянием «предыстории» можно пренебречь. И при изучении таких процессов можно применять Марковские модели (в теории массового обслуживания рассматриваются и не Марковские системы массового обслуживания, но математический аппарат, их описывающий, гораздо сложнее).

В исследовании операций большое значение имеют Марковские случайные процессы с дискретными состояниями и непрерывным временем.

Процесс называется процессом с дискретным состоянием, если его возможные состояния S1, S2, … можно заранее определить, и переход системы из состояния в состояние происходит «скачком», практически мгновенно.

Процесс называется процессом с непрерывным временем, если моменты возможных переходов из состояния в состояние не фиксированы заранее, а неопределенны, случайны и могут произойти в любой момент.

Далее рассматриваются только процессы с дискретным состоянием и непрерывным временем.

Пример. Технологическая система (участок) S состоит из двух станков, каждый из которых в случайный момент времени может выйти из строя (отказать), после чего мгновенно начинается ремонт узла, тоже продолжающийся заранее неизвестное, случайное время. Возможны следующие состояния системы:

S0 - оба станка исправны;

S1 - первый станок ремонтируется, второй исправен;

S2 - второй станок ремонтируется, первый исправен;

S3 - оба станка ремонтируются.

Переходы системы S из состояния в состояние происходят практически мгновенно, в случайные моменты выхода из строя того или иного станка или окончания ремонта.

При анализе случайных процессов с дискретными состояниями удобно пользоваться геометрической схемой – графом состояний. Вершины графа – состояния системы. Дуги графа – возможные переходы из состояния в состояние. Для нашего примера граф состояний приведен на рис. 1.


Система массового обслуживания с ограниченным временем ожидания

Рис. 1. Граф состояний системы


Примечание. Переход из состояния S0 в S3 на рисунке не обозначен, т.к. предполагается, что станки выходят из строя независимо друг от друга. Вероятностью одновременного выхода из строя обоих станков мы пренебрегаем.


1.3 Потоки событий


Поток событий – последовательность однородных событий, следующих одно за другим в какие-то случайные моменты времени.

В предыдущем примере – это поток отказов и поток восстановлений. Другие примеры: поток вызовов на телефонной станции, поток покупателей в магазине и т.д.

Поток событий можно наглядно изобразить рядом точек на оси времени O t – рис. 2.


Система массового обслуживания с ограниченным временем ожидания

Рис. 2. Изображение потока событий на оси времени


Положение каждой точки случайно, и здесь изображена лишь какая-то одна реализация потока.

Интенсивность потока событий (Система массового обслуживания с ограниченным временем ожидания) – это среднее число событий, приходящееся на единицу времени.

Рассмотрим некоторые свойства (виды) потоков событий.

Поток событий называется стационарным, если его вероятностные характеристики не зависят от времени.

В частности, интенсивность Система массового обслуживания с ограниченным временем ожидания стационарного потока постоянна. Поток событий неизбежно имеет сгущения или разрежения, но они не носят закономерного характера, и среднее число событий, приходящееся на единицу времени, постоянно и от времени не зависит.

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

Поток событий называется ординарным, если события в нем появляются поодиночке, а не группами по нескольку сразу.

Поток событий называется простейшим (или стационарным пуассоновским), если он обладает сразу тремя свойствами:

1) стационарен;

2) ординарен;

3) не имеет последствий.

Простейший поток имеет наиболее простое математическое описание. Он играет среди потоков такую же особую роль, как и закон нормального распределения среди других законов распределения. А именно, при наложении достаточно большого числа независимых, стационарных и ординарных потоков (сравнимых между собой по интенсивности) получается поток, близкий к простейшему.

Для простейшего потока с интенсивностью Система массового обслуживания с ограниченным временем ожидания интервал T между соседними событиями имеет так называемое показательное (экспоненциальное) распределение с плотностью:


Система массового обслуживания с ограниченным временем ожидания


где Система массового обслуживания с ограниченным временем ожидания- параметр показательного закона.

Для случайной величины T, имеющей показательное распределение, математическое ожидание Система массового обслуживания с ограниченным временем ожидания есть величина, обратная параметру, а среднее квадратичное отклонение Система массового обслуживания с ограниченным временем ожидания равно математическому ожиданию:


Система массового обслуживания с ограниченным временем ожидания


1.4 Уравнения Колмогорова для вероятностей состояний. Финальные вероятности состояний


Рассматривая Марковские процессы с дискретными состояниями и непрерывным временем, подразумевается, что все переходы системы S из состояния в состояние происходят под действием простейших потоков событий (потоков вызовов, потоков отказов, потоков восстановлений и т.д.). Если все потоки событий, переводящие систему S из состояния в состояние простейшие, то процесс, протекающий в системе, будет Марковским.

Итак, на систему, находящуюся в состоянии Система массового обслуживания с ограниченным временем ожидания, действует простейший поток событий. Как только появится первое событие этого потока, происходит «перескок» системы из состояния Система массового обслуживания с ограниченным временем ожиданияв состояние Система массового обслуживания с ограниченным временем ожидания(на графе состояний по стрелке Система массового обслуживания с ограниченным временем ожидания).

Для наглядности на графе состояний системы у каждой дуги проставляют интенсивности того потока событий, который переводит систему по данной дуге (стрелке). Система массового обслуживания с ограниченным временем ожидания - интенсивность потока событий, переводящий систему из состояния Система массового обслуживания с ограниченным временем ожидания в Система массового обслуживания с ограниченным временем ожидания. Такой граф называется размеченным. Для нашего примера размеченный граф приведен на рис. 3.


Система массового обслуживания с ограниченным временем ожидания

Рис. 3. Размеченный граф состояний системы


На этом рисунке Система массового обслуживания с ограниченным временем ожидания - интенсивности потока отказов; Система массового обслуживания с ограниченным временем ожидания - интенсивности потока восстановлений.

Предполагаем, что среднее время ремонта станка не зависит от того, ремонтируется ли один станок или оба сразу. Т.е. ремонтом каждого станка занят отдельный специалист.

Пусть система находится в состоянии S0. В состояние S1 ее переводит поток отказов первого станка. Его интенсивность равна:


Система массового обслуживания с ограниченным временем ожидания


где Система массового обслуживания с ограниченным временем ожидания - среднее время безотказной работы первого станка.

Из состояния S1 в S0 систему переводит поток «окончаний ремонтов» первого станка. Его интенсивность равна:


Система массового обслуживания с ограниченным временем ожидания


где Система массового обслуживания с ограниченным временем ожидания - среднее время ремонта первого станка.

Аналогично вычисляются интенсивности потоков событий, переводящих систему по всем дугам графа. Имея в своем распоряжении размеченный граф состояний системы, строится математическая модель данного процесса.

Пусть рассматриваемая система S имеет Система массового обслуживания с ограниченным временем ожидания-возможных состояний Система массового обслуживания с ограниченным временем ожидания. Вероятность Система массового обслуживания с ограниченным временем ожидания-го состояния Система массового обслуживания с ограниченным временем ожидания - это вероятность того, что в момент времени Система массового обслуживания с ограниченным временем ожидания, система будет находиться в состоянии Система массового обслуживания с ограниченным временем ожидания. Очевидно, что для любого момента времени сумма всех вероятностей состояний равна единице:


Система массового обслуживания с ограниченным временем ожидания

Для нахождения всех вероятностей состояний Система массового обслуживания с ограниченным временем ожидания как функций времени составляются и решаются уравнения Колмогорова – особого вида уравнения, в которых неизвестными функциями являются вероятности состояний. Правило составления этих уравнений приведем здесь без доказательств. Но прежде, чем его приводить, объясним понятие финальной вероятности состояния.

Что будет происходить с вероятностями состояний при Система массового обслуживания с ограниченным временем ожидания? Будут ли Система массового обслуживания с ограниченным временем ожидания стремиться к каким-либо пределам? Если эти пределы существуют и не зависят от начального состояния системы, то они называются финальными вероятностями состояний.


Система массового обслуживания с ограниченным временем ожидания


где Система массового обслуживания с ограниченным временем ожидания - конечное число состояний системы.

Финальные вероятности состояний – это уже не переменные величины (функции времени), а постоянные числа. Очевидно, что:


Система массового обслуживания с ограниченным временем ожидания


Финальная вероятность состояния Система массового обслуживания с ограниченным временем ожидания – это по–существу среднее относительное время пребывания системы в этом состоянии.

Например, система S имеет три состояния S1, S2 и S3. Их финальные вероятности равны соответственно 0,2; 0,3 и 0,5. Это значит, что система в предельном стационарном состоянии в среднем 2/10 времени проводит в состоянии S1, 3/10 – в состоянии S2 и 5/10 – в состоянии S3.

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

Пользуясь этим правилом, напишем систему уравнений для нашего примера:


Система массового обслуживания с ограниченным временем ожидания.


Эту систему четырех уравнений с четырьмя неизвестными Система массового обслуживания с ограниченным временем ожидания, казалось бы, можно вполне решить. Но эти уравнения однородны (не имеют свободного члена), и, значит, определяют неизвестные только с точностью до произвольного множителя. Однако можно воспользоваться нормировочным условием: Система массового обслуживания с ограниченным временем ожидания и с его помощью решить систему. При этом одно (любое) из уравнений можно отбросить (оно вытекает как следствие из остальных).

Продолжение примера. Пусть значения интенсивностей потоков равны: Система массового обслуживания с ограниченным временем ожидания.

Четвертое уравнение отбрасываем, добавляя вместо него нормировочное условие:


Система массового обслуживания с ограниченным временем ожидания.


Система массового обслуживания с ограниченным временем ожидания.

Т.е. в предельном, стационарном режиме система S в среднем 40% времени будет проводить в состоянии S0 (оба станка исправны), 20% - в состоянии S1 (первый станок ремонтируется, второй работает), 27% - в состоянии S2 (второй станок ремонтируется, первый работает), 13% - в состоянии S3 (оба станка ремонтируются). Знание этих финальных вероятностей может помочь оценить среднюю эффективность работы системы и загрузку ремонтных органов.

Пусть система S в состоянии S0 (полностью исправна) приносит в единицу времени доход 8 условных единиц, в состоянии S1 – доход 3 условные единицы, в состоянии S2 – доход 5 условных единиц, в состоянии S3 – не приносит дохода. Тогда в предельном, стационарном режиме средний доход в единицу времени будет равен: Система массового обслуживания с ограниченным временем ожидания условных единиц.

Станок 1 ремонтируется долю времени, равную: Система массового обслуживания с ограниченным временем ожидания. Станок 2 ремонтируется долю времени, равную: Система массового обслуживания с ограниченным временем ожидания. Возникает задача оптимизации. Пусть мы можем уменьшить среднее время ремонта первого или второго станка (или обоих), но это нам обойдется в определенную сумму. Спрашивается, окупит ли увеличение дохода, связанное с ускорением ремонта, повышенные расходы на ремонт? Нужно будет решить систему четырех уравнений с четырьмя неизвестными.


1.5 Задачи теории массового обслуживания


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

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

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

Процесс работы СМО – случайный процесс с дискретными состояниями и непрерывным временем. Состояние СМО меняется скачком в моменты появления каких-то событий (прихода новой заявки, окончания обслуживания, момента, когда заявка, которой надоело ждать, покидает очередь).

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

Математический анализ работы СМО очень облегчается, если процесс этой работы Марковский, т.е. потоки событий, переводящие систему из состояния в состояние – простейшие. Иначе математическое описание процесса очень усложняется и его редко удается довести до конкретных аналитических зависимостей. На практике не Марковские процессы с приближением приводятся к Марковским. Приведенный далее математический аппарат описывает Марковские процессы.


1.6 Классификация систем массового обслуживания


Первое деление (по наличию очередей):

СМО с отказами;

СМО с очередью.

В СМО с отказами заявка, поступившая в момент, когда все каналы заняты, получает отказ, покидает СМО и в дальнейшем не обслуживается.

В СМО с очередью заявка, пришедшая в момент, когда все каналы заняты, не уходит, а становится в очередь и ожидает возможности быть обслуженной.

СМО с очередями подразделяются на разные виды в зависимости от того, как организована очередь – ограничена или не ограничена. Ограничения могут касаться как длины очереди, так и времени ожидания, «дисциплины обслуживания».

Итак, например, рассматриваются следующие СМО:

СМО с нетерпеливыми заявками (длина очереди и время обслуживания ограничено);

СМО с обслуживанием с приоритетом, т.е. некоторые заявки обслуживаются вне очереди и т.д.

Кроме этого СМО делятся на открытые СМО и замкнутые СМО.

В открытой СМО характеристики потока заявок не зависят от того, в каком состоянии сама СМО (сколько каналов занято). В замкнутой СМО – зависят. Например, если один рабочий обслуживает группу станков, время от времени требующих наладки, то интенсивность потока «требований» со стороны станков зависит от того, сколько их уже исправно и ждет наладки.

Классификация СМО далеко не ограничивается приведенными разновидностями, но этого достаточно.


2. Системы массового обслуживания с ожиданием


2.1 Одноканальная СМО с ожиданием


Рассмотрим простейшую СМО с ожиданием — одноканальную систему (n - 1), в которую поступает поток заявок с интенсивностью Система массового обслуживания с ограниченным временем ожидания; интенсивность обслуживания Система массового обслуживания с ограниченным временем ожидания (т.е. в среднем непрерывно занятый канал будет выдавать Система массового обслуживания с ограниченным временем ожидания обслуженных заявок в единицу (времени). Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания.

Система с ограниченной длиной очереди. Предположим сначала, что количество мест в очереди ограничено числом m, т.е. если заявка пришла в момент, когда в очереди уже стоят m-заявок, она покидает систему не обслуженной. В дальнейшем, устремив m к бесконечности, мы получим характеристики одноканальной СМО без ограничений длины очереди.

Будем нумеровать состояния СМО по числу заявок, находящихся в системе (как обслуживаемых, так и ожидающих обслуживания):

Система массового обслуживания с ограниченным временем ожидания — канал свободен;

Система массового обслуживания с ограниченным временем ожидания — канал занят, очереди нет;

Система массового обслуживания с ограниченным временем ожидания — канал занят, одна заявка стоит в очереди;

Система массового обслуживания с ограниченным временем ожидания — канал занят, k-1 заявок стоят в очереди;

Система массового обслуживания с ограниченным временем ожидания — канал занят, т-заявок стоят в очереди.

ГСП показан на рис. 4. Все интенсивности потоков событий, переводящих в систему по стрелкам слева направо, равны Система массового обслуживания с ограниченным временем ожидания, а справа налево — Система массового обслуживания с ограниченным временем ожидания. Действительно, по стрелкам слева направо систему переводит поток заявок (как только придет заявка, система переходит в следующее состояние), справа же налево — поток «освобождений» занятого канала, имеющий интенсивность Система массового обслуживания с ограниченным временем ожидания (как только будет обслужена очередная заявка, канал либо освободится, либо уменьшится число заявок в очереди).

Система массового обслуживания с ограниченным временем ожидания

Рис. 4. Одноканальная СМО с ожиданием


Изображенная на рис. 4 схема представляет собой схему размножения и гибели. Напишем выражения для предельных вероятностей состояний:


Система массового обслуживания с ограниченным временем ожидания (5)


или с использованием: Система массового обслуживания с ограниченным временем ожидания:


Система массового обслуживания с ограниченным временем ожидания (6)


Последняя строка в (6) содержит геометрическую прогрессию с первым членом 1 и знаменателем р, откуда получаем:


Система массового обслуживания с ограниченным временем ожидания (7)


в связи с чем предельные вероятности принимают вид:

Система массового обслуживания с ограниченным временем ожидания(8).


Выражение (7) справедливо только при Система массового обслуживания с ограниченным временем ожидания< 1 (при Система массового обслуживания с ограниченным временем ожидания= 1 она дает неопределенность вида 0/0). Сумма геометрической прогрессии со знаменателем Система массового обслуживания с ограниченным временем ожидания= 1 равна m+2, и в этом случае:


Система массового обслуживания с ограниченным временем ожидания.


Определим характеристики СМО: вероятность отказа Система массового обслуживания с ограниченным временем ожидания, относительную пропускную способность q, абсолютную пропускную способность А, среднюю длину очереди Система массового обслуживания с ограниченным временем ожидания, среднее число заявок, связанных с системой Система массового обслуживания с ограниченным временем ожидания, среднее время ожидания в очереди Система массового обслуживания с ограниченным временем ожидания, среднее время пребывания заявки в СМО Система массового обслуживания с ограниченным временем ожидания.

Вероятность отказа. Очевидно, заявка получает отказ только в случае, когда канал занят и все т-мест в очереди тоже:


Система массового обслуживания с ограниченным временем ожидания (9).


Относительная пропускная способность:


Система массового обслуживания с ограниченным временем ожидания (10).

Абсолютная пропускная способность:


Система массового обслуживания с ограниченным временем ожидания.


Средняя длина очереди. Найдем среднее число Система массового обслуживания с ограниченным временем ожидания-заявок, находящихся в очереди, как математическое ожидание дискретной случайной величины R—числа заявок, находящихся в очереди:


Система массового обслуживания с ограниченным временем ожидания.


С вероятностьюСистема массового обслуживания с ограниченным временем ожиданияв очереди стоит одна заявка, с вероятностьюСистема массового обслуживания с ограниченным временем ожидания— две заявки, вообще с вероятностьюСистема массового обслуживания с ограниченным временем ожиданияв очереди стоят k-1 заявок, и т.д., откуда:


Система массового обслуживания с ограниченным временем ожидания (11).


Поскольку Система массового обслуживания с ограниченным временем ожидания, сумму в (11) можно трактовать как производную по Система массового обслуживания с ограниченным временем ожидания от суммы геометрической прогрессии:


Система массового обслуживания с ограниченным временем ожидания.


Подставляя данное выражение в (11) и используя Система массового обслуживания с ограниченным временем ожидания из (8), окончательно получаем:


Система массового обслуживания с ограниченным временем ожидания(12).

Среднее число заявок, находящихся в системе. Получим далее формулу для среднего числа Система массового обслуживания с ограниченным временем ожидания-заявок, связанных с системой (как стоящих в очереди, так и находящихся на обслуживании). Поскольку Система массового обслуживания с ограниченным временем ожидания, где Система массового обслуживания с ограниченным временем ожидания — среднее число заявок, находящихся под обслуживанием, а k известно, то остается определить Система массового обслуживания с ограниченным временем ожидания. Поскольку канал один, число обслуживаемых заявок может равняться 0 (с вероятностью Система массового обслуживания с ограниченным временем ожидания) или 1 (с вероятностью 1 - Система массового обслуживания с ограниченным временем ожидания), откуда:


Система массового обслуживания с ограниченным временем ожидания.


и среднее число заявок, связанных с СМО, равно:


Система массового обслуживания с ограниченным временем ожидания(13).


Среднее время ожидания заявки в очереди. Обозначим его Система массового обслуживания с ограниченным временем ожидания; если заявка приходит в систему в какой-то момент времени, то с вероятностью Система массового обслуживания с ограниченным временем ожидания канал обслуживания не будет занят, и ей не придется стоять в очереди (время ожидания равно нулю). С вероятностью Система массового обслуживания с ограниченным временем ожидания она придет в систему во время обслуживания какой-то заявки, но перед ней не будет очереди, и заявка будет ждать начала своего обслуживания в течение времени Система массового обслуживания с ограниченным временем ожидания (среднее время обслуживания одной заявки). С вероятностью Система массового обслуживания с ограниченным временем ожидания в очереди перед рассматриваемой заявкой будет стоять еще одна, и время ожидания в среднем будет равно Система массового обслуживания с ограниченным временем ожидания, и т.д.

Если же k=m+1, т.е. когда вновь приходящая заявка застает канал обслуживания занятым и m-заявок в очереди (вероятность этого Система массового обслуживания с ограниченным временем ожидания), то в этом случае заявка не становится в очередь (и не обслуживается), поэтому время ожидания равно нулю. Среднее время ожидания будет равно:


Система массового обслуживания с ограниченным временем ожидания,


если подставить сюда выражения для вероятностей (8), получим:


Система массового обслуживания с ограниченным временем ожидания(14).


Здесь использованы соотношения (11), (12) (производная геометрической прогрессии), а также Система массового обслуживания с ограниченным временем ожидания из (8). Сравнивая это выражение с (12), замечаем, что иначе говоря, среднее время ожидания равно среднему числу заявок в очереди, деленному на интенсивность потока заявок.


Система массового обслуживания с ограниченным временем ожидания (15).


Среднее время пребывания заявки в системе. Обозначим Система массового обслуживания с ограниченным временем ожидания - матожидание случайной величины — время пребывания заявки в СМО, которое складывается из среднего времени ожидания в очереди Система массового обслуживания с ограниченным временем ожидания и среднего времени обслуживания Система массового обслуживания с ограниченным временем ожидания. Если загрузка системы составляет 100%, очевидно, Система массового обслуживания с ограниченным временем ожидания, в противном же случае:


Система массового обслуживания с ограниченным временем ожидания.


Отсюда:


Система массового обслуживания с ограниченным временем ожидания.

Пример 1. Автозаправочная станция (АЗС) представляет собой СМО с одним каналом обслуживания (одной колонкой).

Площадка при станции допускает пребывание в очереди на заправку не более трех машин одновременно (m = 3). Если в очереди уже находятся три машины, очередная машина, прибывшая к станции, в очередь не становится. Поток машин, прибывающих для заправки, имеет интенсивность Система массового обслуживания с ограниченным временем ожидания=1 (машина в минуту). Процесс заправки продолжается в среднем 1,25 мин.

Определить:

вероятность отказа;

относительную и абсолютную пропускную способности АЗС;

среднее число машин, ожидающих заправки;

среднее число машин, находящихся на АЗС (включая обслуживаемую);

среднее время ожидания машины в очереди;

среднее время пребывания машины на АЗС (включая обслуживание).

Иначе говоря, среднее время ожидания равно среднему числу заявок в очереди, деленному на интенсивность потока заявок.

Находим вначале приведенную интенсивность потока заявок: Система массового обслуживания с ограниченным временем ожидания=1/1,25=0,8; Система массового обслуживания с ограниченным временем ожидания=1/0,8=1,25.

По формулам (8):


Система массового обслуживания с ограниченным временем ожидания


Вероятность отказа Система массового обслуживания с ограниченным временем ожидания0,297.

Относительная пропускная способность СМО: q=1-Система массового обслуживания с ограниченным временем ожидания=0,703.

Абсолютная пропускная способность СМО: A=Система массового обслуживания с ограниченным временем ожидания=0,703 машины в мин.

Среднее число машин в очереди находим по формуле (12):

Система массового обслуживания с ограниченным временем ожидания,


т.е. среднее число машин, ожидающих в очереди на заправку, равно 1,56.

Прибавляя к этой величине среднее число машин, находящихся под обслуживанием:


Система массового обслуживания с ограниченным временем ожидания


получаем среднее число машин, связанных с АЗС.

Среднее время ожидания машины в очереди по формуле (15):


Система массового обслуживания с ограниченным временем ожидания


Прибавляя к этой величине Система массового обслуживания с ограниченным временем ожидания, получим среднее время, которое машина проводит на АЗС:


Система массового обслуживания с ограниченным временем ожидания


Системы с неограниченным ожиданием. В таких системах значение т не ограничено и, следовательно, основные характеристики могут быть получены путем предельного перехода Система массового обслуживания с ограниченным временем ожидания в ранее полученных выражениях (5), (6) и т.п.

Заметим, что при этом знаменатель в последней формуле (6) представляет собой сумму бесконечного числа членов геометрической прогрессии. Эта сумма сходится, когда прогрессия бесконечно убывающая, т.е. при Система массового обслуживания с ограниченным временем ожидания<1.

Может быть доказано, что Система массового обслуживания с ограниченным временем ожидания<1 есть условие, при котором в СМО с ожиданием существует предельный установившийся режим, иначе такого режима не существует, и очередь при Система массового обслуживания с ограниченным временем ожидания будет неограниченно возрастать. Поэтому в дальнейшем здесь предполагается, что Система массового обслуживания с ограниченным временем ожидания<1.

ЕслиСистема массового обслуживания с ограниченным временем ожидания, то соотношения (8) принимают вид:


Система массового обслуживания с ограниченным временем ожидания (16).


При отсутствии ограничений по длине очереди каждая заявка, пришедшая в систему, будет обслужена, поэтому q=1, Система массового обслуживания с ограниченным временем ожидания.

Среднее число заявок в очереди получим из (12) при Система массового обслуживания с ограниченным временем ожидания:


Система массового обслуживания с ограниченным временем ожидания.


Среднее число заявок в системе по формуле (13) при Система массового обслуживания с ограниченным временем ожидания:


Система массового обслуживания с ограниченным временем ожидания.


Среднее время ожиданияСистема массового обслуживания с ограниченным временем ожиданияполучим из формулы (14) приСистема массового обслуживания с ограниченным временем ожидания:


Система массового обслуживания с ограниченным временем ожидания.


Наконец, среднее время пребывания заявки в СМО есть:

Система массового обслуживания с ограниченным временем ожидания.


2.2 Многоканальная СМО с ожиданием


Система с ограниченной длиной очереди. Рассмотрим Система массового обслуживания с ограниченным временем ожиданияканальную СМО с ожиданием, на которую поступает поток заявок с интенсивностью Система массового обслуживания с ограниченным временем ожидания; интенсивность обслуживания (для одного канала) Система массового обслуживания с ограниченным временем ожидания; число мест в очереди Система массового обслуживания с ограниченным временем ожидания.

Состояния системы нумеруются по числу заявок, связанных системой:

нет очереди:

Система массового обслуживания с ограниченным временем ожидания — все каналы свободны;

Система массового обслуживания с ограниченным временем ожидания — занят один канал, остальные свободны;

Система массового обслуживания с ограниченным временем ожидания — заняты Система массового обслуживания с ограниченным временем ожидания-каналов, остальные нет;

Система массового обслуживания с ограниченным временем ожидания— заняты все Система массового обслуживания с ограниченным временем ожидания-каналов, свободных нет;

есть очередь:

Система массового обслуживания с ограниченным временем ожидания — заняты все n-каналов; одна заявка стоит в очереди;

Система массового обслуживания с ограниченным временем ожидания — заняты все n-каналов, r-заявок в очереди;

Система массового обслуживания с ограниченным временем ожидания — заняты все n-каналов, r-заявок в очереди.

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


Система массового обслуживания с ограниченным временем ожидания

Рис. 17. Многоканальная СМО с ожиданием

Система массового обслуживания с ограниченным временем ожидания


Граф типичен для процессов размножения и гибели, для которой решение ранее получено. Напишем выражения для предельных вероятностей состояний, используя обозначение Система массового обслуживания с ограниченным временем ожидания: (здесь используется выражение для суммы геометрической прогрессии со знаменателем Система массового обслуживания с ограниченным временем ожидания).

Таким образом, все вероятности состояний найдены.

Определим характеристики эффективности системы.

Вероятность отказа. Поступившая заявка получает отказ, если заняты все n-каналов и все m-мест в очереди:


Система массового обслуживания с ограниченным временем ожидания (18)


Относительная пропускная способность дополняет вероятность отказа до единицы:


Система массового обслуживания с ограниченным временем ожидания


Абсолютная пропускная способность СМО:

Система массового обслуживания с ограниченным временем ожидания (19)


Среднее число занятых каналов. Для СМО с отказами оно совпадало со средним числом заявок, находящихся в системе. Для СМО с очередью среднее число занятых каналов не совпадает со средним числом заявок, находящихся в системе: последняя величина отличается от первой на среднее число заявок, находящихся в очереди.

Обозначим среднее число занятых каналов Система массового обслуживания с ограниченным временем ожидания. Каждый занятый канал обслуживает в среднем Система массового обслуживания с ограниченным временем ожидания-заявок в единицу времени, а СМО в целом обслуживает в среднем А-заявок в единицу времени. Разделив одно на другое, получим:


Система массового обслуживания с ограниченным временем ожидания.


Среднее число заявок в очереди можно вычислить непосредственно как математическое ожидание дискретной случайной величины:


Система массового обслуживания с ограниченным временем ожидания (20)


где Система массового обслуживания с ограниченным временем ожидания.

Здесь опять (выражение в скобках) встречается производная суммы геометрической прогрессии (см. выше (11), (12) — (14)), используя соотношение для нее, получаем:


Система массового обслуживания с ограниченным временем ожидания


Среднее число заявок в системе:


Система массового обслуживания с ограниченным временем ожидания


Среднее время ожидания заявки в очереди. Рассмотрим ряд ситуаций, различающихся тем, в каком состоянии застанет систему вновь пришедшая заявка и сколько времени ей придется ждать обслуживания.

Если заявка застанет не все каналы занятыми, ей вообще не придется ждать (соответствующие члены в математическом ожидании равны нулю). Если заявка придет в момент, когда заняты все n-каналов, а очереди нет, ей придется ждать в среднем время, равное Система массового обслуживания с ограниченным временем ожидания (потому что «поток освобождений» Система массового обслуживания с ограниченным временем ожидания-каналов имеет интенсивность Система массового обслуживания с ограниченным временем ожидания). Если заявка застанет все каналы занятыми и одну заявку перед собой в очереди, ей придется в среднем ждать в течение времени Система массового обслуживания с ограниченным временем ожидания (по Система массового обслуживания с ограниченным временем ожидания на каждую впереди стоящую заявку) и т. д. Если заявка застанет в очереди Система массового обслуживания с ограниченным временем ожидания-заявок, ей придется ждать в среднем в течение времени Система массового обслуживания с ограниченным временем ожидания. Если вновь пришедшая заявка застанет в очереди уже m-заявок, то она вообще не будет ждать (но и не будет обслужена). Среднее время ожидания найдем, умножая каждое из этих значений на соответствующие вероятности:


Система массового обслуживания с ограниченным временем ожидания (21)


Так же, как и в случае одноканальной СМО с ожиданием, отметим, что это выражение отличается от выражения для средней длины очереди (20) только множителем Система массового обслуживания с ограниченным временем ожидания, т. е.


Система массового обслуживания с ограниченным временем ожидания.


Среднее время пребывания заявки в системе, так же, как и для одноканальной СМО, отличается от среднего времени ожидания на среднее время обслуживания, умноженное на относительную пропускную способность:


Система массового обслуживания с ограниченным временем ожидания.


Системы с неограниченной длиной очереди. Мы рассмотрели Система массового обслуживания с ограниченным временем ожиданияканальную СМО с ожиданием, когда в очереди одновременно могут находиться не более m-заявок.

Так же, как и ранее, при анализе систем без ограничений необходимо рассмотреть полученные соотношения при Система массового обслуживания с ограниченным временем ожидания.

Вероятности состояний получим из формул предельным переходом (при Система массового обслуживания с ограниченным временем ожидания). Заметим, что сумма соответствующей геометрической прогрессии сходится при Система массового обслуживания с ограниченным временем ожидания и расходится при Система массового обслуживания с ограниченным временем ожидания>1. Допустив, что Система массового обслуживания с ограниченным временем ожидания<1 и устремив в формулах величину m к бесконечности, получим выражения для предельных вероятностей состояний:


Система массового обслуживания с ограниченным временем ожидания (22)


Вероятность отказа, относительная и абсолютная пропускная способность. Так как каждая заявка рано или поздно будет обслужена, то характеристики пропускной способности СМО составят:


Система массового обслуживания с ограниченным временем ожидания


Среднее число заявок в очереди получим при Система массового обслуживания с ограниченным временем ожидания из (20):


Система массового обслуживания с ограниченным временем ожидания,


а среднее время ожидания — из (21):


Система массового обслуживания с ограниченным временем ожидания.


Среднее число занятых каналов Система массового обслуживания с ограниченным временем ожидания, как и ранее, определяется через абсолютную пропускную способность:


Система массового обслуживания с ограниченным временем ожидания.

Среднее число заявок, связанных с СМО, определяется как среднее число заявок в очереди плюс среднее число заявок, находящихся под обслуживанием (среднее число занятых каналов):


Система массового обслуживания с ограниченным временем ожидания.


Пример 2. Автозаправочная станция с двумя колонками (n = 2) обслуживает поток машин с интенсивностью Система массового обслуживания с ограниченным временем ожидания=0,8 (машин в минуту). Среднее время обслуживания одной машины:


Система массового обслуживания с ограниченным временем ожидания


В данном районе нет другой АЗС, так что очередь машин перед АЗС может расти практически неограниченно. Найти характеристики СМО.

Имеем:


Система массового обслуживания с ограниченным временем ожидания


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


Система массового обслуживания с ограниченным временем ожидания

Система массового обслуживания с ограниченным временем ожидания и т. д.


Среднее число занятых каналов найдем, разделив абсолютную пропускную способность СМО А=Система массового обслуживания с ограниченным временем ожидания=0,8 на интенсивность обслуживания Система массового обслуживания с ограниченным временем ожидания=0,5:


Система массового обслуживания с ограниченным временем ожидания


Вероятность отсутствия очереди у АЗС будет:


Система массового обслуживания с ограниченным временем ожидания


Среднее число машин в очереди:


Система массового обслуживания с ограниченным временем ожидания


Среднее число машин на АЗС:


Система массового обслуживания с ограниченным временем ожидания

Среднее время ожидания в очереди:

Система массового обслуживания с ограниченным временем ожидания


Среднее время пребывания машины на АЗС:


Система массового обслуживания с ограниченным временем ожидания


СМО с ограниченным временем ожидания. Ранее рассматривались системы с ожиданием, ограниченным только длиной очереди (числом m-заявок, одновременно находящихся в очереди). В такой СМО заявка, разраставшая в очередь, не покидает ее, пока не дождется обслуживания. На практике встречаются СМО другого типа, в которых заявка, подождав некоторое время, может уйти из очереди (так называемые «нетерпеливые» заявки).

Рассмотрим СМО подобного типа, предполагая, что ограничение времени ожидания является случайной величиной.

Предположим, что имеется n-канальная СМО с ожиданием, в которой число мест в очереди не ограничено, но время пребывания заявки в очереди является некоторой случайной величиной со средним значениемСистема массового обслуживания с ограниченным временем ожидания, таким образом, на каждую заявку, стоящую в очереди, действует своего рода пуассоновский «поток уходов» с интенсивностью:


Система массового обслуживания с ограниченным временем ожидания


Если этот поток пуассоновский, то процесс, протекающий в СМО, будет марковским. Найдем для него вероятности состояний. Нумерация состояний системы связывается с числом заявок в системе — как обслуживаемых, так и стоящих в очереди:

нет очереди:

Система массового обслуживания с ограниченным временем ожидания — все каналы свободны;

Система массового обслуживания с ограниченным временем ожидания — занят один канал;

Система массового обслуживания с ограниченным временем ожидания — заняты два канала;

Система массового обслуживания с ограниченным временем ожидания — заняты все n-каналов;

есть очередь:

Система массового обслуживания с ограниченным временем ожидания — заняты все n-каналов, одна заявка стоит в очереди;

Система массового обслуживания с ограниченным временем ожидания — заняты все n-каналов, r-заявок стоят в очереди и т. д.

Граф состояний и переходов системы показан на рис. 23.

Система массового обслуживания с ограниченным временем ожидания

Рис. 23. СМО с ограниченным временем ожидания


Разметим этот граф, как и раньше; у всех стрелок, ведущих слева направо, будет стоять интенсивность потока заявок Система массового обслуживания с ограниченным временем ожидания. Для состояний без очереди у стрелок, ведущих из них справа налево, будет, как и раньше, стоять суммарная интенсивность потока обслуживании всех занятых каналов. Что касается состояний с очередью, то у стрелок, ведущих из них справа налево, будет стоять суммарная интенсивность потока обслуживания всех n-каналов Система массового обслуживания с ограниченным временем ожиданияплюс соответствующая интенсивность потока уходов из очереди. Если в очереди стоят r-заявок, то суммарная интенсивность потока уходов будет равна Система массового обслуживания с ограниченным временем ожидания.

Как видно из графа, имеет место схема размножения и гибели; применяя общие выражения для предельных вероятностей состояний в этой схеме (используя сокращенные обозначения Система массового обслуживания с ограниченным временем ожидания, запишем:


Система массового обслуживания с ограниченным временем ожидания (24)


Отметим некоторые особенности СМО с ограниченным ожиданием сравнительно с ранее рассмотренными СМО с «терпеливыми» заявками.

Если длина очереди не ограничена и заявки «терпеливы» (не уходят из очереди), то стационарный предельный режим существует только в случае Система массового обслуживания с ограниченным временем ожидания (при Система массового обслуживания с ограниченным временем ожидания соответствующая бесконечная геометрическая прогрессия расходится, что физически соответствует неограниченному росту очереди при Система массового обслуживания с ограниченным временем ожидания).

Напротив, в СМО с «нетерпеливыми» заявками, уходящими рано или поздно из очереди, установившийся режим обслуживания при Система массового обслуживания с ограниченным временем ожидания достигается всегда, независимо от приведенной интенсивности потока заявок Система массового обслуживания с ограниченным временем ожидания. Это следует из того, что ряд для Система массового обслуживания с ограниченным временем ожидания в знаменателе формулы (24) сходится при любых положительных значениях Система массового обслуживания с ограниченным временем ожидания и Система массового обслуживания с ограниченным временем ожидания.

Для СМО с «нетерпеливыми» заявками понятие «вероятность отказа» не имеет смысла — каждая заявка становится в очередь, но может и не дождаться обслуживания, уйдя раньше времени.

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


Система массового обслуживания с ограниченным временем ожидания (25)


На каждую из этих заявок действует «поток уходов» с интенсивностью Система массового обслуживания с ограниченным временем ожидания. Значит, из среднего числа Система массового обслуживания с ограниченным временем ожидания-заявок в очереди в среднем будет уходить, не дождавшись обслуживания, Система массового обслуживания с ограниченным временем ожидания-заявок в единицу времени и всего в единицу времени в среднем будет обслуживаться Система массового обслуживания с ограниченным временем ожидания-заявок. Относительная пропускная способность СМО будет составлять:


Система массового обслуживания с ограниченным временем ожидания

Среднее число занятых каналов Система массового обслуживания с ограниченным временем ожидания по-прежнему получаем, деля абсолютную пропускную способность А на Система массового обслуживания с ограниченным временем ожидания:


Система массового обслуживания с ограниченным временем ожидания (26)


Среднее число заявок в очереди. Соотношение (26) позволяет вычислить среднее число заявок в очереди Система массового обслуживания с ограниченным временем ожидания, не суммируя бесконечного ряда (25). Из (26) получаем:


Система массового обслуживания с ограниченным временем ожидания,


а входящее в эту формулу среднее число занятых каналов можно найти как математическое ожидание случайной величины Z, принимающей значения 0, 1, 2,..., n с вероятностями Система массового обслуживания с ограниченным временем ожидания,Система массового обслуживания с ограниченным временем ожидания:


Система массового обслуживания с ограниченным временем ожидания.


В заключение заметим, что если в формулах (24) перейти к пределу при Система массового обслуживания с ограниченным временем ожидания (или, что то же, при Система массового обслуживания с ограниченным временем ожидания), то при Система массового обслуживания с ограниченным временем ожидания получатся формулы (22), т. е. «нетерпеливые» заявки станут «терпеливыми».


3. Замкнутые СМО


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

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

Пусть n - число каналов обслуживания, s - число потенциальных заявок, n<s, Система массового обслуживания с ограниченным временем ожидания - интенсивность потока заявок каждого потенциального требования, μ - интенсивность обслуживания:

ρ=Система массового обслуживания с ограниченным временем ожидания.

Вероятность простоя системы определяется формулой


Р0=Система массового обслуживания с ограниченным временем ожидания.


Финальные вероятности состояний системы:


Pk=Система массового обслуживания с ограниченным временем ожидания при k<n, Pk=Система массового обслуживания с ограниченным временем ожидания при Система массового обслуживания с ограниченным временем ожидания.


Через эти вероятности выражается среднее число занятых каналов


Система массового обслуживания с ограниченным временем ожидания=P1+2P2+…+n(Pn+Pn+1+…+Ps) или

Система массового обслуживания с ограниченным временем ожидания=P1+2P2+…+(n-1)Pn-1+n(1-P0-P1-…-Pn-1).


Через Система массового обслуживания с ограниченным временем ожидания находим абсолютную пропускную способность системы:


A=Система массового обслуживания с ограниченным временем ожиданияСистема массового обслуживания с ограниченным временем ожидания,


а также среднее число заявок в системе


М=s-Система массового обслуживания с ограниченным временем ожидания=s-Система массового обслуживания с ограниченным временем ожидания.


Пример 1. На вход трехканальной СМО с отказами поступает поток заявок с интенсивностью Система массового обслуживания с ограниченным временем ожидания =4 заявки в минуту, время обслуживания заявки одним каналом tобсл=1/μ =0,5 мин. Выгодно ли с точки зрения пропускной способности СМО заставить все три канала обслуживать заявки сразу, причем среднее время обслуживания уменьшается втрое? Как это скажется на среднем времени пребывания заявки в СМО?

Решение. Находим вероятность простоя трехканальной СМО по формуле


Система массового обслуживания с ограниченным временем ожидания

ρ =Система массового обслуживания с ограниченным временем ожидания/μ =4/2=2, n=3,

Р0=Система массового обслуживания с ограниченным временем ожидания=Система массового обслуживания с ограниченным временем ожидания=Система массового обслуживания с ограниченным временем ожиданияСистема массового обслуживания с ограниченным временем ожидания0,158.


Вероятность отказа определяем по формуле:

Ротк=Рn=Система массового обслуживания с ограниченным временем ожидания= Система массового обслуживания с ограниченным временем ожидания

Pотк=Система массового обслуживания с ограниченным временем ожиданияСистема массового обслуживания с ограниченным временем ожидания0,21.


Относительная пропускная способность системы:


Робсл=1-РоткСистема массового обслуживания с ограниченным временем ожидания1-0,21=0,79.


Абсолютная пропускная способность системы:


А=Система массового обслуживания с ограниченным временем ожиданияРобслСистема массового обслуживания с ограниченным временем ожидания3,16.


Среднее число занятых каналов определяем по формуле:


Система массового обслуживания с ограниченным временем ожидания


Система массового обслуживания с ограниченным временем ожидания1,58, доля каналов, занятых обслуживанием,


q=Система массового обслуживания с ограниченным временем ожиданияСистема массового обслуживания с ограниченным временем ожидания0,53.


Cреднее время пребывания заявки в СМО находим как вероятность того, что заявка принимается к обслуживанию, умноженную на среднее время обслуживания: tСМОСистема массового обслуживания с ограниченным временем ожидания0,395 мин.

Объединяя все три канала в один, получаем одноканальную систему с параметрами μ=6, ρ=2/3. Для одноканальной системы вероятность простоя:

Р0=Система массового обслуживания с ограниченным временем ожидания=Система массового обслуживания с ограниченным временем ожидания=0,6,

вероятность отказа:


Ротк=ρ Р0=Система массового обслуживания с ограниченным временем ожидания=0,4,


относительная пропускная способность:


Робсл=1-Ротк=0,6,


абсолютная пропускная способность:


А=Система массового обслуживания с ограниченным временем ожиданияРобсл=2,4.

Среднее время пребывания заявки в СМО:


tСМО=РобслСистема массового обслуживания с ограниченным временем ожидания=Система массового обслуживания с ограниченным временем ожидания=0,1 мин.


В результате объединения каналов в один пропускная способность системы снизилась, так как увеличилась вероятность отказа. Среднее время пребывания заявки в системе уменьшилось.

Пример 2. На вход трехканальной СМО с неограниченной очередью поступает поток заявок с интенсивностью Система массового обслуживания с ограниченным временем ожидания=4 заявки в час, среднее время обслуживания одной заявки t=1/μ=0,5 ч. Найти показатели эффективности работы системы.

Для рассматриваемой системы n=3, Система массового обслуживания с ограниченным временем ожидания=4, μ=1/0,5=2, ρ=Система массового обслуживания с ограниченным временем ожидания/μ=2, ρ/n=2/3<1. Определяем вероятность простоя по формуле:


РСистема массового обслуживания с ограниченным временем ожидания=Система массового обслуживания с ограниченным временем ожидания.

P0= Система массового обслуживания с ограниченным временем ожидания=1/9.


Среднее число заявок в очереди находим по формуле:


L=Система массового обслуживания с ограниченным временем ожидания.

L=Система массового обслуживания с ограниченным временем ожидания=Система массового обслуживания с ограниченным временем ожидания.


Среднее время ожидания заявки в очереди считаем по формуле:

t=Система массового обслуживания с ограниченным временем ожидания.

t=Система массового обслуживания с ограниченным временем ожидания=Система массового обслуживания с ограниченным временем ожиданияСистема массового обслуживания с ограниченным временем ожидания0,22 ч.

Среднее время пребывания заявки в системе:


Т=t+Система массового обслуживания с ограниченным временем ожиданияСистема массового обслуживания с ограниченным временем ожидания0,22+0,5=0,72.


Пример 3. В парикмахерской работают 3 мастера, а в зале ожидания расположены 3 стула. Поток клиентов имеет интенсивность Система массового обслуживания с ограниченным временем ожидания=12 клиентов в час. Среднее время обслуживания tобсл=20 мин. Определить относительную и абсолютную пропускную способность системы, среднее число занятых кресел, среднюю длину очереди, среднее время, которое клиент проводит в парикмахерской.

Для данной задачи n=3, m=3, Система массового обслуживания с ограниченным временем ожидания=12, μ=3, ρ=4, ρ/n=4/3. Вероятность простоя определяем по формуле:


Р0=Система массового обслуживания с ограниченным временем ожидания.

P0=Система массового обслуживания с ограниченным временем ожиданияСистема массового обслуживания с ограниченным временем ожидания0,012.


Вероятность отказа в обслуживании определяем по формуле


Ротк=Рn+m= Система массового обслуживания с ограниченным временем ожидания.

Pотк=Pn+mСистема массового обслуживания с ограниченным временем ожиданияСистема массового обслуживания с ограниченным временем ожиданияСистема массового обслуживания с ограниченным временем ожидания0,307.


Относительная пропускная способность системы, т.е. вероятность обслуживания:


Pобсл=1-PоткСистема массового обслуживания с ограниченным временем ожидания1-0,307=0,693.


Абсолютная пропускная способность:


А=Система массового обслуживания с ограниченным временем ожиданияРобслСистема массового обслуживания с ограниченным временем ожидания12Система массового обслуживания с ограниченным временем ожидания.


Среднее число занятых каналов:


Система массового обслуживания с ограниченным временем ожидания.

Средняя длина очереди определяется по формуле:


L=Система массового обслуживания с ограниченным временем ожидания

L=Система массового обслуживания с ограниченным временем ожиданияСистема массового обслуживания с ограниченным временем ожидания1,56.


Среднее время ожидания обслуживания в очереди:


t=Система массового обслуживания с ограниченным временем ожиданияч.


Среднее число заявок в СМО:


M=L+Система массового обслуживания с ограниченным временем ожидания.

Среднее время пребывания заявки в СМО:


Т=М/Система массового обслуживания с ограниченным временем ожиданияСистема массового обслуживания с ограниченным временем ожидания0,36 ч.


Пример 4. Рабочий обслуживает 4 станка. Каждый станок отказывает с интенсивностью Система массового обслуживания с ограниченным временем ожидания=0,5 отказа в час, среднее время ремонта tрем=1/μ=0,8 ч. Определить пропускную способность системы.

Эта задача рассматривает замкнутую СМО, μ=1,25, ρ=0,5/1,25=0,4. Вероятность простоя рабочего определяем по формуле:


Р0=Система массового обслуживания с ограниченным временем ожидания.

P0=Система массового обслуживания с ограниченным временем ожидания.


Вероятность занятости рабочего Рзан=1-Р0Система массового обслуживания с ограниченным временем ожидания. Если рабочий занят, он налаживает μ-станков в единицу времени, пропускная способность системы: А=(1-P0)μ=0,85μ Система массового обслуживания с ограниченным временем ожидания станков в час.


Решение задачи


Задача:

Два рабочих обслуживают группу из четырех станков. Остановки работающего станка происходят в среднем через 30 мин. Среднее время наладки составляет 15 мин. Время работы и время наладки распределено по экспоненциальному закону.

Найдите среднюю долю свободного времени для каждого рабочего и среднее время работы станка.

Найдите те же характеристики для системы, в которой:

а) за каждым рабочим закреплены два станка;

б) два рабочих всегда обслуживают станок вместе, причем с двойной интенсивностью;

в) единственный неисправный станок обслуживают оба рабочих сразу (с двойной интенсивностью), а при появлении еще хотя бы одного неисправного станка они начинают работать порознь, причем каждый обслуживает один станок (вначале опишите систему в терминах процессов гибели и рождения).

Решение:

Возможны следующие состояния системы S:

S0 – все станки исправны;

S1 – 1 станок ремонтируется, остальные исправны;

S2 – 2 станок ремонтируется, остальные исправны;

S3 – 3 станок ремонтируется, остальные исправны;

S4 – 4 станок ремонтируется, остальные исправны;

S5 – (1, 2) станки ремонтируются, остальные исправны;

S6 – (1, 3) станки ремонтируются, остальные исправны;

S7 – (1, 4) станки ремонтируются, остальные исправны;

S8 – (2, 3) станки ремонтируются, остальные исправны;

S9 – (2, 4) станки ремонтируются, остальные исправны;

S10 – (3, 4) станки ремонтируются, остальные исправны;

S11 – (1, 2, 3) станки ремонтируются, 4 станок исправен;

S12 – (1, 2, 4) станки ремонтируются, 3 станок исправен;

S13 – (1, 3, 4) станки ремонтируются, 2 станок исправен;

S14 – (2, 3, 4) станки ремонтируются, 1 станок исправен;

S15 – все станки ремонтируются.

Граф состояний системы…


Система массового обслуживания с ограниченным временем ожидания


Данная система S является примером замкнутой системы, так как каждый станок является потенциальным требованием, превращаясь в реальное в момент своей поломки. Пока станок работает, он находится в блоке задержки, а с момента поломки до момента окончания ремонта – в самой системе. Каждый рабочий является каналом обслуживания.


Система массового обслуживания с ограниченным временем ожидания

Система массового обслуживания с ограниченным временем ожидания

Система массового обслуживания с ограниченным временем ожидания

Система массового обслуживания с ограниченным временем ожидания

Система массового обслуживания с ограниченным временем ожидания

Система массового обслуживания с ограниченным временем ожидания


Вероятность простоя рабочего определяется по формуле:


Система массового обслуживания с ограниченным временем ожидания

Система массового обслуживания с ограниченным временем ожидания

Система массового обслуживания с ограниченным временем ожидания.


Вероятность занятости рабочего:


Система массового обслуживания с ограниченным временем ожидания.

Если рабочий занят, он налаживает μ-станков в единицу времени, пропускная способность системы:


Система массового обслуживания с ограниченным временем ожидания.


Ответ:

Средняя доля свободного времени для каждого рабочего ≈ 0,09.

Среднее время работы станка ≈ 3,64.

а) За каждым рабочим закреплены два станка.


Система массового обслуживания с ограниченным временем ожидания

Система массового обслуживания с ограниченным временем ожидания

Система массового обслуживания с ограниченным временем ожидания

Система массового обслуживания с ограниченным временем ожидания

Система массового обслуживания с ограниченным временем ожидания

Система массового обслуживания с ограниченным временем ожидания


Вероятность простоя рабочего определяется по формуле:


Система массового обслуживания с ограниченным временем ожидания

Система массового обслуживания с ограниченным временем ожидания

Система массового обслуживания с ограниченным временем ожидания.


Вероятность занятости рабочего:


Система массового обслуживания с ограниченным временем ожидания.


Если рабочий занят, он налаживает μ-станков в единицу времени, пропускная способность системы:


Система массового обслуживания с ограниченным временем ожидания.


Ответ:

Средняя доля свободного времени для каждого рабочего ≈ 0,62.

Среднее время работы станка ≈ 1,52.

б) Два рабочих всегда обслуживают станок вместе, причем с двойной интенсивностью.

в) Единственный неисправный станок обслуживают оба рабочих сразу (с двойной интенсивностью), а при появлении еще хотя бы одного неисправного станка они начинают работать порознь, причем каждый обслуживает один станок (вначале опишите систему в терминах процессов гибели и рождения).

Сравнение 5 ответов:

Наиболее эффективным способом организации рабочих за станками будет являться начальный вариант задачи.


Заключение


Выше были рассмотрены примеры простейших систем массового обслуживания (СМО). Понятие «простейшие» не означает «элементарные». Математические модели этих систем применимы и успешно используются в практических расчетах.

Возможность применения теории принятия решений в системах массового обслуживания определяется следующими факторами:

1. Количество заявок в системе (которая рассматривается как СМО) должно быть достаточно велико (массово).

2. Все заявки, поступающие на вход СМО, должны быть однотипными.

3. Для расчетов по формулам необходимо знать законы, определяющие поступление заявок и интенсивность их обработки. Более того, потоки заявок должны быть Пуассоновскими.

4. Структура СМО, т.е. набор поступающих требований и последовательность обработки заявки, должна быть жестко зафиксирована.

5. Необходимо исключить из системы субъектов или описывать их как требования с постоянной интенсивностью обработки.

К перечисленным выше ограничениям можно добавить еще одно, оказывающее сильное влияние на размерность и сложность математической модели.

6. Количество используемых приоритетов должно быть минимальным. Приоритеты заявок должны быть постоянными, т.е. они не могут меняться в процессе обработки внутри СМО.

В ходе выполнения работы была достигнута основная цель – изучен основной материал «СМО с ограниченным временем ожидания» и «Замкнутые СМО», которая была поставлена преподавателем учебной дисциплины. Также мы ознакомились применением полученных знаний на практике, т.е. закрепили пройденный материал.

Список литературы


1) http://www.5ballov.ru.

2) http://www.studentport.ru.

3) http://vse5ki.ru.

4) http://revolution.allbest.ru.

5) Фомин Г.П. Математические методы и модели в коммерческой деятельности. М: Финансы и статистика, 2001.

6) Гмурман В.Е. Теория вероятностей и математическая статистика. М: Высшая школа, 2001.

7) Советов Б.А., Яковлев С.А. Моделирование систем. М: Высшая школа, 1985.

8) Лифшиц А.Л. Статистическое моделирование СМО. М., 1978.

9) Вентцель Е.С. Исследование операций. М: Наука, 1980.

10) Вентцель Е.С., Овчаров Л.А. Теория вероятностей и её инженерные приложения. М: Наука, 1988.

Похожие работы:

  1. • Понятие и классификация систем массового ...
  2. • Системы массового обслуживания
  3. • Разработка имитационной модели системы массового ...
  4. •  ... теории массового обслуживания в экономическом ...
  5. • Математическое моделирование и оптимизация системы ...
  6. • Методика оптимизации библиотечной системы обслуживания
  7. • Моделирование систем массового обслуживания
  8. • Методика оптимизации структуры и параметров библиотечной ...
  9. •  ... распределения трехузловой сети массового обслуживания
  10. • Теория массового обслуживания с ожиданием
  11. • Моделирование системы массового обслуживания
  12. • Имитационное моделирование работы систем ...
  13. • Моделирование 2-х канальной системы массового обслуживания с ...
  14. • Имитационное моделирование системы массового ...
  15. • Моделирование систем массового обслуживания
  16. • Имитационное моделирование системы массового ...
  17. • Теория массового обслуживания с ожиданием
  18. • Методика оптимизации структуры и параметров библиотечной ...
  19. • Планирование машинного эксперимента с ...
Смотреть все похожие работы
Рефетека ру refoteka@gmail.com