Постановка задач массового обслуживания

 

1.2. Графы состояний СМО

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

 

 

 

 

 

 

 

 

 

λ₀₁ λ₁₂

 

 

 

λ₁₀ λ₂₁

 

Рисунок 1 – Размеченный граф состояний СМО

 

Система может находиться в одном из трех состояний: S₀ – канал свободен, простаивает, S₁ – канал занят обслуживанием, S₂– канал занят обслуживанием и одна заявка в очереди. Переход системы из состояния S₀ в S_l происходит под воздействием простейшего потока заявок интенсивностью λ ₀₁ а из состояния S_l в состояние S₀ систему переводит поток обслуживания с интенсивностью λ ₀₁. Граф состояний системы обслуживания с проставленными интенсивностями потоков у стрелок называется размеченным. Поскольку пребывание системы в том или ином состоянии носит вероятностный характер, то вероятность:p_i(t) того, что система будет находиться в состоянии S_i в момент времени t, называется вероятностью i– го состояния СМО и определяется числом поступивших заявок k на обслуживание.

Случайный процесс, происходящий в системе, заключается в том, что в случайные моменты времени t₀, t_1, t₂,..., t_k,..., t_n система оказывается в том или другом заранее известном дискретном состоянии последовательно. Такая. случайная последовательность событий называется Марковской цепью, если для каждого шага вероятность перехода из одного состояния S_t в любое другое Sj не зависит от того, когда и как система перешла в состояние S_t. Описывается марковская цепь с помощью вероятности состояний, причем они образуют полную группу событий, поэтому их сумма равна единице. Если вероятность перехода не зависит от номера к, то марковская цепь называется однородной. Зная начальное состояние системы обслуживания, можно найти вероятности состояний для любого значения к– числа заявок поступивших на

обслуживание. [3]

 

1.3. Случайные процессы

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

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

Такие случайные  процессы называются процессами без  последствия, или марковскими, в которых при фиксированном настоящем будущее состояние СМО не зависит от прошлого. Случайный процесс, протекающий в системе, называется марковским случайным процессом, или «процессом без последствия», если он обладает следующим свойством: для каждого момента времени t₀ вероятность любого состояния t > t₀ системы S_i, – в будущем (t >t_Q) зависит только от ее состояния в настоящем (при t = t₀) и не зависит от того, когда и каким образом система пришла в это состояние, т.е. оттого, как развивался процесс в прошлом.

Марковские  случайные процессы делятся на два  класса: процессы с дискретными и  непрерывными состояниями. Процесс  с дискретными состояниями возникает  в сиcтемах, обладающих только некоторыми фиксированными состояниями, между которыми возможны скачкообразные переходы в некоторые, заранее не известные моменты времени. Рассмотрим пример процесса с дискретными состояниями. В офисе фирмы имеются два телефона. Возможны следующие состояния у этой системы обслуживания: S_o – телефоны свободны; S_l – один из телефонов занят; S₂ – оба телефона заняты.

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

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

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

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

Для описания процессов с непрерывным временем используется модель в виде так называемой марковской цепи с дискретными состояниями системы, или непрерывной марковской цепью. [4]

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

1.   По характеру обслуживания выделяют следующие виды СМО:

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

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

1.2. Системы с ограниченной очередью. (ремонт в гараже)

1.3. Системы с отказами. Все заявки, прибывшие в момент обслуживания заявки, получают отказ. (ГТС)

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

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

 следующие  группы:

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

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

3. По кругу обслуживаемых объектов различают два вида:

Замкнутые СМО. Замкнутая система массового обслуживания – это система массового обслуживания, в которой обслуженные требования могут возвращаться в систему и вновь поступать на обслуживание. Примерами замкнутой СМО являются ремонтные мастерские, сберегательные банки.

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

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

Однофазные СМО – это однородные системы, которые выполняют

 одну  и ту же операцию обслуживания.

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

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

 

 

 

2 УРАВНЕНИЯ, ОПИСЫВАЮЩИЕ СИСТЕМЫ  МАССОВОГО ОБСЛУЖИВАНИЯ

 

2.1. Уравнения Колмогорова

 

