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

 

СОДЕРЖАНИЕ

ВВЕДЕНИЕ____________________________________________________3

1. Предмет и задачи теории массового обслуживания__________________4
1. Система массового обслуживания_____________________________5
2. Классификация систем массового обслуживания_________________6
2. Понятие марковского случайного процесса________________________7
3. Потоки событий_______________________________________________10

ЗАКЛЮЧЕНИЕ_________________________________________________13

СПИСОК ЛИТЕРАТУРЫ_________________________________________14

 

ВВЕДЕНИЕ

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

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

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

 

 

 

 

1. Предмет и задачи теории массового обслуживания

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

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

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

Задачи теории массового обслуживания носят оптимизационный характер и в конечном итоге включают экономический аспект по определению такого варианта системы, при котором будет обеспечен минимум суммарных затрат от ожидания обслуживания, потерь времени и ресурсов на обслуживание и простоев каналов обслуживания. [1]

 

 

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

 

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

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

 

 

 

 

 

 

 

 

 

 

 

Рис.1. Структура СМО.

3. Классификация СМО.

 

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

Рис. 2 Классификация СМО

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

• среднее время обслуживания;
• среднее время ожидания в очереди;
• среднее время пребывания в СМО;
• средняя длина очереди;
• среднее число заявок в СМО;
• количество каналов обслуживания;
• интенсивность входного потока заявок;
• интенсивность обслуживания;
• интенсивность нагрузки;
• коэффициент нагрузки;
• относительная пропускная способность;
• абсолютная пропускная способность;
• доля времени простоя СМО;
• доля обслуженных заявок;
• доля потерянных заявок;
• среднее число занятых каналов;
• среднее число свободных каналов;
• коэффициент загрузки каналов;
• среднее время простоя каналов.

 

2. Понятие марковского случайного процесса

 

Процесс работы СМО представляет собой случайный процесс. 

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

 Процесс называется процессом с дискретными состояниями, если его возможные состояния S₁, S₂, S₃… можно заранее перечислить, а переход системы из состояния в состояние происходит мгновенно (скачком). Процесс называется процессом с непрерывным временем, если моменты возможных переходов системы из состояния в состояние не фиксированы заранее, а случайны. 

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

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

Например, показание S счетчика в такси в какой-либо момент времени t зависят только от показаний S₀ счетчика в начальный момент времени t₀ и от пути, пройденного такси после этого момента, что является случайной величиной, и не зависит от того, как изменялись показания счетчика до момента t₀. [3]

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

Например, процесс игры в шахматы; система S — группа шахматных фигур. Состояние системы характеризуется числом фигур противника, сохранившихся на доске в момент t₀. Вероятность того, что в момент t > t₀ материальный перевес будет на стороне одного из противников, зависят в первую очередь от того, в каком состоянии находится система в данный момент t₀, а не того, когда и в какой последовательности исчезли фигуры с доски до момента t₀. 

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

Для примера построим граф состояний технической системы S, состоящей из двух узлов, каждый из которых в случайный момент времени может выйти из строя, после чего мгновенно начинается ремонт узла, продолжающийся заранее неизвестное случайное время. [3]

Возможные состояния  системы:

S₀ — оба узла исправны;

S₁ — первый узел ремонтируется, второй исправен;

S₂ — второй узел ремонтируется, первый исправен;

S₃ — оба узла ремонтируются.

Граф системы приведен на рис.3.

 

 

 

 

 

 

 

 

 

Рис.3. Граф состояний системы из двух узлов

 

Стрелка, направленная, например, из S₀ в S₁ означает переход системы в момент отказа первого узла, из S₁ в S₀ — переход в момент окончания ремонта этого узла. 

На графе отсутствуют  стрелки из S₀, в S₃ и из S₁ в S₂. Это объясняется тем, что выходы узлов из строя предполагаются независимыми друг от друга и, например, вероятностью одновременного выхода из строя двух узлов (переход из S₀ в S₃) или одновременного окончания ремонтов двух узлов (переход из S₃ в S₀) можно пренебречь. 

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

 

 

3. Потоки событий

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

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

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

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

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

Поток событий называется ординарным, если события в нем проявляются поодиночке, а не группами. Например, поток поездов, подходящих к станции ординарен, а поток вагонов нет. Если поток ординарен, то вероятность попадания на малый промежуток времени ∆t двух или более событий можно пренебречь. [2]

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

Выделим на оси времени Ot промежуток t, рис.4, и рассмотрим случайную величину m – число событий, которое происходит за этот промежуток.

Рис. 4 Ось времени случайного процесса

Для простейшего потока событий  вероятность того, что в течение промежутка времени t произойдет ровно m событий, находится по формуле: