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

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Содержание 

ВВЕДЕНИЕ………………………………………………………………..…..…3

ГЛАВА I. ПОСТАНОВКА ЗАДАЧ МАССОВОГО ОБСЛУЖИВАНИЯ

1 Общее понятие теории массового обслуживания……………………….….4

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

1.3 Потоки событий. Простейший поток и его свойства………….……..….14

1.Механизм  обслуживания……………………………….……………………..23

1.5 Графы состояний СМО…………………………………………………....…23

Глава II. УРАВНЕНИЯ, ОПИСЫВАЮЩИЕ СИСТЕМЫ

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

 СИСТЕМЫ  МАССОВОГО ОБСЛУЖИВАНИЯ

1. Процессы «рождения – гибели»………………………………..…….…..29
2. Пример моделирования системы массового обслуживания…….…..…31

Заключение……………………………………………………………………….33

Список  литературы……………………………………………………..………..35 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

                         Введение 
 

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

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

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

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

ГЛАВА I.  ПОСТАНОВКА ЗАДАЧ МАССОВОГО ОБСЛУЖИВАНИЯ. 

1.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).

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

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

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

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

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

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

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

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

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

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

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

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

 
Моделирование позволяет исследовать  такие системы, прямой эксперимент  с которыми:

а) трудно выполним;

б) экономически невыгоден;

в) вообще невозможен.

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