Polytech-soft.com

ПК журнал
1 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

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

Теория массового обслуживания

. ВНИМАНИЕ . Этот раздел будет состоять из нескольких страниц, остальные из которых в данный момент находится в стадии написания. Но уже написанная часть достаточно интересная, поэтому я считаю, что будет полезно уже сейчас сделать её доступной читателям

Давно-давно, когда мы были студентами, этот раздел математики у нас выпил немало студенческой крови. А между тем, этот раздел чрезвычайно интересный!

Датский инженер Агнер Эрланг работал в телефонной компании и занялся в начале XX в. рассчётами, касающимися работы телефонной станции: какая доля попыток позвонить не будет успешной, т.к. заняты все линии, сколько нужно иметь линий связи, если абоненты могут дожидаться освобождения линии или если будут прекращать попытку. В технике фамилия датского инженера осталась в виде единицы измерения абонентской нагрузки Эрланг (Эрл).

1 Эрл — это занятие одной телефонной линии в течение 1 часа.

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

Я не ставлю себе целью написать целый учебник по ТМО. Такого роду материалов в интернете много. «Изюминкой» моей статьи должен стать интерактивный онлайн-расчётник, который позволит менять исходные данные и смотреть, как будет меняться поведение системы.

Главные понятия Теории:

Исходные данные для рассчётов в ТМО

Основные показатели работы СМО

Какие задачи позволяет решать ТМО?

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

    Классическая задача. Справочная служба имеет многолинейный телефонный номер, в среднем разговор оператора с абонентом длится 3 минуты, а в течение суток поступает 600 звонков. Сколько нужно иметь телефонных линий (и посадить операторов), чтобы не более 2% звонков оставались без ответа по причине занятости всех линий? А если звонков будет 300 или 1400 в течение суток?

