Простейший поток и применение практических задач.

Нестационарные пуассоновские потоки.

Потоки с ограниченными последствиями (потоки Пальма).

Потоки восстановления.

1. Введение.

1.1. Историческая справка.

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

Первые задачи теории систем массового обслуживания (ТСМО) были рассмотрены сотрудником Копенгагенской телефонной компании, датским ученым А.К. Эрлангом (1878- 1929г) в период между 1908 и 1922гг. Эти задачи были вызваны к жизни стремлением упорядочить работу телефонной сети и разработать методы, позволяющие заранее повысить качество обслуживания потребителей в зависимости от числа используемых устройств. Оказалось, что ситуации, возникающие на телефонных станциях, являются типичными не только для телефонной связи. Работа аэродромов, морских и речных портов, магазинов, терминальных классов, электронных вычислительных комплексов, радиолокационных станций и т.д. может быть описана в рамках ТСМО.

1.2. Примеры систем массового обслуживания. Анализ задач ТСМО.

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

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

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

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

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

Задача: Обеспечить определенный объем перевозок при минимальных расходах. При этом сократить простои судов при погрузочно-разгрузочных работах.

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

Задача: Обеспечить ускорение обработки сигналов при заданной суммарной длине очереди.

Пример 5 . На рис 1.1. изображена структурная схема типичной системы массового обслуживания – ремонтного предприятия (например, по ремонту ПЭВМ). Порядок ее работы ясен из схемы и не требует разъяснений.

рис 1.1.

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

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

1. условия “двойной” случайности –

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

2)проблема бича нашего времени – очередей: судов перед шлюзами, машин перед прилавками, задач на входе процессоров вычислительного комплекса и т.д.

А.К. Эрланг обратил внимание на то, что СМО могут быть разделены на два типа, а именно: на системы с ожиданием и системы с потерями. В первом случае – заявка, поступившая на вход системы “ждет” очереди на выполнение, во втором – она из-за занятости канала обслуживания получает отказ и теряется для СМО.

В дальнейшем мы увидим, что к классическим задачам Эрланга прибавляются новые задачи:

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

1.3. Понятия, определения, терминология.

Все СМО имеют вполне определенную структуру, изображенную на рис 1.2

рис 1.2

Определения, термины

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

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

1.4.1. По характеру источника требований различают СМО с конечным и бесконечным количеством требований на входе.

В первом случае в системе циркулирует конечное, обычно постоянное количество требований, которые после завершения обслуживания возвращаются в источник.

Во втором случае источник генерирует бесконечное число требований.

Пример 1. Цех с постоянным количеством станков или определенное количество ПЭВМ в терминальном классе, требующих постоянного профилактического осмотра и ремонта.

Пример 2 . Сеть Internet с бесконечным требованием на входе, любой магазин, парикмахерская и т.д.

Первый вид СМО называют замкнутой, второй – разомкнутой.

СМО различают:

1.4.2. По дисциплине обслуживания:

1. обслуживание в порядке поступления;
2. обслуживание в случайном порядке (в соответствии с заданным законом распределения);
3. обслуживание с приоритетом.

1.4.3. по характеру организации:

1. с отказами;
2. с ожиданиями;
3. с ограничением ожидания.

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

1.4.4. По количеству единиц обслуживания:

1. одноканальные;
2. двухканальные;
3. многоканальные.

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

1.4.6. По свойствам каналов: на однородные, когда каналы имеют одинаковую характеристику и неоднородные в противном случае.

Математический (абстрактный) объект, элементами которого являются (рис. 2.1):

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

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

Рис. 2.1.

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

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

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

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

Заявка, поступившая в СМО, может находиться в двух состояниях:

• 1) обслуживания (в приборе);
• 2) ожидания (в накопителе), если все приборы заняты обслуживанием других заявок.

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

Дисциплина буферизации (дисциплина постановки в очередь) - правило занесения поступающих заявок в накопитель (буфер).

Дисциплина обслуживания - правило выбора заявок из очереди для обслуживания в приборе.

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

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

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

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

В системах ИМ при реализации СМО принимаются следующие ограничения и допущения:

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

Остановимся на некоторых элементах СМО более подробно.

Входной (входящий) поток заявок. Потоком событий называется последовательность однородных событий, следующих одно за другим и происходящих в какие-то, вообще говоря, случайные моменты времени. Если событие заключается в появлении заявок, имеем поток заявок. Для описания потока заявок в общем случае необходимо задать интервалы времени т = t k - t k-1 между соседними моментами t k _ k и t k поступления заявок с порядковыми номерами к - 1 и к соответственно (к - 1, 2, ...; t 0 - 0 - начальный момент времени).

Основной характеристикой потока заявок является его интенсивность X - среднее число заявок, поступающих на вход СМО за единицу времени. Величина т = 1/Х определяет средний интервал времени между двумя последовательными заявками.

Поток называется детерминированным, если интервалы времени т к между соседними заявками принимают определенные заранее известные значения. Если при этом интервалы одинаковы (х к = т для всех к = 1, 2, ...), то поток называется регулярным. Для полного описания регулярного потока заявок достаточно задать интенсивность потока X или значение интервала т = 1/Х.

Поток, в котором интервалы времени х к между соседними заявками представляют собой случайные величины, называется случайным. Для полного описания случайного потока заявок в общем случае необходимо задать законы распределений F fc (x fc) каждого из интервалов времени х к, к = 1,2,....

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

Случайный поток называется рекуррентным, если все интервалы времени х ь т 2 , ... между заявками распределены по одному и тому же закону F(t). Рекуррентных потоков много. Каждый закон распределения порождает свой рекуррентный поток. Рекуррентные потоки иначе называют потоками Пальма.

Если интенсивность X и закон распределения F(t) интервалов между последовательными заявками не меняются со временем, то поток заявок называется стационарнъш. В противном случае поток заявок является нестационарным.

Если в каждый момент времени t k на входе СМО может появиться только одна заявка, то поток заявок называется ординарным. Если в какой-либо момент времени может появиться более одной заявки, то поток заявок - неординарный, или групповой.

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

Стационарный ординарный поток без последействия называется простейшим.

Интервалы времени т между заявками в простейшем потоке распределены по экспоненциальному (показательному ) закону: с функцией распределения F(t) = 1 - е~ м; плотностью распределения/(f) = Хе~" л, где X > 0 - параметр распределения - интенсивность потока заявок.

