Патудин В.М., Блем А.Г. Математическая экономика

6. МОДЕЛИ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ

6.1 Определение систем массового обслуживания

Под системой массового обслуживания (СМО) понимается некоторая сис-

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

Элементы СМО называются обслуживающими каналами. Заявки в систе-

му поступают в случайные моменты времени, продолжительность обслужива-

ния одной заявки также является случайной величиной. Задачи исследования

СМО впервые были рассмотрены А.К. Эрлангом в начале 20 века и легли в ос-

нову теории массового обслуживания, которая развивается до сих пор. Данная

теория базируется на теории Марковских случайных процессов, уравнениях

Колмогорова для вероятностей состояний, анализе процессов «гибели и раз-

множения», формуле Литтла и других теоретических положений, которые рас-

сматриваются в рамках теории массового обслуживания.

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

живания.

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

одно за другим в какие-то случайные моменты времени. Например, поток вызовов на теле-

фонной станции, поток вызовов на станции скорой помощи, поток автомобилей, прибы-

вающих на АЗС, поток покупателей у кассы магазина и т.п.

Интенсивность (скорость) потока обозначается символом

λλ

и представляет собой

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

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

зависят от времени. Например, поток покупателей в магазине между 17 и 18 часами можно

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

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

а не группами по нескольку сразу.

Поток событий называется без последействия, если для любых непересекающихся ин-

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

событий попало на другой.

Поток событий называется

простейшим

(стационарным пуассоновским), если он об-

ладает свойствами

стационарности, ординарности и не имеет последействия.

Для простейшего потока интервал времени

между соседними событиями имеет по-

казательное распределение с плотностью:

f(t) =

λe

-λt

t>0

(6.1)

в формуле (6.1) называется параметров показательного закона. Как известно из кур-

са теории вероятностей для случайной величины Т, имеющей показательное распределение,

математическое ожидание М

есть величина , обратная параметру

λ, а

среднее квадратиче-

ское отклонение σ

равно математическому ожиданию: М

= 1/

λ.

Любая СМО состоит из блока обслуживания, состоящего из одного или

нескольких каналов обслуживания и потока заявок, поступающих в систему.

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

вания населения (магазины, предприятия общественного питания), больницы,

станции скорой помощи, ремонтные, инструментальные, транспортные, склад-

ские хозяйства промышленных предприятий, телекоммуникационные системы

и многие другие объекты экономической, технической и социальной сферы

жизнедеятельности человека.

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

По количеству обслуживающих каналов различают одноканальные (со-

стоящие из одного обслуживающего канала) и многоканальные (состоящие из

нескольких каналов) СМО.

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

все обслуживающие каналы заняты, различают «СМО с отказами» (заявки по-

лучают отказ и покидают систему) и «СМО с ожиданием (очередью)» (заявки

встают в очередь на обслуживание).

Среди СМО с ожиданием, в свою очередь, различают: «СМО с неограни-

ченным временем ожидания (неограниченной длиной очереди)» (заявки в лю-

бом случае встают в очередь и ждут обслуживания), «СМО с ограниченным

временем ожидания» (заявки встают в очередь и ожидают обслуживания, но

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

начнется, заявка покидает систему), «СМО с ограниченной длиной очереди»

(заявка встает в очередь, если ее длина на момент поступления заявки не пре-

вышает заданную величину, в противном случае заявка покидает систему).

По месту формирования заявок на обслуживание различают открытые

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

этому интенсивность входного потока заявок не зависит от состояния самой

СМО) и закрытые или замкнутые СМО (источники заявок находятся внутри

системы, поэтому интенсивность входного потока заявок зависит от состояния

СМО). Примерами открытых СМО служат станции скорой помощи, магазины

и т.п. Пример замкнутой СМО – наладчик, обслуживающий пять станков. Ис-

точниками заявок в этом случае являются станки, требующие наладки. Если в

некоторый момент времени требуют наладки два станка, то источниками но-

вых заявок могут быть только оставшиеся три станка.

СМО с ожиданием могут отличаться дисциплиной обслуживания. Наибо-

лее естественной является дисциплина «первым пришел – первым обслужен»,

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

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

