Бережная_Матметоды моделирования эк cистем

оказался неработоспособным, то вновь проводится профилактика. В начальный момент все ПК компьютерной сети нуждаются в про­ филактическом осмотре.

Постройте фаф состояний для системы S (6 ПК), напишите дифференциальные уравнения для вероятностей состояний. Най­ дите вероятности состояний РДЗ) и математическое ожидание чис­ ла персональных компьютеров (Л/3), успешно прошедших профи­ лактику после трех часов с начала обслуживания (/ = 3).

2.21.Используйте условие задачи 2.20, за исключением того, что система учета предприятия применяет не шесть, а десять пер­ сональных компьютеров.

2.22.Размеченный фаф состояний в установившемся режиме для процесса гибели и размножения приведен на рис, 2.20.

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

2.23. Граф состояний системы имеет вид, приведенный на рис. 2.21.

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

Найдите вероятности состояний системы в стационарном режиме.

2.24. Рассматривается производство персональных компьюте­ ров на заводе. Поток производимых компьютеров — простейший пуассоновский с интенсивностью Л(0 = X = 1200 год~^ (число ком­ пьютеров в год).

Определите вероятность выпуска 5000 компьютеров. За четыре года работы завода вычислите характеристики процесса производ­ ства ПК m[X{t)\ и D[X{t)], при / = 4 года.

Постройте граф состояний процесса производства ПК.

80

2.25. Аудиторская фирма разрабатывает проекты отдельных до­ кументов для 6 предприятий. Поток разрабатываемых документов — простейший пуассоновский с интенсивностью Я = 2 месяца" ^ Оп­ ределите закон распределения случайного процесса X(t) — число разрабатываемых документов на момент времени t = 2 месяца, ес­ ли в момент t = О начата разработка документов.

Вычислите математическое ожидание MlX(t)] случайного про­ цесса X(t), предварительно построив размеченный граф состояний.

2.26. Размеченный граф состояний в установившемся режиме для процесса гибели и размножения приведен на рис. 2.22.

Найдите вероятности состояний.

2.27. Граф состояний системы имеет вид, приведенный на рис. 2.23.

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

Найдите вероятности состояний в стационарном режиме. 2.28. Размеченный граф состояний представлен на рис. 2.24.

Найдите вероятности состояний 5/ и характеристику Af[X(t)] на момент времени / = 3.

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

81

2.29. Размеченный граф состояний представлен на рис. 2.25. Найдите вероятности состояний Si и характеристику M{X{t)] на

момент времени / = 4.

@Ц^)^^® Kf:

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

2.30. Размеченный граф состояний представлен на рис. 2.26.

So)—/s^—-К^Г)—К?)—Кл)—Кл)—•••'

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

Найдите вероятности состояний 5/ и характеристики M[X(t)] и D[X{t)] juuit=2.

Глава 3

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

3.1. Компоненты и классификация моделей массового обслуживания

Рассмотренный в гл. 2 марковский случайный процесс с дис­ кретными состояниями и непрерывным временем имеет место в системах массового обслуживания.

Системы массового обслуживания ~ это такие системы, в кото­ рые в случайные моменты времени поступают заявки на обслужи­ вание, при этом поступившие заявки обслуживаются с помощью имеющихся в распоряжении системы каналов обслуживания.

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

82

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

Примерами систем массового обслуживания могут служить:

•посты технического обслуживания автомобилей;

•посты ремонта автомобилей;

•персональные компьютеры, обслуживающие поступающие за­ явки или требования на решение тех или иных задач;

•станции технического обслуживания автомобилей;

•аудиторские фирмы;

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

•телефонные станции и т. д.

Основными компонентами системы массового обслуживания любого вида являются:

•входной поток поступающих требований или заявок на обслу­ живание;

•дисциплина очереди;

•механизм обслуживания.

Раскроем содержание каждого из указанных выше компонентов. Для описания входного потока требований нужно задать вероят­

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

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

•первым пришел — первым обслуживаешься;

•пришел последним — обслуживаешься первым;

•случайный отбор заявок;

•отбор заявок по критерию приоритетности;

83

• ограничение времени ожидания момента наступления обслу­ живания (имеет место очередь с ограниченным временем ожида­ ния обслуживания, что ассоциируется с понятием «допустимая дли­ на очереди»).

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

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

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

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

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

•вероятностным распределением моментов поступлений за­ явок на обслуживание (единичных или групповых);

•вероятностным распределением времени продолжительности обслуживания;

•конфигурацией обслуживающей системы (параллельное, по­ следовательное или параллельно-последовательное обслуживание);