Простейший поток часто называют пуассоновским. Название происходит от того, что для этого потока вероятность P fc (At) появления ровно к заявок за некоторый интервал времени At определяется законом Пуассона:

Следует заметить, что пуассоновский поток, в отличие от простейшего, может быть:

• стационарным, если интенсивность X не меняется со временем;
• нестационарным, если интенсивность потока зависит от времени: X = >.(t).

В то же время простейший поток, по определению, всегда является стационарным.

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

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

Сумма N независимых стационарных ординарных потоков с интенсивностями Х ь Х 2 ,..., X N образует простейший поток с интенсивностью

X=Y,^i при условии, что складываемые потоки оказывают более или

менее одинаково малое влияние на суммарный поток. На практике суммарный поток близок к простейшему при N > 5. Значит, при суммировании независимых простейших потоков суммарный поток будет простейшим при любом значении N.

• 2. Вероятностное разрежение потока. Вероятностное (но не детерминированное ) разрежение простейшего потока заявок, при котором любая заявка случайным образом с некоторой вероятностью р исключается из потока независимо от того, исключены другие заявки или нет, приводит к образованию простейшего потока с интенсивностью X* = рХ, где X - интенсивность исходного потока. Поток исключенных заявок с интенсивностью X** = (1 - р)Х - тоже простейший поток.
• 3. Эффективность. Если обслуживающие каналы (приборы) рассчитаны на простейший поток заявок с интенсивностью X, то обслуживание других типов потоков (с той же интенсивностью) будет обеспечено с не меньшей эффективностью.
• 4. Простота. Предположение о простейшем потоке заявок позволяет для многих математических моделей получить в явном виде зависимости показателей СМО от параметров. Наибольшее число аналитических результатов получено для простейшего потока заявок.

Анализ моделей с потоками заявок, отличными от простейших, обычно усложняет математические выкладки и не всегда позволяет получить аналитическое решение в явном виде. Свое название «простейший» поток получил именно благодаря этой особенности.

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

Важной характеристикой входного потока является коэффициент вариации

где т инт - математическое ожидание длины интервала; о - среднее квадратическое отклонение длины интервала х инт (случайной величины) .

Для простейшего потока (а =-, т = -) имеем v = 1. Для большинства

реальных потоков 0

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

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

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

где ц - интенсивность обслуживания, здесь р = _--; т 0 бсл - матема-

тическое ожидание времени обслуживания.

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

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

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

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

Способы управления потоками заявок определяются дисциплинами:

• буферизации;
• обслуживания.

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

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

Вариант классификации дисциплин буферизации (постановки в очередь) в соответствии с перечисленными признаками представлен на рис. 2.2.

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

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

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

Рис. 2.2.

Дисциплины буферизации могут использовать следующие правила вытеснения заявок из накопителя:

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

На рис. 2.3 представлена классификация дисциплин обслуживания заявок в соответствии с теми же признаками, что и для дисциплин буферизации.

Иногда емкость накопителя в моделях полагают неограниченной, хотя в реальной системе она ограничена. Такое допущение оправдано, когда вероятность потери заявки в реальной системе из-за переполнения емкости накопителя меньше 10 _3 . В этом случае дисциплина практически не влияет на показатели обслуживания заявок.

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

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

• одиночного режима;
• группового режима;
• комбинированного режима.

Рис. 2.3.

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

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

Комбинированный режим - комбинация одиночного и группового режимов, когда часть очередей заявок обрабатывается в одиночном режиме, а другая часть - в групповом.

Дисциплины обслуживания могут использовать следующие правила выбора заявок на обслуживание.

Бесприоритетные (заявки не имеют привилегий на досрочное обслуживание - захват ресурсов):

• обслуживание в порядке поступления FIFO (first in -first out, первый вошел - первый вышел);
• обслуживание в обратном порядке - заявка выбирается из очереди в режиме LIFO (last in - first out, последний вошел - первый вышел);
• обслуживание в случайном порядке - заявка выбирается из очереди в режиме RAND (random - случайным образом);
• обслуживание в циклическом порядке - заявки выбираются в процессе циклического опроса накопителей в последовательности 1, 2,Н СН - количество накопителей), после чего указанная последовательность повторяется;

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

• с относительными приоритетами - если в процессе текущего обслуживания заявки в систему поступают заявки с более высокими приоритетами, то обслуживание текущей даже бесприоритетной заявки не прерывается, а поступившие заявки направляются в очередь; относительные приоритеты играют роль только в момент окончания текущего обслуживания заявки при выборе из очереди новой заявки на обслуживание.
• с абсолютными приоритетами - при поступлении заявки с высоким приоритетом обслуживание заявки с низким приоритетом прерывается и на обслуживание направляется поступившая заявка; прерванная заявка может быть возвращена в очередь или удалена из системы; если заявка возвращена в очередь, то ее дальнейшее обслуживание может быть выполнено с прерванного места или заново;
• со смешанными приоритетами - строгие ограничения на время ожидания в очереди на обслуживание отдельных заявок требуют присвоения им абсолютных приоритетов; вследствие этого время ожидания заявок с низкими приоритетами может оказаться недопустимо большим, хотя отдельные заявки имеют запас по времени ожидания; для выполнения ограничений по всем видам заявок можно наряду с абсолютными приоритетами некоторым заявкам присвоить относительные приоритеты, а остальные обслуживать в бесприоритетном режиме;
• с чередующимися приоритетами - аналогом относительных приоритетов, приоритет учитывается только в моменты завершения текущего обслуживания группы заявок одной очереди и назначения новой группы на обслуживание;
• обслуживание по расписанию - заявки разных классов (находящиеся в разных накопителях) выбираются на обслуживание согласно некоторому расписанию, задающему последовательность опроса очередей заявок, например в случае трех классов заявок (накопителей) расписание может иметь вид {2, 1, 3, 3, 1, 2} или {1, 2, 3, 3, 2, 1}.

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

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

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

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

Для математического описания дисциплин обслуживания со смешанными приоритетами используется матрица приоритетов, представляющая собой квадратную матрицу Q = (q, ;), i,j - 1,..., Я, Я - число классов заявок, поступающих в систему.