пришел – первым обслужен», «обслуживание в соответствии с приоритетом

(статусом) заявки».

6.3. Параметры СМО

Входные переменные СМО:

λλ

интенсивность (скорость) входного потока заявок (среднее количест-

во заявок, поступающих в систему в единицу времени),

µµ

–

––

–

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

которое может обслужить один канал в единицу времени)

–

––

–

количество обслуживающих каналов

µx

µxµx

µx

–

––

–

совокупная интенсивность (скорость) обслуживания (среднее коли-

чество заявок, которое могут обслужить все обслуживающие каналы, то есть

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

производительность).

При этом переменные λ

λλ

и µ

µµ

являются неуправляемыми переменными, а

переменная x

управляемой переменной СМО.

Выходные переменные СМО:

Для систем с отказами основными выходными переменными являются:

Pотк – вероятность в отказе обслуживания поступившей заявки;

А – абсолютная пропускная способность СМО (среднее число заявок, об-

служенных в единицу времени)

К – коэффициент загрузки СМО (доля каналов, занятых обслуживанием)

Для систем с ожиданием основными выходными переменными являются:

Y1 – средняя длина очереди (среднее количество заявок, ожидающих об-

служивания);

Y2 – среднее количество заявок в системе (в очереди плюс на обслужива-

нии);

Y3 – среднее время ожидания заявки (среднее время нахождения в очере-

ди: от момента поступления заявки до начала обслуживания);

Y4 – среднее время нахождения заявки в системе ( от момента поступле-

ния до окончания обслуживания);

Pi – вероятность того, что в системе находится i заявок (соответственно

P0 – вероятность того, что в системе нет ни одной заявки);

К – коэффициент загрузки обслуживающих каналов

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

живания сделать определенные предположения, в частности, что потоки собы-

тий, переводящие СМО из одного состояния в другое (поток заявок на обслу-

живание и поток обработки заявок) являются простейшими, а их законы рас-

пределения являются показательными (экспоненциальными), то есть проме-

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

закону распределения с параметром λ:

(t) =

λt

, а продолжительность об-

служивания распределена по показательному распределению с параметром µ:

(t) = µe

µt

, то для расчета выходных переменных СМО можно использовать

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

мости в виде расчетных формул. Отметим, что во многих практических случа-

ях реальные законы распределения случайных величин (интервала поступле-

ния заявок и продолжительности обслуживания) действительно близки к пока-

зательному распределению, поэтому представленные ниже расчетные форму-

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

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

стояния в другое, не являются простейшими, то есть не соблюдаются условия

стационарности, ординарности, отсутствия последействия, общих аналитиче-

ских методов для расчета выходных переменных таких систем не существует.

Для исследования этих СМО могут быть использованы методы имитационно-

го моделирования.

Предварительно введем еще одну вспомогательную переменную: ρ = λ/µx

Данная переменная характеризует отношение скорости поступления зая-

вок к совокупной скорости обслуживания.

6.4 Модели СМО с отказами.

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

щих каналов):

∑

Вероятность отказа в обслуживании:

отк

= ρ

/x!

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

обсл

= 1 – P

отк

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

единицу времени):

А = λ P

обсл

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

К = ρ P

обсл

/ x

6.5 Модели СМО с неограниченным временем ожидания

Для СМО с неограниченной очередью должно выполняться условие: ρ / x < 1,

в противном случае очередь будет возрастать до бесконечности и система ут-

ратит работоспособность.