В терминах ТМО задача звучит так:

  • λ = 25 звонков в час (600 звонков поделить на 24 часа)
  • μ = 20 звонков в час (60 минут поделить на 3)
  • m = 0 (при занятости всех линий звонящий абонент услышит гудки «занято»)
  • Найти n, при условии, что вероятность отказа 2%
  • В резервуар водонапорной башни железнодорожной станции непрерывно поступает вода — по кубометру воды за 3 минуты. От водонапорной башни воду получают три гидроколонки для снабжения паровозов водой. На каждую колонку заезжает паровоз в среднем раз в 2 часа и берёт от 10 до 30 кубометров воды (количество воды равномерно распределено в указанном диапазоне). При переполнении резервуара вода вытекает из переливной трубы, чего желательно избегать. Какой объём резервуара требуется водонапорной башне?

    В терминах ТМО задача звучит так:

    • λ = 20 м 3 в час
    • μ = 10 м 3 в час (математическое ожидание разового расхода 20 м , делить на промежуток в 2 часа)
    • n = 2 — количество каналов обслуживания (гидроколонок)
    • Найти m — размер накопителя, т.е. резервуара при условии нулевой вероятности отказа
  • В кассу вокзала приходит в среднем по 200 человек в час. Каждого будущего пассажира кассир обслуживает в среднем 4 минуты. Сколько должно работать касс, чтобы касса успевала обслужить каждого желающего? А сколько должно работать касс, чтобы люди стояли в очереди не более 20 минут?

    В терминах ТМО:

    • λ = 200 человек в час
    • μ = 15 человек в час (60 минут поделить на 4)
    • m = ∞, т.е. в очереди может быть бесконечно много людей
    • Найти n, при котором S имеет конечную величину
  • Пора уже что-то посчитать!

    Вычислительные мощности, доступные каждому в XXI веке колоссальны, и позволяют легко и непринуждённо проводить ресурсоёмкий расчёт — имитационное моделирование. В таблице ниже осуществляется моделирование простенькой одиночной системы массового обслуживания. Можно изменять любые из исходных данных и наблюдать, как система отзывается. Можно, например, увеличить интенсивность потока заявок и наблюдать, как система будет «утопать» в заявках (или увеличится поток отказов, если размер накопителя конечен). А вслед за этим можно увеличить количество приборов в системе и наблюдать, как показатели работы придут в норму. В этом расчёте предельная длина очереди равна 1000. Для большинства применений это можно считать бесконечно большим накопителем, однако следует помнить, что если в накопителе окажется больше тысячи заявок, расчёт будет некорректным.

    ПараметрВеличинаПояснение
    Исходные данные
    λв час — Интенсивность потока заявок
    Pμ(t)Закон распределения времени обслуживания: экспоненциальный .
    Подробнее о законах распределения
    μв час — Интенсивность потока обслуживания (каждым прибором)
    kМасштабный коэффициент
    nКоличество каналов обслуживания (не более 50)
    Результаты моделирования (на момент)
    tВремя моделирования
    SСостояние СМО, т.е. количество заявок на обслуживании + в накопителе
    S-nДлина очереди
    Статистика, показатели работы системы
    Количество поступивших заявок
    pВероятность простоя СМО
    P1-nЗагруженность обслуживающих приборов
    SMAXМаксимальное количество заявок в системе за время моделирования
    pWВероятность ожидания
    TWСреднее время ожидания, мин.
    TWmaxМаксимальное время ожидания, мин.
    PnРаспределение вероятностей пребывания СМО в различных состояниях
    TWРаспределение времени ожидания в очереди

    Если интересно, см. подробное описание математической модели в этой таблице. Даже такая модель позволяет делать интересные наблюдения. Например, можно сравнить несколько СМО с одинаковой производительностью μ×n, обслуживающих одинаковый поток заявок λ, но содержащих различное количество обслуживающих приборов n. В зависимости от того, стремимся ли мы сократить количество обслуживающих аппаратов или же вероятность ожидания, выгодным будет либо наличие одного высокопроизводительного прибора, или десятка низкопроизводительных. Также видно, что среднее арифметическое времени ожидания — величина коварная. Надо будет сделать расчёт медианной величины.

    Теория массового обслуживания

    . ВНИМАНИЕ . Этот раздел будет состоять из нескольких страниц, остальные из которых в данный момент находится в стадии написания. Но уже написанная часть достаточно интересная, поэтому я считаю, что будет полезно уже сейчас сделать её доступной читателям

    Давно-давно, когда мы были студентами, этот раздел математики у нас выпил немало студенческой крови. А между тем, этот раздел чрезвычайно интересный!

    Датский инженер Агнер Эрланг работал в телефонной компании и занялся в начале XX в. рассчётами, касающимися работы телефонной станции: какая доля попыток позвонить не будет успешной, т.к. заняты все линии, сколько нужно иметь линий связи, если абоненты могут дожидаться освобождения линии или если будут прекращать попытку. В технике фамилия датского инженера осталась в виде единицы измерения абонентской нагрузки Эрланг (Эрл).

    1 Эрл — это занятие одной телефонной линии в течение 1 часа.

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

    Я не ставлю себе целью написать целый учебник по ТМО. Такого роду материалов в интернете много. «Изюминкой» моей статьи должен стать интерактивный онлайн-расчётник, который позволит менять исходные данные и смотреть, как будет меняться поведение системы.

    Главные понятия Теории:

    Исходные данные для рассчётов в ТМО

    Основные показатели работы СМО

    Какие задачи позволяет решать ТМО?

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

      Классическая задача. Справочная служба имеет многолинейный телефонный номер, в среднем разговор оператора с абонентом длится 3 минуты, а в течение суток поступает 600 звонков. Сколько нужно иметь телефонных линий (и посадить операторов), чтобы не более 2% звонков оставались без ответа по причине занятости всех линий? А если звонков будет 300 или 1400 в течение суток?

    В терминах ТМО задача звучит так:

    • λ = 25 звонков в час (600 звонков поделить на 24 часа)
    • μ = 20 звонков в час (60 минут поделить на 3)
    • m = 0 (при занятости всех линий звонящий абонент услышит гудки «занято»)
    • Найти n, при условии, что вероятность отказа 2%
  • В резервуар водонапорной башни железнодорожной станции непрерывно поступает вода — по кубометру воды за 3 минуты. От водонапорной башни воду получают три гидроколонки для снабжения паровозов водой. На каждую колонку заезжает паровоз в среднем раз в 2 часа и берёт от 10 до 30 кубометров воды (количество воды равномерно распределено в указанном диапазоне). При переполнении резервуара вода вытекает из переливной трубы, чего желательно избегать. Какой объём резервуара требуется водонапорной башне?

    В терминах ТМО задача звучит так:

    • λ = 20 м 3 в час
    • μ = 10 м 3 в час (математическое ожидание разового расхода 20 м , делить на промежуток в 2 часа)
    • n = 2 — количество каналов обслуживания (гидроколонок)
    • Найти m — размер накопителя, т.е. резервуара при условии нулевой вероятности отказа
  • В кассу вокзала приходит в среднем по 200 человек в час. Каждого будущего пассажира кассир обслуживает в среднем 4 минуты. Сколько должно работать касс, чтобы касса успевала обслужить каждого желающего? А сколько должно работать касс, чтобы люди стояли в очереди не более 20 минут?

    В терминах ТМО:

    • λ = 200 человек в час
    • μ = 15 человек в час (60 минут поделить на 4)
    • m = ∞, т.е. в очереди может быть бесконечно много людей
    • Найти n, при котором S имеет конечную величину
  • Пора уже что-то посчитать!

    Вычислительные мощности, доступные каждому в XXI веке колоссальны, и позволяют легко и непринуждённо проводить ресурсоёмкий расчёт — имитационное моделирование. В таблице ниже осуществляется моделирование простенькой одиночной системы массового обслуживания. Можно изменять любые из исходных данных и наблюдать, как система отзывается. Можно, например, увеличить интенсивность потока заявок и наблюдать, как система будет «утопать» в заявках (или увеличится поток отказов, если размер накопителя конечен). А вслед за этим можно увеличить количество приборов в системе и наблюдать, как показатели работы придут в норму. В этом расчёте предельная длина очереди равна 1000. Для большинства применений это можно считать бесконечно большим накопителем, однако следует помнить, что если в накопителе окажется больше тысячи заявок, расчёт будет некорректным.

    ПараметрВеличинаПояснение
    Исходные данные
    λв час — Интенсивность потока заявок
    Pμ(t)Закон распределения времени обслуживания: экспоненциальный .
    Подробнее о законах распределения
    μв час — Интенсивность потока обслуживания (каждым прибором)
    kМасштабный коэффициент
    nКоличество каналов обслуживания (не более 50)
    Результаты моделирования (на момент)
    tВремя моделирования
    SСостояние СМО, т.е. количество заявок на обслуживании + в накопителе
    S-nДлина очереди
    Статистика, показатели работы системы
    Количество поступивших заявок
    pВероятность простоя СМО
    P1-nЗагруженность обслуживающих приборов
    SMAXМаксимальное количество заявок в системе за время моделирования
    pWВероятность ожидания
    TWСреднее время ожидания, мин.
    TWmaxМаксимальное время ожидания, мин.
    PnРаспределение вероятностей пребывания СМО в различных состояниях
    TWРаспределение времени ожидания в очереди

    Если интересно, см. подробное описание математической модели в этой таблице. Даже такая модель позволяет делать интересные наблюдения. Например, можно сравнить несколько СМО с одинаковой производительностью μ×n, обслуживающих одинаковый поток заявок λ, но содержащих различное количество обслуживающих приборов n. В зависимости от того, стремимся ли мы сократить количество обслуживающих аппаратов или же вероятность ожидания, выгодным будет либо наличие одного высокопроизводительного прибора, или десятка низкопроизводительных. Также видно, что среднее арифметическое времени ожидания — величина коварная. Надо будет сделать расчёт медианной величины.

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

    5 Общие сведения о сетях систем массового обслуживания

    Структура сетей массового обслуживания

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

    Простейшая разомкнутая или открытая сеть получается при последовательном соединении CMO (рисунок 5.1). Она еще называется многофазной CMO.

    Рисунок 5.1 — Простейшая разомкнутая цепь

    Замкнутая сеть СМО

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

    Простейшая замкнутая сеть показана на рисунке 5.2. Эта система c отказами и восстановлениями хорошо известна из теории массового обслуживания. В системе постоянно находятся М1 требований, которые появляются при отказе устройств M. Если устройство отказало, то поступает требование на его ремонт к бригаде c N ремонтниками, которые ремонтируют устройство, а потом отремонтированное устройство восстанавливает свою работу. На рисунке 5.2 это показано обратной связью от N1 устройств. Сеть также используется при моделировании компьютерной системы, которая работает в режиме «запрос — ответ», то есть пользователь не посылает новый запрос к системе до тех пор, пока не получит ответ на предшествующий запрос. Запросы обрабатываются любым из N1 компьютеров. Примерами таких систем могут быть автоматизированные системы продажи билетов на поезда или самолеты, системы передачи транзакций от кассиров в банке и т.п.

    Рисунок 5.2 — Структурная схема замкнутой сети

    Сеть (рисунок 5.3) содержит K узлов и N требований, которые находятся в сети. Каждый узел может иметь одно или несколько одинаковых устройств обслуживания. C вероятностью (или частотой) q0j — требования поступают к любому узлу сети, a c вероятностью qkj (j = 1. К) требование, которое оставляет узел k, направляется к узлу j. Таким образом, любое требование до завершения своего обслуживания в сети обычно проходит несколько узлов.

    Рисунок 5.3 — Структура сети из К узлов

    Внешняя среда обозначается как узел 0 сети. Если сеть замкнутая, то требования c выхода направляются на вход (пунктирная линия на рисунке 5.3) и количество требований N в сети не изменяется

    Законы о потоках в сети СМО

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

    Рисунок 5.4 — Закон о разделении потоков требований в сети

    Рисунок 5.5 — Закон о сумме потоков требований в сети

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Читать еще:  Разделить сеть на подсети
    Ссылка на основную публикацию
    Adblock
    detector