Элемент q (j матрицы задает приоритет заявок класса i по отношению к заявкам класса; и может принимать следующие значения:

• 0 - нет приоритета;
• 1 - приоритет относительный;
• 2 - приоритет абсолютный.

Элементы матрицы приоритетов должны удовлетворять следующим требованиям:

• q n = 0, так как между заявками одного и того же класса не могут быть установлены приоритеты;
• если q (j = 1 или 2, то q ^ = 0, так как если заявки класса i имеют приоритет к заявкам класса j, то последние не могут иметь приоритет к заявкам класса i (i,j = 1, ..., Я).

В зависимости от возможности изменения приоритетов в процессе функционирования системы приоритетные дисциплины буферизации и обслуживания делятся на два класса:

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

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

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

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

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

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

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

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

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

Рис. 2.4.

СеМО называют также многофазными СМО.

Пример построения ИМ СеМО мы рассмотрим позже.

Основными элементами СеМО являются узлы (У) и источники (генераторы) заявок (Г).

Узел сети - это система массового обслуживания.

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

Для упрощенного изображения СеМО используется граф.

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

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

Для лучшего восприятия этого творческого потенциала в первом приближении остановимся на классификации моделей СМО.

Рисунок 0 - 2 Потоки событий (а) и простейший поток (б)

10.5.2.1. Стационарность

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

Рисунок 0-2 , а) зависит только от длины участка и не зависит от того, где именно на оси t расположен этот участок.

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

На практике часто встречаются потоки событий, которые (по крайней мере, на ограниченном участке времени) могут рассматриваться как стационарные. Например, поток вызовов, поступающих на телефонную станцию, скажем, на интервале от 12 до 13 часов может считаться стационарным. Тот же поток в течение целых суток уже не будет стационарным (ночью интенсивность потока вызовов гораздо меньше, чем днем). Заметим, что так же обстоит дело и с большинством физических процессов, которые мы называем «стационарными» в действительности они стационарны только на ограниченном участке времени, а распространение этого участка до бесконечности лишь удобный прием, применяемый в целях упрощения.

10.5.2.2. Отсутствие последействия

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

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

Рассмотрим, например, поток грузовых поездов, идущих по железнодорожной ветке. Если по условиям безопасности они не могут следовать один за другим чаще, чем через интервал времени t 0 , то между событиями в потоке имеется зависимость, и условие отсутствия последействия нарушается. Однако, если интервал t 0 мал по сравнению со средним интервалом между поездами, то такое нарушение несущественно.

Рисунок 0 - 3 Распределение Пуассона

Рассмотрим на оси t простейший поток событий с интенсивностью λ. (Рисунок 0-2 б). Нас будет интересовать случайный интервал времени Т между соседними событиями в этом потоке; найдем его закон распределения. Сначала найдем функцию распределения:

F(t) = P(T (0-2)

т. е. вероятность того, что величина Т будет иметь значение, меньшее, чем t . Отложим от начала интервала Т (точки t 0 ) отрезок t и найдем вероятность того, что интервал Т будет меньше t . Для этого нужно, чтобы на участок длины t , примыкающий к точке t 0 , попало хотя бы одно событие потока. Вычислим вероятность этого F (t ) через вероятность противоположного события (на участок t не попадет ни одного события потока):

F (t ) = 1 - Р0

Вероятность Р 0 найдем по формуле (1), полагая m = 0:

откуда функция распределения величины Т будет:

(0-3)

Чтобы найти плотность распределения f (t ) случайной величины Т, необходимо продифференцировать выражение (0‑1) по t :

0-4)

Закон распределения с плотностью (0‑4) называется показательным (или экспоненциальным). Величина λ называется параметром показательного закона.

Рисунок 0 - 4 Экспоненциальное распределение

Найдем числовые характеристики случайной величины Т - математическое ожидание (среднее значение) M [ t ]= m t , и дисперсию D t . Имеем

( 0-5)

(интегрируя по частям) .

Дисперсия величины Т составляет:

(0-6)

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

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

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

Пример СМО- 1 .

В качестве примера рассмотрим банковскую систему, работающую в реальном масштабе времени и обслуживающую большое число клиентов. В часы пик запросы от кассиров банка, работающих с клиентами, образуют пуассоновский поток и поступают в среднем по два в 1 с (λ = 2).Поток состоит из заявок, поступающих с интенсивностью 2 заявки в секунду.

Рассчитаем вероятность Р (m ) появления m сообщений в 1 с. Так как λ = 2, то из предыдущей формулы имеем

Подставляя m = 0, 1, 2, 3, получим следующие величины (с точностью до четырех десятичных знаков):

Рисунок 0 - 5 Пример простейшего потока

Возможно поступление и более 9 сообщений в 1 с, но вероятность этого очень мала (около 0,000046).

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

Пример СМО- 2 .

Прибор (сервер), обрабатывающей три сообщения в 1с.

Пусть имеется оборудование, которое может обрабатывать три сообщения в 1 с (µ=3). Поступает всреднем два сообщения в 1с, причем в соответствии c распределением Пуассона. Какая часть этих сообщений будет обрабатываться сразу же после поступления?

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

Если система может обрабатывать максимум 3 сообщения в 1 с, то вероятность того, что она не будет перегружена, равна

Другими словами, 85,71% сообщений будут обслуживаться немедленно, а 14,29% с некоторой задержкой. Как видим, задержка в обработке одного сообщения на время, большее времени обработки 3 сообщений, будет встречаться редко. Время обработки 1сообщения составляет в среднем 1/3 с. Следовательно, задержка более 1с будет редким явлением, что вполне приемлемо для большинства систем.

Пример СМО- 3

· Если кассир банка занят в течение 80% своего рабочего времени, а остальное время он тратит на ожидание клиентов, то его можно рассматривать как устройство с коэффициентом использования 0,8.

· Если канал связи используется для передачи 8-битовых символов со скоростью 2400 бит/с, т. е. передается максимум 2400/8 символов в 1 с, и мы строим систему, в которой суммарный объем данных составляет 12000 символов, посылаемых от различных устройств через канал связи в минуту наибольшей нагрузки (включая синхронизацию, символы конца сообщений, управляющие и т. д.), то коэффициент использования оборудования канала связи в течение этой минуты равен

· Если механизм доступа к файлу в час наибольшей нагрузки осуществляет 9000 обращений к файлу, а время одного обращения равно в среднем 300 мс, то коэффициент использования оборудования механизма доступа в час наибольшей нагрузки составляет

Понятие коэффициента использования оборудования будет использоваться довольно часто. Чем ближе коэффициент использования оборудования к 100%, тем больше задержки и длиннее очереди.

Используя предыдущую формулу, можно составить таблицы значений функции Пуассона, по которым можно определить вероятность поступления m или более сообщений в данный отрезок времени. Например, если в среднем поступает 3,1 сообщения в секунду [т. е. λ = 3,1], то вероятность поступления 5 и более сообщений в данную секунду равна 0,2018 (для m = 5 в таблице). Или в аналитическом виде

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

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

ρ ≤ 0,9

Эти значения можно получить с помощью таблиц Пуассона.

Пусть снова средняя скорость поступления сообщений λ = 3,1 сообщения/с. Из таблиц следует, что вероятность поступления 6 или более сообщений в 1 с равна 0,0943. Следовательно, это число можно взять в качестве критерия нагрузки для проведения начальных расчетов.

10.6.2. Задачи проектирования

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

Чем больше коэффициент использования оборудования, тем длиннее возникающие очереди. Как будет показано ниже, можно спроектировать удовлетворительно работающую систему с коэффициентом использований ρ =0,7 но коэффициент, превышающий ρ > 0,9, может привести к ухудшению качества обслуживания. Другими словами, если канал пересылки массива данных имеет загрузку 20%, вряд ли на нем возникнет очередь. Если же загрузка; составляет 0,9, то, как правило, будут образовываться очереди, иногда очень большие.

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

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

· Какова длина очереди?

· Сколько времени на нее будет затрачиваться?

На вопросы подобного типа можно ответить с помощью теории очередей.

10.6.3. Системы массового обслуживания, их классы и основные характеристики

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

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

СМО классифицируются на системы с:

· отказами (с потерями). В таких системах заявка, поступившая в момент, когда все каналы заняты, получает «отказ», покидает СМО и в дальнейшем процессе обслуживания не участвует.

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

Обслуживание (дисциплина очереди) в системе с ожиданием может быть

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

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

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

· Приоритетным

o со статическим приоритетом

o с динамическим приоритетом

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

Системы с очередью делятся на системы

· с неограниченным ожиданием и

· с ограниченным ожиданием.

В системах с неограниченным ожиданием каждая заявка, поступившая в момент, когда нет свободных каналов, становится в очередь и «терпеливо» ждет освобождения канала, который примет ее к обслуживанию. Любая заявка, поступившая в СМО, рано или поздно будет обслужена.

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

· длины очереди (числа заявок, одновременно находящихся в очереди система с ограниченной длиной очереди),

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

· общего времени пребывания заявки в СМО

и т. д.

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

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

Помимо абсолютной и относительной пропускной способностей при анализе СМО с отказами нас могут, в зависимости от задачи исследования, интересовать и другие характеристики, например:

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

· среднее относительное время простоя системы в целом и отдельного канала

и т. д.

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

· среднее число заявок в очереди;

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

· среднее время ожидания заявки в очереди;

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

а также и другие характеристики ожидания.

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

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

В зависимости от значений этих параметров выражаются характеристики эффективности работы СМО.

10.6.4. Формулы расчета характеристик СМО для случая обслуживания с одним прибором

Рисунок 0 - 6 Модель системы массового обслуживания с очередью

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

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

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

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

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

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

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

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

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

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

Рассмотрим следующий пример. Имеется шесть типов сообщений с временами обслуживания 15, 20, 25, 30, 35 и 300. Число сообщений каждого типа одинаково. Стандартное отклонение указанных времен несколько выше их среднего. Значение последнего времени обслуживания намного больше других. Это приведет к тому, что сообщения будут находиться в очереди значительно дольше, чем, если бы времена обслуживания были одного порядка. В таком случае при проектировании целесообразно принять меры для уменьшения длины очереди. Например, если указанные цифры связаны с длинами сообщений, то, возможно, очень длинные сообщения стоит разделить на части.

10.6.6. Пример расчета

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

Время ответа системы и его стандартное отклонение рассчитаны с учетом времени ввода данных с АРМа, печатания и оформления документа.

Действия кассира были прохронометрированы. Время обслуживания ts равно общему времени, затрачиваемому кассиром на клиента. Коэффициент использования кассира ρ пропорционален времени его занятости. Если λ число клиентов в часы пик, то ρ для кассира равно

Предположим, что в часы пик приходит 30 клиентов в час. В среднем кассир тратит 1,5 мин на клиента. Тогда

ρ =(1,5 * 30) / 60 = 0,75

т. е. кассир используется на 75%.

Число людей в очереди можно быстро оценить с помощью графиков. Из них следует, что если ρ = 0,75, то среднее число nq людей в очереди у кассы лежит между 1,88 и 3,0 в зависимости от стандартного отклонения для t s .

Предположим, что измерение стандартного отклонения для t s дало величину 0,5 мин. Тогда

σ s = 0,33 t s

Из графика на первом рисунке находим, что nq = 2,0, т. е. в среднем у кассы буду ожидать два клиента.

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

t ∑ = t q + t s = 2,5 мин + 1,5 мин=4мин

где t s вычисляется с помощью формулы Хинчина-Полачека.

10.6.7. Фактор усиления

Анализируя кривые, изображенные на рисунках, мы видим, что, когда оборудование, обслуживающее очередь, используется более чем на 80%, кривые начинают расти с угрожающей быстротой. Этот факт очень важен при проектировании систем передачи данных. Если мы проектируем систему, в которой оборудование используется более чем на 80%, то незначительное увеличение трафика может привести к резкому спаду производительности системы или даже заставить ее работать в аварийном режиме.

Увеличение входного трафика на небольшое число х%. приводит к увеличению размеров очереди приблизительно на

Если коэффициент использования оборудования равен 50%, то это увеличение равно 4ts % для экспоненциального закона распределения времени обслуживания. Но если коэффициент использования оборудования равен 90%, то увеличение размера очереди равно 100ts %, что в 25 раз больше. Незначительное увеличение нагрузки при 90%-ном использовании оборудования приводит к 25-кратному увеличению размеров очереди по сравнению со случаем 50%-ного использования оборудования.

Аналогично время пребывания в очереди увеличивается на

При экспоненциально распределенном времени обслуживания эта величина имеет значение 4 t s 2 для коэффициента использования оборудования, равного 50%, и 100 t s 2 для коэффициента 90%, т. е. снова в 25 раз хуже.

Кроме того, для малых коэффициентов использования оборудования влияние изменений σs на размер очереди незначительно. Однако для больших коэффициентов изменение σ s сильно сказывается на размере очереди. Поэтому при проектировании систем с высоким коэффициентом использования оборудования желательно получить точные сведения о параметре σ s . Неточность предположения относительно экспоненциальности распределения t s наиболее ощутима при больших значениях ρ. Более того, если вдруг время обслуживания возрастет, что возможно в каналах связи при передаче длинных сообщений, то в случае большого ρ образуется значительная очередь.

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

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

Вы можете заказать решение своих задач и контрольных работ по разным темам теории систем массового обслуживания в МатБюро: (Решение задач по экономико-математическим методам на заказ). Стоимость выполнения от 200 рублей, срок от 2 дней, оформление подробное в Word с графиками и выводами.

Бесплатные примеры решений по СМО (системы массового обслуживания)

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

Задача 2. Система массового обслуживания - билетная касса с одним окошком и неограниченной очередью. Касса продает билеты в пункты А и В. Пассажиров, желающих купить билет в пункт А, приходит в среднем трое за 20 мин, в пункт В - двое за 20 мин. Поток пассажиров простейший. Кассир в среднем обслуживает трех пассажиров за 10 мин. Время обслуживания - показательное. Вычислить финальные вероятности Р0, P2, P3, среднее число заявок в системе и в очереди, среднее время пребывания заявки в системе, среднее время пребывания заявки в очереди.

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

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

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

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

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

Таблица 30.1. Примеры систем массового обслуживания

СМО	Заявки	Каналы
Автобусный маршрут и перевозка пассажиров	Пассажиры	Автобусы
Производственный конвейер по обработке деталей	Детали, узлы	Станки, склады
Влетающая на чужую территорию эскадрилья самолетов, которая «обслуживается» зенитками ПВО	Самолеты	Зенитные орудия, радары, стрелки, снаряды
Ствол и рожок автомата, которые «обслуживают» патроны	Патроны	Ствол, рожок
Электрические заряды, перемещающиеся в некотором устройстве	Заряды	Каскады технического устройства

Но все эти системы объединены в один класс СМО, поскольку подход к их изучению един. Он состоит в том, что, во-первых , с помощью генератора случайных чисел разыгрываются случайные числа, которые имитируют СЛУЧАЙНЫЕ моменты появления заявок и время их обслуживания в каналах. Но в совокупности эти случайные числа, конечно, подчинены статистическим закономерностям.

К примеру, пусть сказано: «заявки в среднем приходят в количестве 5 штук в час». Это означает, что времена между приходом двух соседних заявок случайны, например: 0.1; 0.3; 0.1; 0.4; 0.2, как это показано на рис. 30.1 , но в сумме они дают в среднем 1 (обратите внимание, что в примере это не точно 1, а 1.1 — но зато в другой час эта сумма, например, может быть равной 0.9); и только за достаточно большое время среднее этих чисел станет близким к одному часу.

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

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

Рис. 30.2. Схема статистического эксперимента для изучения систем массового обслуживания

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

Перечислим некоторые основные понятия СМО.

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

Очереди характеризуются правилами стояния в очереди (дисциплиной обслуживания), количеством мест в очереди (сколько клиентов максимум может находиться в очереди), структурой очереди (связь между местами в очереди). Бывают ограниченные и неограниченные очереди. Перечислим важнейшие дисциплины обслуживания. FIFO (First In, First Out — первым пришел, первым ушел): если заявка первой пришла в очередь, то она первой уйдет на обслуживание. LIFO (Last In, First Out — последним пришел, первым ушел): если заявка последней пришла в очередь, то она первой уйдет на обслуживание (пример — патроны в рожке автомата). SF (Short Forward — короткие вперед): в первую очередь обслуживаются те заявки из очереди, которые имеют меньшее время обслуживания.

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

Пусть имеется два магазина. В магазине № 1 обслуживание осуществляется в порядке очереди, то есть здесь реализована дисциплина обслуживания FIFO (см. рис. 30.3 ).

Рис. 30.3. Организация очереди по дисциплине FIFO

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

В магазине № 2 реализована дисциплина SF (см. рис. 30.4 ), означающая, что штучный товар можно купить вне очереди, так как время обслуживания t обслуж. такой покупки невелико.

Рис. 30.4. Организация очереди по дисциплине SF

Как видно из обоих рисунков, последний (пятый) покупатель собирается приобрести штучный товар, поэтому время его обслуживания невелико — 0.5 минут. Если этот покупатель придет в магазин № 1, он будет вынужден выстоять в очереди целых 8 минут, в то время как в магазине № 2 его обслужат сразу же, вне очереди. Таким образом, среднее время обслуживания каждого из покупателей в магазине с дисциплиной обслуживания FIFO составит 4 минуты, а в магазине с дисциплиной обслуживания КВ — лишь 2.8 минуты. А общественная польза, экономия времени составит: (1 – 2.8/4) · 100% = 30 процентов! Итак, 30% сэкономленного для общества времени — и это лишь за счет правильного выбора дисциплины обслуживания.

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

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

Судить о результатах работы СМО можно по показателям . Наиболее популярные из них:

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

Судить о качестве полученной системы нужно по совокупности значений показателей. При анализе результатов моделирования (показателей) важно также обращать внимание на интересы клиента и интересы владельца системы , то есть минимизировать или максимизировать надо тот или иной показатель, а также на степень их выполнения. Заметим, что чаще всего интересы клиента и владельца между собой не совпадают или совпадают не всегда. Показатели будем обозначать далее H = {h 1 , h 2 , …} .

Параметрами СМО могут быть: интенсивность потока заявок, интенсивность потока обслуживания, среднее время, в течение которого заявка готова ожидать обслуживания в очереди, количество каналов обслуживания, дисциплина обслуживания и так далее. Параметры — это то, что влияет на показатели системы. Параметры будем обозначать далее как R = {r 1 , r 2 , …} .

Пример. Автозаправочная станция (АЗС) .

1. Постановка задачи . На рис. 30.5 приведен план АЗС. Рассмотрим метод моделирования СМО на ее примере и план ее исследования. Водители, проезжая по дороге мимо АЗС по дороге, могут захотеть заправить свой автомобиль. Хотят обслужиться (заправить машину бензином) не все автомобилисты подряд; допустим, что из всего потока машин на заправку в среднем заезжает 5 машин в час.

Рис. 30.5. План моделируемой АЗС

На АЗС две одинаковые колонки, статистическая производительность каждой из которых известна. Первая колонка в среднем обслуживает 1 машину в час, вторая в среднем — 3 машины в час. Владелец АЗС заасфальтировал для машин место, где они могут ожидать обслуживания. Если колонки заняты, то на этом месте могут ожидать обслуживания другие машины, но не более двух одновременно. Очередь будем считать общей. Как только одна из колонок освободится, то первая машина из очереди может занять ее место на колонке (при этом вторая машина продвигается на первое место в очереди). Если появляется третья машина, а все места (их два) в очереди заняты, то ей отказывают в обслуживании, так как стоять на дороге запрещено (см. дорожные знаки около АЗС). Такая машина уезжает прочь из системы навсегда и как потенциальный клиент является потерянной для владельца АЗС. Можно усложнить задачу, рассмотрев кассу (еще один канал обслуживания, куда надо попасть после обслуживания в одной из колонок) и очередь к ней и так далее. Но в простейшем варианте очевидно, что пути движения потоков заявок по СМО можно изобразить в виде эквивалентной схемы, а добавив значения и обозначения характеристик каждого элемента СМО, получаем окончательно схему, изображенную на рис. 30.6 .

Рис. 30.6. Эквивалентная схема объекта моделирования

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

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

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

В этой формуле величина потока λ должна быть задана (до этого она должна быть определена экспериментально на объекте как статистическое среднее), r — случайное равномерно распределенное число от 0 до 1 из ГСЧ или таблицы , в которой случайные числа нужно брать подряд (не выбирая специально).

Задача . Сгенерируйте поток из 10 случайных событий с интенсивностью появления событий 5 шт/час.

Решение задачи . Возьмем случайные числа, равномерно распределенные в интервале от 0 до 1 (см. таблицу), и вычислим их натуральные логарифмы (см. табл. 30.2).

Формула пуассоновского потока определяет расстояние между двумя случайными событиями следующим образом: t = –Ln(r рр)/λ . Тогда, учитывая, что λ = 5 , имеем расстояния между двумя случайными соседними событиями: 0.68, 0.21, 0.31, 0.12 часа. То есть события наступают: первое — в момент времени t = 0 , второе — в момент времени t = 0.68 , третье — в момент времени t = 0.89 , четвертое — в момент времени t = 1.20 , пятое — в момент времени t = 1.32 и так далее. События — приход заявок отразим на первой линейке (см. рис. 30.7 ).

Рис. 30.7. Временная диаграмма работы СМО

Берется первая заявка и, так как в этот момент каналы свободны, устанавливается на обслуживание в первый канал. Заявка 1 переносится на линейку «1 канал».

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

где роль интенсивности играет величина потока обслуживания μ 1 или μ 2 , в зависимости от того, какой канал обслуживает заявку. Находим на диаграмме момент окончания обслуживания, откладывая сгенерированное время обслуживания от момента начала обслуживания, и опускаем заявку на линейку «Обслуженные».

Заявка прошла в СМО весь путь. Теперь можно, согласно принципу последовательной проводки заявок, также проимитировать путь второй заявки.

Если в некоторый момент окажется, что оба канала заняты, то следует установить заявку в очередь. На рис. 30.7 это заявка с номером 3. Заметим, что по условиям задачи в очереди в отличие от каналов заявки находятся не случайное время, а ожидают, когда освободится какой-то из каналов. После освобождения канала заявка поднимается на линейку соответствующего канала и там организуется ее обслуживание.

Если все места в очереди в момент, когда придет очередная заявка, будут заняты, то заявку следует отправить на линейку «Отказанные». На рис. 30.7 это заявка с номером 6.

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

Анализ временной диаграммы

Анализ проведем на уже рассмотренном примере.

Сначала нужно дождаться установившегося режима. Откидываем первые четыре заявки как нехарактерные, протекающие во время процесса установления работы системы. Измеряем время наблюдения, допустим, что в нашем примере оно составит T н = 5 часов. Подсчитываем из диаграммы количество обслуженных заявок N обс. , времена простоя и другие величины. В результате можем вычислить показатели, характеризующие качество работы СМО.

1. Вероятность обслуживания: P обс. = N обс. /N = 5/7 = 0.714 . Для расчета вероятности обслуживания заявки в системе достаточно разделить число заявок, которым удалось обслужиться за время T н (см. линейку «Обслуженные») N обс. , на число заявок N , которые хотели обслужиться за это же время. Как и раньше вероятность экспериментально определяем отношением свершившихся событий к общему числу событий, которые могли совершиться!
2. Пропускная способность системы: A = N обс. /T н = 7/5 = 1.4 [шт/час] . Для расчета пропускной способности системы достаточно разделить число обслуженных заявок N обс. на время T н , за которое произошло это обслуживание (см. линейку «Обслуженные»).
3. Вероятность отказа: P отк. = N отк. /N = 3/7 = 0.43 . Для расчета вероятности отказа заявке в обслуживании достаточно разделить число заявок N отк. , которым отказали за время T н (см. линейку «Отказанные»), на число заявок N , которые хотели обслужиться за это же время, то есть поступили в систему. Обратите внимание . P отк. + P обс. в теории должно быть равно 1. На самом деле экспериментально получилось, что P отк. + P обс. = 0.714 + 0.43 = 1.144 . Эта неточность объясняется тем, что время наблюдения T н мало и статистика накоплена недостаточная для получения точного ответа. Погрешность это показателя сейчас составляет 14%!
4. Вероятность занятости одного канала: P 1 = T зан. /T н = 0.05/5 = 0.01 , где T зан. — время занятости только одного канала (первого или второго). Измерениям подлежат временные отрезки, на которых происходят определенные события. Например, на диаграмме ищутся такие отрезки, во время которых заняты или первый или второй канал. В данном примере есть один такой отрезок в конце диаграммы длиной 0.05 часа. Доля этого отрезка в общем времени рассмотрения (T н = 5 часов) определяется делением и составляет искомую вероятность занятости.
5. Вероятность занятости двух каналов: P 2 = T зан. /T н = 4.95/5 = 0.99 . На диаграмме ищутся такие отрезки, во время которых одновременно заняты и первый, и второй канал. В данном примере таких отрезков четыре, их сумма равна 4.95 часа. Доля продолжительности этих события в общем времени рассмотрения (T н = 5 часов) определяется делением и составляет искомую вероятность занятости.
6. Среднее количество занятых каналов: N ск = 0 · P 0 + 1 · P 1 + 2 · P 2 = 0.01 + 2 · 0.99 = 1.99 . Чтобы подсчитать, сколько каналов занято в системе в среднем, достаточно знать долю (вероятность занятости одного канала) и умножить на вес этой доли (один канал), знать долю (вероятность занятости двух каналов) и умножить на вес этой доли (два канала) и так далее. Полученная цифра 1.99 говорит о том, что из возможных двух каналов в среднем загружено 1.99 канала. Это высокий показатель загрузки, 99.5%, система хорошо использует ресурс.
7. Вероятность простоя хотя бы одного канала: P * 1 = T простоя1 /T н = 0.05/5 = 0.01 .
8. Вероятность простоя двух каналов одновременно: P * 2 = T простоя2 /T н = 0 .
9. Вероятность простоя всей системы: P * c = T простоя сист. /T н = 0 .
10. Среднее количество заявок в очереди: N сз = 0 · P 0з + 1 · P 1з + 2 · P 2з = 0.34 + 2 · 0.64 = 1.62 [шт] . Чтобы определить среднее количество заявок в очереди, надо определить отдельно вероятность того, что в очереди будет одна заявка P 1з , вероятность того, в очереди будет стоять две заявки P 2з и т. д. и снова с соответствующими весами их сложить.
11. Вероятность того, что в очереди будет одна заявка: P 1з = T 1з /T н = 1.7/5 = 0.34 (всего на диаграмме четырех таких отрезка, в сумме дающих 1.7 часа).
12. Вероятность того, в очереди будет стоять одновременно две заявки: P 2з = T 2з /T н = 3.2/5 = 0.64 (всего на диаграмме три таких отрезка, в сумме дающих 3.25 часа).
13. Среднее время ожидания заявки в очереди:

    

    (Сложить все временные интервалы, в течение которых какая-либо заявка находилась в очереди, и разделить на количество заявок). На временной диаграмме таких заявок 4.

14. Среднее время обслуживания заявки:

    

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

15. Среднее время нахождения заявки в системе: T ср. сист. = T ср. ож. + T ср. обсл. .
16. Среднее количество заявок в системе:

    

    Разобьем интервал наблюдения, например, на десятиминутки. Получится на пяти часах K подынтервалов (в нашем случае K = 30 ). В каждом подынтервале определим по временной диаграмме, сколько заявок в этот момент находится в системе. Смотреть надо на 2, 3, 4 и 5-ю линейки — какие из них заняты в данный момент. Затем сумму K слагаемых усреднить.

Далее следует оценить точность каждого из полученных результатов. То есть ответить на вопрос: насколько мы можем доверять этим значениям? Оценка точности проводится по методике, описанной в лекции 34 .

Если точность не является удовлетворительной, то следует увеличить время эксперимента и тем самым улучшить статистику. Можно сделать и по-другому. Снова несколько раз запустить эксперимент на время T н . А в последствии усреднить значения этих экспериментов. И снова проверить результаты на критерий точности. Эту процедуру следует повторять до тех пор, пока не будет достигнута требуемая точность.

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

Таблица 30.3. Показатели СМО

Показатель	Формула	Значение	Интересы владельца СМО	Интересы клиента СМО
Вероятность обслуживания	P обс. = N обс. /N	0.714	Вероятность обслуживания мала, много клиентов уходят из системы неудовлетворенными, их деньги для владельца потеряны. Это «минус».	Вероятность обслуживания мала, каждый третий клиент хочет, но не может обслужиться. Это «минус».
Среднее количество заявок в очереди	N сз = 0 · P 0з + 1 · P 1з + 2 · P 2з	1.62	Очередь практически все время вся забита. Все места в очереди используются достаточно эффективно. Вложения на организацию очереди окупают затраты на нее. Это «плюс». Клиенты, которые долго стоят в очереди, могут уйти, не дождавшись обслуживания. Клиенты, простаивая, могут нанести ущерб системе, ломать оборудование. Много отказов, потерянных клиентов. Это «минусы».	Очередь практически все время вся забита. Клиенту приходится стоять в очереди, прежде чем он попадет на обслуживание. Клиент может не попасть даже в очередь. Это «минус».
Общий итог:			В интересах владельца: а) увеличить пропускную способность каналов, чтобы не терять клиентов (правда, модернизация каналов стоит денег); б) увеличить число мест в очереди (это тоже стоит денег), чтобы задержать потенциальных клиентов.	Клиенты заинтересованы в значительном увеличении пропускной способности для уменьшения времени ожидания и уменьшения отказов.