Вероятность простоя всех каналов (то есть СМО в целом):

)(!!

ρρ

−

∑

xxi

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

Y1 = ρ

x+1

/ (x-1)!(x-ρ)

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

Y2 = Y1 + ρ

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

Y3 = Y1 / λ

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

Y4 = Y2 / λ

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

К = ρ

/ x

6.6 Модели замкнутых СМО

В замкнутой СМО циркулирует одно и то же конечное число потенциаль-

ных клиентов (заявок), поэтому в таких СМО кроме входных переменных λ

λλ

λ,

, ,

, µ

µµ

появляется еще одна входная переменная n – количество потенциальных

клиентов (источников заявок).

Вероятность простоя всех каналов:

!)!(!)!(

xxiniin

−

+==

−

∑∑

ρρ

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

!)!(

kkn

−

при k<x ,

!)!(

xxkn

−

при x≤k≤<n

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

Z = P

+2P

+ 3P

+… + n(P

x+1

+ … + P

)

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

A = Z µ

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

Y2 = n – Z/ρ

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

Y4 = Y2 / λ

После изучения данного раздела следует выполнить задачи 1-5 кон-

трольной работы № 6

7. МОДЕЛИ СЕТЕВОГО ПЛАНИРОВАНИЯ И УПРАВЛЕНИЯ (СПУ)

СПУ представляет собой систему методов и моделей планирования и

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

ных народно-хозяйственных комплексов, комплексных целевых программ

(например, программа подготовки к олимпиаде «Сочи-2014»), технической

подготовки производства на крупных промышленных предприятиях, планов

строительства и реконструкции жилых и промышленных комплексов и т.п.

СПУ основано на моделировании процесса с помощью построения сете-

вого графика, отображающего планируемый комплекс работ.

Система СПУ позволяет:

- формировать календарный план реализации некоторого комплекса ра-

бот;

- выявлять и мобилизовать резервы времени, трудовые, материальные ре-

сурсы и денежные ресурсы;

- осуществлять управление комплексом работ по принципу «ведущего

звена» с прогнозированием и предупреждением возможных срывов в ходе ра-

бот.

Сетевая модель представляет собой план выполнения некоторого ком-

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

сети, графическое изображение которой называется сетевым графиком. Се-

тевой график – это ориентированный граф без контуров, отражающий логиче-

скую взаимосвязь всех операций (работ).

Главными элементами сетевой модели являются события и работы.

Работа (операция) – это активный процесс, требующий затрат ресурсов

(например, сборка изделия, рытье котлована и т.п.), либо пассивный про-

цесс(ожидание) – протяженный во времени процесс, не требующий затрат ре-

сурсов (например, процесс сушки после покраски, процесс твердения бетона и

т.п.). Кроме активных и пассивных работ выделяются фиктивные работы –

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

бующие затрат времени и ресурсов.

Событие – это результат (промежуточный или конечный) выполнения

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

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

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

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

Среди событий сетевой модели выделяют исходное и завершающее со-

бытия. Исходное событие не имеет предшествующих работ и событий, отно-

сящихся к рассматриваемому комплексу работ (это событие – начало всего

комплекса работ). Завершающее событие не имеет последующих работ и со-

бытий (это событие – окончание всего комплекса работ).

События на сетевом графике изображаются кружками (вершинами графа),

и работы – стрелками (ориентированными дугами графа).

Путь – любая непрерывная последовательность (цепь) работ и событий.

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

бытием, а конец – с завершающим.

Критический путь – наиболее продолжительный полный путь в сетевом

графике. Этот путь не имеет резервов и включает самые напряженные работы

комплекса. Все остальные работы (не лежащие на критическом пути) являются

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

сроки их выполнения, не влияя на общую продолжительность работ.

Все события и работы в сетевом графике нумеруются. При этом работы

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

исходит работа, второе число – номер события, к которому приводит работа.

При построении сетевых моделей необходимо соблюдать следующие пра-

вила:

1. Сеть вычерчивается слева направо, и каждое событие с большим номе-

ром изображается правее (или на одном уровне) предыдущего. Ориентация

стрелок, изображающих работы, также в основном должна быть слева напра-

во. При этом каждая работа должна выходить из события с меньшим номером

и входить в событие с большим номером.

2. Два события могут быть объединены только одной работой. Для изо-

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

работы.

3. В сети не должно быть тупиков, то есть событий (кроме завершающе-

го), из которых не выходит ни одна работа.

4. В сети не должно быть событий (кроме исходного), которым не пред-

шествует хотя бы одна работа.

5. В сети не должно быть замкнутых контуров, состоящих из взаимосвя-

занных работ, образующих замкнутую цепь.

Отметим, что над стрелками, обозначающими работы, в сетевом графике

обычно указывается их (работ) продолжительность.

Приведем пример построения сетевого графика. П

Пусть речь идет об издании книги некоторого автора некоторым изда-

тельством. Упрощенная последовательность процессов (работ), приводящая к

реализации проекта издания книги представлена в таблице 7.1.

Таблица 7.1. Исходные данные процесса издания книги.

Процесс (работа) Предшествующие процес-

сы, которые должны быть

выполнены до начала дан-

ного

Длительность

(недели)

A: Прочтение рукописи редактором - 3

B: Пробная верстка отдельных страниц - 2

C: Разработка обложки книги - 4

D: Подготовка иллюстраций - 3

E: Просмотр автором редакторских правок

A,B 2

F: Верстка (создание макета книги) E 4

G: Проверка автором макета книги F 2

H: Проверка автором иллюстраций D 1

I: Подготовка печатных форм G,H 2

J: Печать и брошюровка книги C,I 4

Сетевой график, отображающий комплекс работ по изданию книги представ-

лен на рисунке 7.1 (Красным выделен критический путь, расчет произведен

ниже)

Рис.7.1. Сетевой график комплекса работ по изданию книги.

Расчет сетевого графика заключается в определении:

- ранних сроков свершения событий, ранних сроков начала и окончания работ;

- поздних сроков наступления событий, поздних сроков начала и окончания

работ;

- резервов времени работ и событий, критического пути.

Введем следующие обозначения:

Тi

– ранний срок наступления события i ;

Тi

– поздний срок наступления события i ;

Тij

рн

– ранний срок начала работы ij ;

Тij

ро

– ранний срок окончания работы ij ;

Тij

пн

– поздний срок начала работы ij ;

Тij

по

– поздний срок окончания работы ij ;

R i – резерв времени события i ;

R ij – резерв времени работы ij ;

tij – продолжительность выполнения работы ij .

Алгоритм расчета параметров сетевого графика состоит из следующих

основных этапов:

Этап 1. Двигаясь от исходного события к завершающему, определяются ран-

ние сроки наступления событий, ранние сроки начала и окончания работ:

1.1 Ранний срок наступления исходного события полагается равным нулю: То

= 0.

100

Ранний срок начала всех работ, исходящих из исходного события также

полагается равным нулю: Тоj

рн

= 0.

Ранний срок окончания работ, исходящих из исходного события определяется

по формуле: Тоj

ро

= Тоj

рн

+ tоj

1.2. Ранний срок наступления события j определяется по формуле:

Тj

= max { Тi

+ tij }

i<j

Ранний срок наступления события j – это самый ранний срок, к которому за-

вершаются все работы, предшествующие этому событию.

Ранний срок начала всех работ, исходящих из события j полагается рав-

ным раннему

сроку наступления события:: Тjk

рн

= Тj

Ранний срок окончания работ, исходящих из события j определяется по

формуле:

Тоj

ро

= Тоj

рн

+ tоj

Этап 2. Двигаясь от завершающего события к исходному, определяются позд-

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

2.1. Для завершающего (конечного) события поздний срок его наступления

полагается равным раннему, определенному на первом этапе:

Тk

= Тk

(здесь номером k обозначен номер завершающего события

сети)

Для всех работ, входящих в завершающее событие (то есть для работ, ре-

зультатом которых является завершающее событие сети) определяются позд-

ние сроки начала и окончания по формулам:

Тik

по

= Тk

; Тik

пн

= Тik

по

– tik .

2.2. Поздний срок наступления события i определяется по формуле:

Тi

= min { Тj

- tij }

j>i

Выбор минимального значения происходит по всем событиям {j}, кото-

рые непосредственно связаны с событием i через работы, то есть в сети есть

работа ij.

Поздний срок наступления события i – это предельный срок, когда собы-

тие может наступить, не повлияв при этом на общий срок завершения всего

комплекса работ.

Для всех работ, результатом которых является событие i, определяются

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

Тik

по

= Тk

; Тik

пн

= Тik

по

– tik .

2.3. Для всех событий и работ определяются резервы времени:

Ri = Тi

– Тi

; Rij = Тij

пн

– Тij

рн

= Тij

по

– Тij

ро

Патудин В.М., Блем А.Г. Математическая экономика

Подождите немного. Документ загружается.