•количеством и производительностью обслуживающих каналов;

•дисциплиной очереди;

•мощностью источника требований.

84

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

•вероятность немедленного обслуживания поступившей заявки;

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

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

•средний процент заявок, получивших отказ в обслуживании;

•среднее время ожидания в очереди;

•средняя длина очереди;

•средний доход от функционирования системы в единицу бре­ мени и т. п.

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

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

Независимо от характера процесса, протекающего в системе массового обслуживания, различают два основных вида СМО:

•системы с отказами, в которых заявка, поступившая в систе­ му в момент, когда все каналы заняты, получает отказ и сразу же покидает очередь;

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

Системы массового обслуживания с ожиданием делятся на си­ стемы с ограниченным ожиданием и системы с неограниченным ожиданием.

85

всистемах с ограниченным ожиданием может ограничиваться:

•длина очереди;

•время пребывания в очереди.

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

Все системы массового обслуживания различают по числу ка­ налов обслуживания:

•одноканальные системы;

•многоканальные системы.

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

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

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

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

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

Пусть система работает с отказами. Необходимо определить абсолютную и относительную пропускную способность системы.

Представим данную систему массового обслуживания в виде графа (рис. 3.1), у которого имеются два состояния:

iSo — канал свободен (ожидание);

Si — канал занят (идет обслуживание заявки).

86

'So]

Рис. 3.1. Граф состояний одноканальной СМО с отказами

Обозначим вероятности состояний:

Ро(0 — вероятность состояния «канал свободен»; Pi(t) — вероятность состояния «канал занят».

По размеченному графу состояний (рис. 3.1) составим систему дифференциальных уравнений Колмогорова для вероятностей со­ стояний:

\dPo(t)• = -XPo(t)+nPi(ty,

Система линейных дифференциальных уравнений (3.3) имеет решение с учетом нормировочного условия 7*0(0 + Pi(t) = 1. Реше­ ние данной системы называется неустановившимся, поскольку оно непосредственно зависит от ^ и выглядит следующим образом:

Нетрудно убедиться, что для одноканальной СМО с отказами вероятность PQCO есть не что иное, как относительная пропускная способность системы д.

Действительно, PQ - вероятность того, что в момент t канал сво­ боден и заявка, пришедшая к моменту /, будет обслужена, а следо­ вательно, для данного момента времени / среднее отношение числа обслуженных заявок к числу поступивших также равно Ро(0> т. е.

По истечении большого интервала времени (при t -^ оо) дости­ гается стационарный (установившийся) режим:

87

Зная относительную пропускную способность, легко найти аб­ солютную. Абсолютная пропускная способность (А) — среднее чис­ ло заявок, которое может обслужить система массового обслужива­ ния в единицу времени:

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

Данная величина PQ^K может быть интерпретирована как сред­ няя доля необслуженных заявок среди поданных.

Пример 3.1. Пусть одноканальная СМО с отказами представ­ ляет собой один пост ежедневного обслуживания (ЕО) для мойки автомобилей. Заявка - автомобиль, прибывший в момент, когда пост занят, — получает отказ в обслуживании. Интенсивность по­ тока автомобилей Л = 1,0 (автомобиль в час). Средняя продолжи­ тельность обслуживания — 1,8 часа. Поток автомобилей и поток обслуживании являются простейшими.

Требуется определить в установившемся режиме предельные значения:

относительной пропускной способности д; абсолютной пропускной способности А; вероятности отказа Р^^^.

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

Решение

1. Определим интенсивность потока обслуживания:

li = j - = Y^ = 0,555.

'об ^>°

2.Вычислим относительную пропускную способность:

88

Величина q означает, что в установившемся режиме система бу­ дет обслуживать примерно 35% прибывающих на пост ЕО автомо­ билей.

3. Абсолютную пропускную способность определим по формуле:

/1 = Л • ^ = 1 • 0,356 = 0,356.

Это означает, что система (пост ЕО) способна осуществить в среднем 0,356 обслуживания автомобилей в час.

3. Вероятность отказа:

^отк = 1 - ^ = 1 - 0.356 = 0,644.

Это означает, что около 65% прибывших автомобилей на пост ЕО получат отказ в обслуживании.

4. Определим номинальную пропускную способность системы:

^ном ="= = 7Т = 0,555 (автомобилей в час).

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

Одноканальная CMC с ожиданием. Система массового обслужи­ вания имеет один канал. Входящий поток заявок на обслуживание

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

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

Граф состояний СМО в этом случае имеет вид, показанный на рис. 3.2.

89