Синтез СМО

Мы проделали анализ существующей системы. Это дало возможность увидеть ее недостатки и определить направления улучшения ее качества. Но остаются непонятными ответы на конкретные вопросы, что именно надо сделать — увеличивать количество каналов или увеличивать их пропускную способность, или увеличивать количество мест в очереди, и, если увеличивать, то насколько? Есть и такие вопросы, что лучше — создать 3 канала с производительностью 5 шт/час или один с производительностью 15 шт/час?

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

Например, для 12 показателей нашего примера можно получить 12 зависимостей от одного параметра: зависимость вероятности отказов P отк. от количества мест в очереди (КМО), зависимость пропускной способности A от количества мест в очереди, и так далее (см. рис. 30.8 ).

Рис. 30.8. Примерный вид зависимостей показателей от параметров СМО

Затем так же можно снять еще 12 зависимостей показателей P от другого параметра R , зафиксировав остальные параметры. И так далее. Образуется своеобразная матрица зависимостей показателей P от параметров R , по которой можно провести дополнительный анализ о перспективах движения (улучшения показателей) в ту или иную сторону. Наклон кривых хорошо показывает чувствительность, эффект от движения по определенному показателю. В математике эту матрицу называют якобианом J , в которой роль наклона кривых играют значения производных ΔP i /ΔR j , см. рис. 30.9 . (Напомним, что производная связана геометрически с углом наклона касательной к зависимости.)

