logo search
Задания, лекции / Lab4

6.3. Время ожидания и время обслуживания

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

(6.12)

Это обусловлено многими причинами, среди которых следует отметить: 1) отсутствие последействия; 2) достаточно кор­ректное отражение свойств многих реальных систем обслужи­вания; 3) простоту и удобство аналитических выражений.

Согласно (6.12), среднее время обслуживания заявки равно 1/ (ср. (6.9)). Величину  называют интенсивностью об­служивания. Функция распределения времени обслуживания заявки равна

(6.13)

Ее значение равно вероятности того, что к моменту времени t обслуживание заявки будет завершено, т.е. освободится канал обслуживания.

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

(6.14)

и функцией распределения

(6.15)

где v — величина, обратная среднему времени ожидания, а значение H(t) равно вероятности того, что в момент t начнется обслуживание заявки.

Основные принципы построения марковских моделей массового обслуживания

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

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

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

Пусть Si, — возможное состояние рассматриваемой системы обслуживания, характеризуемое тем, что в ней занято ровно i каналов обслуживания, i = 0…m, а возможное состояние системы Sm+r характеризуется тем, что все m каналов обслуживания заняты и очередь состоит из r заявок, где r1. Если на длину очереди не накладывают ограничений, то r может быть сколь угодно большим и система может иметь счетное множество состояний. Системы обслуживания с отказами и с ограничениями на длину очереди могут иметь лишь конечные множества возможных состояний.

4. За бесконечно малый промежуток времени t система обслуживания с простейшим входным потоком заявок и экс­поненциальным законом распределения времени обслуживания либо остается в прежнем состоянии (S), либо переходит в со­седнее (Si+1 или Si-1 при i 1, S1 при i= 0).

Таким образом, в любой момент времени t система обслуживания с m идентичными параллельными каналами обслужива­ния находится в одном из своих возможных состояний {Si}ni=0, nN или п =. При этом:

если i = 0…m , то занято i каналов и очереди нет;

если i = m+1…n, то заняты все m каналов и в очереди находится (n - m) заявок;

если n = m, то рассматривают систему обслуживания с отказами;

если m < п < , то рассматривают систему обслуживания ограниченной длиной очереди;

если п =, то рассматривают систему обслуживания с ожиданием без ограничений на длину очереди.

5. Пусть {Si}ni=0— множество возможных состояний рассматриваемой системы обслуживания. Для i = 0,… п введем случайное событие i,-, заключающееся в том, что в момент времени t0 система находится в состоянии Si, и обозначим вероятность его реализации через pi(t): Pi(t) = P [i]. В лю­бой момент времени исходная система может находиться лишь в одном из возможных состояний, поэтому {i}ni=1 — полная группа событий и, как следствие,

(6.16)

Одна из задач теории массового обслуживания сводится к определению вероятностей pi(t), i = 0, ..n, как функций времени.

6. Из приведенных выше рассуждений и определения марковского процесса с дискретными состояниями следует, что рассматриваемые процессы массового обслуживания являются процессами гибели — размножения. К изложенному в 5.4 добавим следующее:

а) элемент размеченного графа состояний системы S, со­ответствующий возможному состоянию Sk, будем называть k-й вершиной графа; стрелки, указывающие возможные пе­реходы системы S из состояния в состояние, с записанными переходными вероятностями, — нагруженными дугами, а переходные вероятности — весами]

б) при составлении системы уравнений Колмогорова можно использовать следующее правило: производная от вероятности пребывания системы в состоянии S; в момент времени t рав­на сумме произведений весов дуг, инцидентных i-й вершине размеченного графа состояний, на вероятности состояний, к j которым они направлены; при этом вес дуги берется со знаком „плюс", если дуга направлена к i-й вершине, соответствующей состоянию Si, и со знаком „минус" в противном случае;

в)плотности вероятностей переходов {ij}, а следова­тельно, и переходные вероятности могут зависеть от струк­туры системы, характеристик входного потока и параметров законов распределения времени ожидания и времени обслуживания.

>>>

Переход из состояния Si, в „младшее" состояние Si-1 зави­сит лишь от освобождения каналов обслуживания. Если . — интенсивность обслуживания, то функция распределения вре­мени обслуживания определяется по формуле (6.13). Поэтому

и, следовательно,

Таким образом, при наличии лишь одного канала обслуживания плотность вероятности перехода в „младшее" состояние равна' . Если занято i каналов и iт (т — число каналов обслуживания), то в силу независимости их функционирования интенсивность обслуживания возрастает в i раз, т.е. i,i-1= i .

>>>

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

В данном случае система имеет лишь два возможных состояния: s0 — канал сво­боден; Si — канал занят. Ее размеченный граф состояний изображен на рис..

далее (см. 6.5) мы докажем, что 01 и 10. Если считать, что в начальный момент времени t = 0 система находилась в состоянии s0, то математическая модель изучаемого процесса массового обслуживания имеет следующий вид:

При этом, учитывая, что, согласно (6.16),

математическую модель можно упростить:

Решив полученную задачу Коши, находим (рис. 6.3)

Важнейшими характеристиками системы обслуживания с отказами являются:

а) абсолютная пропускная способность — среднее число заявок, которое может обслужить система в единицу

времени;

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

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

При стационарном (установившемся) режиме функци­онирования имеем

(6.17)

Поэтому в рассматриваемом случае относительная пропуск­ная способность системы обслуживания равна /( + ,). Мож­но показать, что абсолютная пропускная способность равна величине обратной сумме среднего времени ожидания заявки и среднего времени ее обслуживания:

