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

 

 

Содержание

 

Введение 3

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

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

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

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

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

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

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

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

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

Заключение 38

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

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

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

В данной курсовой работе целью исследования является характеристика

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

Для достижения заданных целей нам  необходимо решить следующие задачи:

• Выяснить, из чего состоит СМО.
• Рассмотреть основные процессы СМО.
• Проанализировать классификацию СМО.

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

 

 

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

 

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

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

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

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

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

 

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

 

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

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

Примеры:

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

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

 

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

 

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

 

 

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

 

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

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

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

 

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

 

На этом рисунке  - интенсивности потока отказов; - интенсивности потока восстановлений.

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

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

 

 

где - среднее время безотказной работы первого станка.

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

 

 

где - среднее время ремонта первого станка.

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

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

 

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

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

 

 

где - конечное число состояний системы.

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

 

 

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

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

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

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

 

.

 

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

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

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

 

.

 

.

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