Рис. 30.9. Якобиан — матрица чувствительностей показателей
в зависимости от изменения параметров СМО

Если показателей 12, а параметров, например, 5, то матрица имеет размерность 12 x 5. Каждый элемент матрицы — кривая, зависимость i -го показателя от j -го параметра. Каждая точка кривой — среднее значение показателя на достаточно представительном отрезке T н или усреднено по нескольким экспериментам.

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

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

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

Поэтому сейчас обсудим только первый вопрос. Как принять решение, каким должно быть все-таки значение параметра, если с его ростом показатель все время монотонно улучшается? Вряд ли значение бесконечности устроит инженера.

Параметр R — управление, это то, что находится в распоряжении владельца СМО (например, возможность заасфальтировать площадку и тем самым увеличить количество мест в очереди, поставить дополнительные каналы, увеличить поток заявок за счет увеличения затрат на рекламу и так далее). Меняя управление, можно влиять на значение показателя P , цель, критерий (вероятность отказов, пропускную способность, среднее время обслуживания и так далее). Из рис. 30.10 видно, что если увеличивать управление R , то можно добиться всегда улучшение показателя P . Но очевидно, что любое управление связано с затратами Z . И чем больше прилагают усилия для управления, чем больше значение управляющего параметра, тем больше затраты. Обычно затраты на управление растут линейно: Z = C 1 · R . Хотя встречаются случаи, когда, например, в иерархических системах, они растут экспоненциально, иногда — обратно экспоненциально (скидки за опт) и так далее.