(6.18)

Пример 6.3. Одноканальная система обслуживания пред­ставляет собой телефонную линию. Заявка-вызов, поступив­шая в момент, когда линия занята, получает отказ. Интен­сивность потока заявок 0,8 (вызовов в минуту). Средняя продолжительность разговора 1,5 минуты. Считая поток за­явок простейшим, а время обслуживания распределенным по экспоненциальному закону, определим в стационарном режиме функционирования:

1) абсолютную пропускную способность канала связи Q;

2) относительную пропускную способность канала связи q;

3) вероятность отказа рот.

Имеем

Таким образом,

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

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

Отметим, что номинальная пропускная способность рассма­триваемого канала связи Qнoм, являясь величиной обратной по отношению к средней продолжительности времени разговора (Qнoм — = 2/3 = 0,66), почти вдвое больше его пропускной способности Q, определенной с учетом случайного характера потока заявок и времени обслуживания.

Задания.

  1. Моделирование пуассоновского потока событий. Известно, что распределение Пуассона есть предельный случай биномиального распределения при m  , p0, mp   , где p –вероятность события при эксперименте, m- число экспериментов,  - конечное число, называемое интенсивностью потока.

Смоделируйте случайный поток функцией =ЕСЛИ(СЛЧИС()<$B$2;1;0) в столбик 50 – 100 значений (m) , здесь в ячейке В2 находится вероятность события (p); задайте p в пределах 0,02…0,2

    1. Просчитайте количество событий (k ) , т.е. найдите сумму по столбцу.

    2. Распространите вычисления на N столбцов, (N>30), найдите среднее значения для величины k и дисперсию данной величины, сравните их с величиной =mp.

    3. Проделайте эксперимент, увеличивая m до 100, N до 50, уменьшая p, сделайте выводы.

(Дисперсия и математическое ожидание случайной величины с распределения Пуассона равны )

    1. Проверьте справедливость формулы 6.5 при больших числах m и N на нескольких примерах.

  1. Моделирование функционирования одноканальной системы массового обслуживания с отказами(см. табл.)

A

B

C

D

E

F

1

p(lam)

p(mu)

2

0,1

0,25

3

10

4

4

t

Zayavky

Zan do

Obsl

Zan pos

5

В столбце A моделируется время начиная с шестой строки (1, 2, 3…) будем условно считать, что в минутах.

В ячейке B2 задается вероятность поступления заявки, p(lam)=0,1 (1 заявка в 10 мин., =10).

В ячейке D2 задается интенсивность обслуживания. p(mu)= 0,25 ( среднее время обслуживания одной заявки при поступлении 4 мин, т.е. =4)

В столбце В, начиная с В4, моделируется поток заявок с параметром  по средством функции =ЕСЛИ(СЛЧИС()<$B$2;1;0), значение «1» соответствует поступлению заявки.

В столбце D, начиная с D4, (поле Zan do) определяется занятость канала на момент до обслуживания на данном шаге (1-занят , 0- свободен); в первом случае (ячейка D6) это зависит только от поступления заявки ( функция=ЕСЛИ(B6=1;1;0) ), на следующем шаге и далее также от состояния занятости на предыдущих шагах ( функция для D7 =ЕСЛИ(ИЛИ(B7=1;F6=1);1;0)).

В столбце E, начиная с E4, моделируется поток обслуживания с параметром , с учетом того, что обслуживание начинается по поступлении заявки, т. е. канал становится занятым, можно использовать функцию для E6 =ЕСЛИ(D6=0;0; ЕСЛИ(СЛЧИС()<$D$2;1;0)); здесь 1-заявка обслужена, 0- пока не обслужена.

В столбце F, начиная с F4, (поле Zan pos) определяется занятость канала на момент после попытки обслуживания на данном шаге (1-занят , 0- свободен); канал остается занятым, если его не обслужили, т.е. можно использовать следующую функцию для F6 =ЕСЛИ(И(D6=1;E6=0);1;0).

Последующие шаги можно получить «потягиванием».

По имеющимся данным для t=1,2…60. найти

  1. Общее число поступивших заявок - nZ (сумма по столбцу B), число обслуженных заявок – nO(сумма по столбцу D), число потерянных заявок- nP.

  2. По формулам 6.17 найти вероятности p0, p1обработки (относительную пропуск­ную способность системы) и потери заявки; проведя эксперимент многократно 20-40 раз ( если активизировать близлежащие ячейки результаты меняются) найти средние для величин v0= nO / nZ , v1= nP / nZ и сравнить их с p0, p1.

  3. Найти абсолютную пропуск­ную способность системы по формуле 6.18 и исходя из реальных данных как среднее по разным экспериментам для величины nO / m, где m – наибольший отсчет времени ( в нашем случае 60).

Изменяя  и  (соответственно p(lam) и p(mu) найдите характеристики работы системы, сделайте выводы.

3) Попытайтесь смоделировать двухканальную систему массового обслуживания с отказами. Поступающая заявка обслуживается сначала первым каналом, при занятости первого – вторым, при занятости обоих каналов – теряется. Экспериментально определите основные параметры при разных параметрах , 1,2, сделайте выводы. Что является более эффективным: двухканальное обслуживание с вероятностями обслуживания каналов p(1) и p(2) или одноканальная с интенсивностью обслуживания с вероятностью обслуживания p() = p(1) + p(2) ?

9