Рассмотрим  математическое описание марковского случайного процесса с дискретными состояниями системы S_o, S_l, S₂ и непрерывным временем. Полагаем, что все переходы системы массового обслуживания из состояния S_i в состояние Sj происходят под воздействием простейших потоков событий с интенсивностями λ_ij, а обратный переход под воздействием другого потока λ_ij. Введем обозначение p_i как вероятность того, что в момент времени t система находится в состоянии S_i. Для любого момента времени t справедливо записать нормировочное условие – сумма вероятностей всех состояний равна 1:

₂

Σp_i(t)=p₀(t)+ p₁(t)+ p₂(t)=1

ⁱ⁼⁰

Проведем  анализ системы в момент времени t, задав малое приращение времени Δt, и найдем вероятность р₁ (t+ Δt) того, что система в момент времени (t+Δt) будет находиться в состоянии S₁ которое достигается разными вариантами:

а) система  в момент t с вероятностью p₁(t) находилась в состоянии S₁ и за малое приращение времени Δt так и не перешла в другое соседнее состояние – ни в S₀, ни b S₂. Вывести систему из состояния S₁ можно суммарным простейшим потоком c интенсивностью (λ₁₀ +λ₁₂), поскольку суперпозиция простейших потоков также является простейшим потоком. На этом основании вероятность выхода из состояния S₁ за малый промежуток времени Δt приближенно равна (λ₁₀ +λ₁₂)*Δt. Тогда вероятность невыхода из этого состояния равна [1 – (λ₁₀ +λ₁₂)* Δ t].B соответствии с этим вероятность того, что система останется в состоянии S_i на основании теоремы умножения вероятностей, равна:

 

p₁(t) [1 – (λ₁₀ +λ₁₂)* Δ t];

 

б) система находилась в соседнем состоянии S_o и за малое время Δt перешла в состояние S_o Переход системы происходит под воздействием потока λ₀₁ с вероятностью, приближенно равной λ₀₁Δ t .

Вероятность того, что система будет находиться в состоянии S₁, в этом варианте равна p_o(t) λ ₀₁ Δ t;

в) система  находилась в состоянии S₂ и за время Δ t перешла в состояние S₁ под воздействием потока интенсивностью λ ₂₁ с вероятностью, приближенно равной λ₂₁Δ t. Вероятность того, что система будет находиться в состоянии S₁, равна p₂(t) λ₂₁Δ t.

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

 

p₂(t+Δt)= p₁(t) [1 – (λ₁₀ +λ₁₂)* Δ t]+ p_o(t) λ ₀₁ Δ t+ p₂(t) λ₂₁Δ t ,

 

которое можно записать иначе:

 

p₂(t+Δt)– p₁(t)/ Δ t= p_o(t) λ ₀₁+ p₂(t) λ₂₁– p₁(t) (λ₁₀ +λ₁₂) .

 

Переходя  к пределу при Δt – > 0, приближенные равенства перейдут в точные, и тогда получим производную первого порядка

 

dp₂/dt= p₀ λ ₀₁ +p₂ λ₂₁ – p₁ (λ₁₀ +λ₁₂) ,

 

что является дифференциальным уравнением.

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

 

dp₀ /dt= p₁ λ ₁₀ ,

dp₁ /dt= p₀ λ ₀₁ +p₂ λ₂₁ – p₁ (λ₁₀ +λ₁₂) ,

dp₂ /dt= p₁ λ ₁₂ +p₂ λ_{21 .}

 

Для составления  уравнений Колмогорова существуют общие правила.

Уравнения Колмогорова позволяют вычислить  все вероятности состояний СМО S_i в функции времени p_i(t). В теории случайных процессов показано, что если число состояний системы конечно, а из каждого из них можно перейти в любое другое состояние, то существуют предельные (финальные) вероятности состояний, которые показывают на среднюю относительную величину времени пребывания системы, в этом состоянии. Если предельная вероятность состояния S₀ – равна p₀ ⁼ 0,2, то, следовательно, в среднем 20% времени, или 1/5 рабочего времени, система находится в состоянии S_o. Например, при отсутствии заявок на обслуживание к = 0, р₀ = 0,2,; следовательно, в среднем 2 ч в день система находится в состоянии S_o и простаивает, если продолжительность рабочего дня составляет 10 ч.