Рис. 30.10. Зависимость показателя Р
от управляемого параметра R (пример)

В любом случае ясно, что когда-то вложение все новых затрат просто перестанет себя окупать. Например, эффект от заасфальтированной площадки размером в 1 км 2 вряд ли окупит затраты владельца бензоколонки в Урюпинске, там просто не будет столько желающих заправиться бензином. Иными словами показатель P в сложных системах не может расти бесконечно. Рано или поздно его рост замедляется. А затраты Z растут (см. рис. 30.11 ).

Рис. 30.11. Зависимости эффекта от применения показателя Р

Из рис. 30.11 видно, что при назначении цены C 1 за единицу затрат R и цены C 2 за единицу показателя P , эти кривые можно сложить. Кривые складывают, если их требуется одновременно минимизировать или максимизировать. Если одна кривая подлежит максимизации, а другая минимизации, то следует найти их разность, например по точкам. Тогда результирующая кривая (см. рис. 30.12 ), учитывающая и эффект от управления и затраты на это, будет иметь экстремум. Значение параметра R , доставляющего экстремум функции, и есть решение задачи синтеза .

Рис. 30.12. Суммарная зависимость эффекта от применения показателя Р
и затрат Z на его получение как функции управляемого параметра R

Кроме управления R и показателя P в системах действует возмущение. Возмущения обозначим как D = {d 1 , d 2 , …} , см. рис. 30.13 . Возмущение — это входное воздействие, которое, в отличие от управляющего параметра, не зависит от воли владельца системы. Например, низкие температуры на улице, конкуренция снижают, к сожалению, поток клиентов, поломки оборудования досадно снижают производительность системы. И управлять этими величинами непосредственно владелец системы не может. Обычно возмущение действует «назло» владельцу, снижая эффект P от управляющих усилий R . Это происходит потому, что, в общем случае, система создается для достижения целей, недостижимых самих по себе в природе. Человек, организуя систему, всегда надеется посредством ее достичь некоторой цели P . На это он затрачивает усилия R , идя наперекор природе. Система — организация доступных человеку, изученных им природных компонент для достижения некоторой новой цели, недостижимой ранее другими способами .

