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

Задание

массовый многоканальный обслуживание

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

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

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

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

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

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

— Среднее число заявок, обслуживаемое СМО в единицу времени, или абсолютная пропускная способность;

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

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

— Вероятность занятости каждого из канала и всех вместе;

— Среднее время занятости каждого канала;

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

— Вероятность простоя каждого канала;

— Вероятность простоя всей системы;

— Среднее количество заявок, стоящих в очереди;

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

— Среднее время обслуживания заявки;

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

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

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

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

Теоретическая часть. Система массового обслуживания

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

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

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

Различают фиксированные и динамические приоритеты. Фиксированные приоритеты чаще называют дисциплиной обслуживания.

Дисциплина обслуживания задает порядок выбора из очереди в освободившийся прибор заявок одинакового приоритета. Выделим следующие дисциплины: FIFO (FirstInput — FirstOutput): первым пришел — первым обслужен, LIFO (LastInput — FirstOutput): последним пришел — первым обслужен, RAND (Random): случайный выбор из очереди. В быту обычно действует дисциплина FIFO. Дисциплина LIFO реализуется в буфере, организованном по принципу стека. Такая дисциплина может оказаться целесообразной, например, при передаче информации, если ее ценность быстро падает со временем.

Характеристики СМО

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

— наличие объектов, нуждающихся в случайные моменты времени в обслуживании (в выполнении некоторых работ над собой или для себя);

— эти объекты порождают так называемый входящий поток заявок (требований) на обслуживание;

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

— возникновение задержек в обслуживании (образование очереди).

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

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

СМО бывают:

— с отказами — если все каналы заняты — заявка покидает систему;

— с ожиданием — заявка, поступившая в систему, становится в очередь;

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

— заявка немедленно принимается на обслуживание, если в системе находится k-заявок и k < n, где n — число каналов;

— заявка становится в очередь, если k < n + m;

— заявка получает отказ и покидает систему, если k = n + m.

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

Расчет параметров СМО

Рассмотрим многоканальную систему массового обслуживания, в которой интенсивность потоков поступающих заявок зависит от состояния в самих системах. Пусть система состоит из n каналов обслуживания иmисточников заявок так, что: n? k. Имеется n каналов, на которые поступает поток заявок с интенсивностью л. Поток обслуживаний имеет интенсивность м. Найти предельные вероятности состояний системы и показатели ее эффективности. Система S (СМО) имеет следующие состояния (нумеруем их по числу заявок, находящихся в системе): S₀, S₁, S₂, …, S_k, …, S_n, где S_k — состояние системы, когда в ней находится k заявок, т. е. занято kканалов. Граф состояний СМО соответствует процессу гибели и размножения и показан на рис. 1.

Рисунок 1

Поток заявок последовательно переводит систему из любого левого состояния в соседнее правое с одной и той же интенсивностью л. Интенсивность же потока обслуживаний, переводящих систему из любого правого состояния в соседнее левое состояние, постоянно меняется в зависимости от состояния. Действительно, если СМО находится в состоянии S₂ (два канала заняты), то она может перейти в состояние. S₁ (один канал занят), когда закончит обслуживание либо первый, либо второй канал, т. е. суммарная интенсивность их потоков обслуживании будет 2 м. Аналогично суммарный поток обслуживаний, переводящий СМО из состояния S₃ (три канала заняты) в S₂. будет иметь интенсивность Зм, т. е. может освободиться любой из трех каналов и т. д. Для нахождения вероятности составим линейное уравнение:

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

Чтобы система имела решение нужно добавить полную вероятность

P₀ + P₁ + …+P_k = 1,

Получим:

Показатели эффективности СМО:

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

N_zan=

2. Среднее число, А заявок обслуживаемых системой за единицу времени: А = N_zan?µ

3. Среднее число поступивших заявок: N_post = k — A/л

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

N_och= N_post-N_zan

Практическая часть. Расчет параметров

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

Дано:

n= 3

k= 8

л=3

t=20 мин. ,(20 мин.- 1/3 часа) => µ=1/t; µ=3

Решение Для начала нарисуем схему системы.

Рис.

Решим систему уравнений:

Для этого добавим полную вероятность P₀ + P₁ + …+P_k = 1, а так же заменим P_r(t) = 0

Теперь выразим каждоеP_nчерезP_o

P₁=; P₁=8.

P₂=; P₂=; P₂= ;

P₂= ;P₂=.

P₃=; P₃=; P₃= .

P₄=; P₄=; P₄= .

P₅=; P₅= ;

P₅= .

P₆=;

P₆= ;

P₆= .

P₇=; P₇=;

P₇= .

P₈=; P₈=;

P₈= .

Выразив все значения P, наблюдаем закономерность вида:

P=, гдес=.

С помощью уравнения полной вероятности найдем P₀:

P₀=

Подставив все значения получим:

P₀=0,183

Проверим условие

P₀=0,183;

P₁=0,1 464;

P₂=0,5 124;

P₃=0,10 248;

P₄=0,1708;

P₅=0,22 773;

P₆=0,22 773;

P₇=0,15 182;

P₈=0,5 060.

0,183+0,1 464+0,5 124+0,10 248+0,1708+

+0,22 773+0,22 773+0,15 182+0,5 060= 0,99 704? 1 Условие выполняется.

Вычислим:

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

N_zan=; N_zan=

N_zan=0,1 464+0,10 248+0,30 744+0,5124+

+0,68 319+0,68 319+0,45 546+0,1518=2,9106? 3.

Среднее число, А заявок обслуживаемых системой за единицу времени:

А = N_zan?µ; А= 9.

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

N_post = k — A/л; N_post= 8−3=5.

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

N_och= N_post-N_zan;N_och=5−3= 2.

Заключение

Судя по выявленным показателям, можно сделать вывод, что при исходных величинах получаем: 5 поступивших заявок на 2 заявку в очереди, то есть 40% заявок находятся в очереди. Следовательно, система не очень результативна.

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

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

1.Лекции по дисциплине «Теория систем и системный анализ»

2.http://math.semestr.ru/cmo