Рис. 30.13. Условное обозначение изучаемой системы,
на которую воздействуют управляющие воздействия R и возмущения D

Итак, если мы снимем зависимость показателя P от управления R еще раз (как показано на рис. 30.10 ), но в условиях появившегося возмущения D , то, возможно, характер кривой изменится. Скорее всего, показатель будет при одинаковых значениях управлений находиться ниже, так как возмущение носит «противный» характер, снижая показатели системы (см. рис. 30.14 ). Система, предоставленная сама себе, без усилий управляющего характера, перестает обеспечивать цель, для достижения которой она была создана . Если, как и ранее, построить зависимость затрат, соотнести ее с зависимостью показателя от параметра управления, то найденная точка экстремума сместится (см. рис. 30.15 ) по сравнению со случаем «возмущение = 0» (см. рис. 30.12 ).

Рис. 30.14. Зависимость показателя P от управляющего параметра R
при различных значениях действующих на систему возмущений D

Если снова увеличить возмущение, то кривые изменятся (см. рис. 30.14 ) и, как следствие, снова изменится положение точки экстремума (см. рис. 30.15 ).

Рис. 30.15. Нахождение точки экстремума на суммарной зависимости
при различных значениях действующего возмущающего фактора D

В конечном итоге, все найденные положения точек экстремума переносятся на новый график, где образуют зависимость Показателя P от Управляющего параметра R при изменении Возмущений D (см. рис. 30.16 ).

Рис. 30.16. Зависимость показателя P от управляющего
параметра R при изменении значений возмущений D
(кривая состоит только из точек экстремумов)

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

Этот график (см. рис. 30.16 ) связывает Показатель P , Управление (ресурс) R и Возмущение D в сложных системах, указывая, как действовать наилучшим образом ЛПР (лицу, принимающему решение) в условиях возникших возмущений. Теперь пользователь может, зная реальную обстановку на объекте (значение возмущения), быстро по графику определить, какое управляющее воздействие на объект необходимо, чтобы обеспечить наилучшее значение интересующего его показателя.

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

Примечание . В тексте лекции мы использовали слова «управление» и «ресурс», то есть считали, что R = U . Следует пояснить, что управление действительно играет роль некоторой ограниченной ценности для владельца системы. То есть всегда является ценным для него ресурсом, за который всегда приходится платить, и которого всегда не хватает. Действительно, если бы эта величина не была ограничена, то мы бы могли достигать за счет бесконечной величины управлений бесконечно больших значений целей, а вот бесконечно больших результатов в природе явно не наблюдается.

Иногда различают собственно управление U и ресурс R , называя ресурсом некоторый запас, то есть границу возможного значения управляющего воздействия. В этом случае понятия ресурс и управление не совпадают: U < R . Иногда различают предельное значение управления U ≤ R и интегральный ресурс ∫U d t ≤ R .