Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Курсовая работа

По дисциплине: математика.

На тему: системы массового обслуживания.

Содержание

• Введение.
• Классификация СМО
• Основные определения.
• 1. Простейший поток.
• 2. Регулярный поток.
• 3. Поток с ограниченным последействием (поток Пальма).
• 4. Поток Эрланга.
• 5. Понятие времени обслуживания и времени ожидания.
• 6. Обозначения.
• Марковские СМО
• СМО, описываемые процессами гибели и размножения.
• Примеры применения обозначений
• 1. M|M|1|?
• 2. M|M|m|?
• 3. M|M|1|0
• 4. M|M|m|0
• 5. M|M|m|n
• 6. M|M|?
• Полумарковские СМО и приоритетные СМО.
• Уравнения Колмогорова. Математические модели марковских СМО. Стационарные режимы функционирования СМО.
• 1. СМО с отказами.
• 2. СМО с ожиданием и ограниченным временем ожидания.
• 3. Чистые СМО с ожиданием.
• 4. Системы обслуживания с ограниченной длиной очереди.
• Литература

Введение

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

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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Процессы, объединенные общей структурой, изображенной на рис. 1, называют процессами массового обслуживания.

Примеры СМО (систем массового обслуживания):

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

2. Функционирование взлетно-посадочной полосы аэродрома. Требования - самолеты, требующие посадки или взлета, работа прибора - резервирование взлетно-посадочной полосы за определенным самолетом.

3. Работа ЭВМ в режиме разделения времени. Требования - программы, обрабатываемые ЭВМ, прибор - процессор ЭВМ.

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

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

СМО могут быть классифицированы по ряду признаков.

1. Условия ожидания начала обслуживания.

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

Пример: работа автоматической телефонной станции (АТС). Абонент, обратившийся на АТС, получает отказ, если необходимая линия связи уже занята.

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

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

· СМО с ограниченной длиной очереди - СМО, допускающие очередь, но с ограниченным числом требований в ней.

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

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

Пример: торговые точки по продаже фруктов, овощей, которые могут храниться ограниченное время.

2. Число каналов обслуживания.

· одноканальные,

· многоканальные.

3. Расположение каналов обслуживания.

· последовательное,

Пример: 1) технологические потоки сборки различных технических изделий: в одном цехе производится сборка одних узлов, после того, как собраны эти узлы, изделие поступает в следующий цех, где производится сборка следующих узлов и т.д. 2) эшелонированная противотанковая оборона какого-нибудь объекта. Танки должны преодолеть последовательно все эшелоны.

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

4. Место нахождения источника требований.

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

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

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

5. Дисциплина обслуживания.

· прямой порядок обслуживания FIFO (First In First Out) - обслуживание в порядке поступления в СМО.

Пример: 1) экзамен - отвечать по билету приглашается студент, который первый зашел и взял билет. 2) операции на конвейере.

· инверсионный (обратный, стековый) порядок обслуживания LIFO (Last In First Out) - на обслуживание выбирается требование, поступившее в СМО последним.

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

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

Пример: 1) система ПВО при отражении воздушного налета противника. 2) отбор образцов для статистического анализа.

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

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

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

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

Пример: автобус, отправляющийся со своей начальной остановки, забирает всех пассажиров, собравшихся к моменту отправления.

При наличии разнородных требований учитывают приоритет.

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

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

· абсолютный приоритет.

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

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

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

· Обслуживание в первую очередь требований с наименьшим временем обслуживания (но в большинстве случаев неизвестна длительность обслуживания до его завершения).

Основные определения.

Случайным процессом называется процесс, который для любого момента времени t = t₀ является случайной величиной.

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

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

1. Простейший поток

Поток событий называется простейшим (стационарным, пуассоновским), если:

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

б) вероятность попадания на элементарный участок ?t двух или более событий пренебрежимо мала по сравнению с вероятностью попадания одного события;

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

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

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

где ? - интенсивность входного потока.

X - СВ, характеризующая число заявок, поступающих в СМО на временном интервале длительности t. Если входной поток - простейший, то

M[X]= ?t (среднее число заявок, поступающих в СМО за время t), D[X]= ?t (величина, характеризующая рассеивание числа заявок, поступивших в СМО за время t).

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



M[X]= 1/?, D[X]= 1/?².

Важнейшее свойство показательного распределения: если промежуток времени, распределенный по показательному закону, уже длился некоторое время ?, то это никак не влияет на закон распределения оставшейся части промежутка (T-?): он будет таким же, как и закон распределения всего промежутка T. Это свойство представляет собой другую формулировку для “отсутствия последействия”, которое является основным свойством простейшего потока.

2. Регулярный поток

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

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

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

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

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

4. Поток Эрланга

Потоки Эрланга образуются “просеиванием” простейшего потока. Потоком Эрланга k-го порядка E_k называется поток, получаемый из простейшего, если сохранить каждую (k+1)-ю точку, а остальные выбросить. Простейший поток можно рассматривать как поток Эрланга 0-го порядка.

Пример: поток Эрланга второго порядка: сохраняем каждую 3-ю точку, а 2 промежуточные выбрасываем.

Закон распределения :

называется законом распределения Эрланга k-го порядка.

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

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

канал массовое обслуживание поток



Величину ? называют интенсивностью обслуживания. Из формулы видно, что среднее время обслуживания одной заявки равно 1/?. Функция распределения времени обслуживания заявки равна:

ее значение равно вероятности того, что к моменту времени t обслуживание заявки будет завершено, т.е. освободится канал обслуживания.

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

Величина ? - величина, обратная среднему времени ожидания. Функция распределения:

ее значение равно вероятности того, что в момент t начнется обслуживание заявки.

6. Обозначения

Структуру СМО принято обозначать последовательностью символов A|B|m|n, где m - число приборов в СМО (каналов обслуживания), n - количество мест ожидания (если число n=?, то символ обычно опускают). Тогда: A|B|m|? - СМО с ожиданием, A|B|m|0 - СМО с потерями.

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

GI (G) - произвольное распределение интервалов между поступлениями требований (входящий поток - произвольный);

M - показательное распределение (пуассоновский поток);

E_k - распределение Эрланга порядка k (Эрланговский поток);

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

U - равномерное распределение.

Символ B характеризует поток обслуживания (характеристика обслуживания).

G - произвольное распределение длительности обслуживания.

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

Марковские СМО

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

Пример марковского процесса: система S - счетчик в такси. Состояние системы в момент t характеризуется числом километров (десятых долей километров), пройденным автомобилем до данного момента. Пусть в момент t₀ счетчик показывает S₀. Вероятность того, что в момент t> t₀ счетчик покажет то или иное число километров S₁ зависит от S₀, но не зависит от того, в какие моменты времени изменялись показания счетчика до момента t₀.

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

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

СМО, описываемые процессами гибели и размножения

Марковский процесс с дискретными состояниями S_k, k=1,...,m называют процессом гибели и размножения, если он имеет размеченный граф состояний:

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Переходы могут осуществляться из любого состояния только в состояния с соседними номерами, т.е. из состояния S_k возможны переходы только либо в состояние S_k-1, либо в состояние S_k+1.Предполагается, что все потоки событий, переводящие систему по стрелкам графа - простейшие с соответствующими интенсивностями ?_k,k+1 или ?_k,k-1. (Интенсивность - частота появления событий или среднее число событий, поступающих в СМО в единицу времени.). ?_i,j - плотности вероятностей перехода из состояния S_i в состояние S_j.

Рассматриваем СМО, на вход которой поступает простейший входной поток с интенсивностью ?, время обслуживания заявки - СВ, распределенная по показательному закону с параметром ?. В случае марковского СП ?_i,i+1=?, ?_i,i-1=?.

Примеры применения обозначений

1. M|M|1|? - одноканальная система с неограниченной очередью, нет ограничений ни по длине очереди, ни по времени ожидания.

Пример: телефон-автомат с одной будкой.

Поток заявок, поступающих в СМО, имеет интенсивность ?, а поток обслуживания (переводящий систему из состояния S_k в S_k-1) - интенсивность ?. Система может находиться в одном из состояний S₀, S₁, ..., S_k,…, по числу заявок, находящихся в СМО: S₀ - канал свободен, S₁ - канал занят (обслуживает заявку), очереди нет, S₂ - канал занят, 1 заявка в очереди, …, S_k - канал занят, (k-1) заявка в очереди.

Это процесс гибели и размножения, но с бесконечным числом состояний

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

2. M|M|m|? - многоканальная система (m каналов) с неограниченной очередью.

Пример: в универсаме к узлу расчета поступает поток покупателей, их обслуживает m кассиров.

Система может находиться в одном из состояний S₀, S₁, ..., S_k,…,S_m,... - нумеруемых по числу заявок, находящихся в СМО: S₀ - в системе нет заявок (все каналы свободны), S₁ -занят один канал, остальные свободны, …, S_k - занято k каналов, остальные свободны, …, S_m - заняты все m каналов (очереди нет), S_m+1 - заняты все m каналов, в очереди 1 заявка,…, S_m+r - заняты все m каналов, r заявок в очереди.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

3. M|M|1|0 - одноканальная система с отказами.

Имеется 1 канал, на который поступает поток заявок с интенсивностью ?, поток обслуживания имеет интенсивность ?. СМО имеет 2 состояния: S₀ - канал свободен, S₁ - канал занят.

Пример: Заявки, поступающие в телевизионное ателье при наличии одного телефонного номера.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

4. M|M|m|0 - многоканальная система с отказами.

Имеется m каналов. СМО может находиться в следующих состояниях (по числу заявок, находящихся в системе): S₀, S₁, ..., S_k,…,S_m. S_k - состояние системы, когда в ней находится k заявок, т.е. занято k каналов. Интенсивность потока обслуживания, переводящего систему из любого правого состояния в соседнее левое, меняется в зависимости от состояния. Если СМО находится в состоянии S₂ (2 канала заняты), то она может перейти в состояние S₁ (1 канал занят), когда закончит обслуживание либо первый, либо второй канал, т.е. суммарная интенсивность их потоков обслуживания будет 2?.

Пример: справочная телефонная служба, m телефонисток отвечают на вопросы абонентов. Если все линии заняты, абонент получает отказ.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

5. M|M|m|n - многоканальная система с ограниченной длиной очереди.

СМО может находиться в следующих состояниях (по числу заявок, находящихся в системе): S₀, S₁, ..., S_k,…,S_m,...S_m+n. S_m+1 - заняты все m каналов, в очереди 1 заявка.

Пример: выдача ограниченного числа m талонов на прием к какому-либо врачу в больнице, (m+1)-ый человек уже не становится в очередь.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

6. M|M|? - немедленное обслуживание (система с бесконечным числом приборов).

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

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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

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

Уравнения Колмогорова.

Математические модели марковских СМО. Стационарные режимы функционирования СМО.

Теорема. Пусть система имеет множество возможных состояний S_k, k=1,...,m, а процесс изменения этой системы представляет собой СП, причем для всех пар возможных состояний S_i и S_j определены плотности вероятностей переходов ?_ij(t) и ?_ji(t). Тогда вероятности состояний системы p_k(t) = P(S_k) удовлетворяют системе уравнений Колмогорова:

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

В случае простейшего входного потока с интенсивностью ?, временем ожидания и обслуживания, распределенными по показательному закону с параметрами ? и ? соответственно: ?_i,i+1(t)=?, ?_i,i-1(t)=?.

Особый интерес представляют вероятности p_k(t) в предельном, стационарном режиме, т.е. при t > ?, которые называются предельными (финальными) состояниями. В уравнениях Колмогорова производные предельных вероятностей равны 0 как производные от постоянных величин.

1. СМО с отказами.

1) одноканальная СМО

Система уравнений Колмогорова имеет вид:

В предельном (стационарном) режиме система уравнений Колмогорова:

Учитывая нормировочное условие p₀ + p₁ = 1, найдем:

; .

которые выражают среднее относительное время пребывания системы в состоянии S₀ (когда канал свободен) и S₁ (когда канал занят), т.е. определяют соответственно относительную пропускную способность системы q и вероятность отказа P_отк:

;

Абсолютная пропускная способность: .

Задача 1. Известно, что заявки в ателье поступают с интенсивностью ?=90 (заявок в час), а средняя продолжительность разговора по телефону t_об = 2 мин. Определить показатели эффективности работы СМО (телефонной связи) при наличии одного телефонного номера.

Решение.

Интенсивность потока обслуживания ?= 1/ t_об =1/2 = 0,5(1/мин ) = 30 (1/ч).

Относительная пропускная способность СМО q = 30/(30+90) = 0,25, т.е. в среднем только 25% поступающих заявок осуществят переговоры по телефону. Соответственно вероятность отказа в обслуживании составит P_отк = 0,75. Абсолютная пропускная способность СМО: Q = 90*0,25 = 22,5, т.е. в среднем в час будут обслужены 22,5 заявки.

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

2) многоканальная СМО

Система уравнений Колмогорова имеет вид:

В стационарном режиме:

(1)

Разрешим систему (1) относительно неизвестных p₀, p₁,..., p_m. Из первого уравнения:

(2)

Из второго с учетом (2):

 (3)

Аналогично из третьего, с учетом (2) и (3):

и вообще, для любого k ? m:

. (4)

Введем обозначение:

(5)

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

Тогда

(6)

Формула (6) выражает все вероятности p_k через p₀ . Воспользуемся условием :

 > (7)

Подставляя (7) в (6), получим , 0 ? k ? m. (8)

Формулы (7) и (8) называют формулами Эрланга. Полагая в формуле (8) k = m, получим вероятность отказа

: . (9)

Относительная пропускная способность (вероятность того, что заявка будет обслужена):

(10)

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

Абсолютная пропускная способность:

. (11)

Среднее число занятых каналов есть математическое ожидание числа занятых каналов:

или или, учитывая (11) и (5)

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

; ; .(7')

При больших значениях i:

, где -

функция Лапласа.

Вероятность отказа: (9')

Относительная пропускная способность

(10')

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

= (11')

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

Решение. Интенсивность нагрузки канала по формуле (5) ? = 90/30 = 3, т.е. за время среднего (по продолжительности) телефонного разговора t_об = 2 мин. поступает в среднем 3 заявки на переговоры.

Будем постепенно увеличивать число каналов (телефонных номеров) n = 2, 3, 4,... и определим по формулам (7), (10), (11) для получаемой n-канальной СМО характеристики обслуживания. Например, при n = 2

; и т.д.

Значения характеристик СМО представим в таблице:



Характеристика обслуживания	Число каналов (телефонных номеров)
	1	2	3	4	5	6
Относит. пропускная способность, q	0,25	0,47	0,65	0,79	0,90	0,95
Абсолют. пропускная способность, Q	22,5	42,4	58,8	71,5	80,1	85,3

По условию оптимальности q ? 0,9, следовательно, в ателье необходимо установить 5 телефонных номеров (в этом случае q = 0,9). При этом в час будут обслуживаться в среднем 80 заявок (Q = 80,1), а среднее число занятых телефонных номеров (каналов)

Задача 3. Автоматическая телефонная станция обеспечивает не более 120 переговоров одновременно. Средняя продолжительность разговора 60 секунд, а вызовы поступают в среднем через 0,5 секунды. Рассматривая такую станцию как многоканальную систему обслуживания с отказами и простейшим входным потоком, определить: а) среднее число занятых каналов, б) относительную пропускную способность, в) среднее время пребывания вызова на станции с учетом того, что разговор может и не состояться.

Решение. Имеем: m = 120; ? = 1/0,5 = 2; ? = 1/60; ? = ?/? = 120.

Используя таблицы функции Лапласа, получаем:

,

так как

.

так как ? есть интенсивность входного потока (число заявок в единицу времени), то ?t_ср = и .

2. СМО с ожиданием и ограниченным временем ожидания.

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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Если занято i каналов и i ? m, то в силу независимости их функционирования интенсивность обслуживания возрастает в i раз: ?_i,i-1 = i?. При возникновении очереди каждое состояние рассматриваемой СМО характеризуется занятостью каналов обслуживания. Поэтому интенсивность освобождения каналов становится постоянной u = m?.

Закон распределения времени ожидания определяется интенсивностью ? ухода из очереди при наличии в ней одной заявки. В силу независимости поступления заявок (см. определение простейшего потока) интенсивность, с которой заявки отказываются от обслуживания и уходят из очереди, равна r? (для очереди длины r ? 1). Т.о., плотность вероятности перехода системы из состояния S_m+r в состояние S_m+r-1 равна сумме интенсивностей освобождения каналов обслуживания и отказа от обслуживания: ?_m+r,m+r-1 = m? + r?.

Составим уравнения Колмогорова:

i=1,..., m-1, r ? 0.

Если на длину очереди не накладывать ограничений, то система обыкновенных дифференциальных уравнений (1) является бесконечной.

Если в начальный момент времени t = 0 рассматриваемая система находилась в одном из своих возможных состояний S_j, то начальные условия для нее выглядят следующим образом:

Для стационарного режима функционирования имеем:

(12)

(В стационарном режиме функционирования изучаемая система также меняет свое состояние случайным образом, но вероятности состояний уже не зависят от текущего времени).

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

i=1,...,m, (13)

Перейдем к уравнениям для i > m (i = m + s, s ? 1). Тем же способом получим:

;

и вообще при любом s ? 1:

r?1 (14)

Определим p₀ (из последнего уравнения системы (12)):

(15)

Вводя обозначения:

 и , где - приведенная плотность потока ухода заявок из очереди, получим:

, 0 < i ? m.

(16)

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

(17)

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

:

(18)

Относительная пропускная способность: или : (19)

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

(20)

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

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

(21)

( есть математическое ожидание числа занятых каналов обслуживания:

) (22)

Время ожидания : , время обслуживания: .

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

3. Чистые СМО с ожиданием

Чистой СМО с ожиданием называют такую систему, в которой заявки не покидают очередь. Эти системы имеют неограниченное время ожидания, интенсивность ухода из очереди нулевая: ? = 0 > ? = 0. P_отк = 0. Рассмотрим многоканальную СМО.

Математическая модель данной СМО:

Для стационарного режима:

при ? = 0 получим:

(23)

Если ? > m, то ряд с общим членом расходится, значит, согласно (23) p₀ = 0 и p_k = 0, не выполняется нормировочное условие.

Если ? < m, то ряд с общим членом сходится, его сумму можно найти (это геометрическая прогрессия) и равенство (23) равносильно следующему:

отсюда, воспользовавшись формулой (13):

(0 ? k ? m), аналогично для k=m+s (s ? 0): (24)

(24')

Вероятность того, что заявка окажется в очереди:

(25)

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

. (26)

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

. (27)

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

. (28)

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

(29)

Вышеприведенные формулы называются формулами Литтла.

Для одноканальных СМО некоторые формулы упрощаются (при ? <1):

, . (30)

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

(31)

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

(32)

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

. (33)

Среднее время пребывания заявки в системе:

. (34)

Среднее время пребывания заявки в очереди:

. (35)

Замечание. Для СМО с неограниченной очередью при ? < 1 любая заявка, пришедшая в систему, будет обслужена, т.е. вероятность отказа P_отк = 0, относительная пропускная способность q = 1, а абсолютная пропускная способность равна интенсивности входящего потока заявок: Q = ?.

Задача 4. На железнодорожную сортировочную горку прибывают составы с интенсивностью 2 состава в час. Среднее время обработки состава равно 0,4 часа. Составы, прибывшие в момент, когда сортировочная горка занята, становятся в очередь в парке ожидания с тремя путями, каждый из которых предназначен для одного состава. Если все пути в парке заняты, то прибывший состав ожидает свою очередь на внешней ветке. Найти:

а) среднее число составов, ожидающих обработки.

б) среднее время пребывания состава в парке ожидания.

в) среднее время пребывания состава на внешней ветке.

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

д) вероятность того, что прибывший состав займет место на внешней ветке.

Решение. Имеем: ? = 2, ? = 1/0,4 = 2,5, ? = ?/? = 0,8, m = 1. Так как ? = 0,8 < 1 = m, то система справляется с обслуживанием входного потока.

а) По формуле (30):

= 1 - 0,8 = 0,2. Из формулы (32) средняя длина очереди:

.

д) Вероятность того, что прибывший состав займет место на внешней ветке, находим из формулы (24'). Искомая вероятность равна вероятности того, что длина очереди будет больше трех:

в) Среднее время ожидания на внешней ветке (в часах) равно:

б) среднее время пребывания в парке ожидания (в часах):

г) среднее время ожидания обслуживания в рассматриваемой системе (в часах) равно:

среднее время пребывания на сортировочной горке:

.

Задача 5. В универсаме к узлу расчета поступает поток покупателей с интенсивностью ? = 81 чел. в час. Средняя продолжительность обслуживания контролером-кассиром одного покупателя t_об = 2 мин. Определить:

а) минимальное количество контролеров-кассиров M, при котором очередь не будет расти до бесконечности, и соответствующие характеристики при m = M.

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

,

будет минимальна, и сравнить характеристики обслуживания при m = M и m = M_опт.

в) вероятность того, что в очереди будет не более трех покупателей.

Решение

а) По условию ? = 81 (1/ч) = 81/60 = 1,35 (1/мин.). По формуле (5) ? = ?/? = ? t_об = 1,35*2=2,7. Очередь не будет возрастать до бесконечности при условии ?/m < 1, т.е. при m > ? = 2,7. Таким образом, минимальное количество контролеров-кассиров M = 3.

Найдем характеристики СМО при m = 3. Вероятность того, что в узле расчета отсутствуют покупатели, по формуле (24):

, т.е. в среднем 2,5% времени контролеры-кассиры будут простаивать.

Вероятность того, что в узле расчета будет очередь, по формуле (25):

Среднее число покупателей, находящихся в очередь, по (27):

Среднее время ожидания в очереди по (29): T_оч = 7,35/1,35 = 5,44 (мин.).

Среднее число покупателей в узле расчета по (28): L_c = 7,35+2,7 = 10,05.

Среднее время нахождения покупателей в узле расчета по (29): T_сист = 10,05/1,35 = 7,44 (мин.).

Среднее число контролеров-кассиров, занятых обслуживанием покупателей, по (26) = ?/m = 2,7/3 = 0,9.

Абсолютная пропускная способность узла расчета Q = 1,35 (1/мин) = 81 (1/ч), т.е. 81 покупатель в час.

Анализ характеристик свидетельствует о значительной перегрузке узла расчета при наличии трех кассиров.

б) Относительная величина затрат при m = 3.

=3/1,35+3*5,44 = 18,54.

Рассчитаем относительную величину затрат при других значениях m.

Характеристика обслуживания	Число контролеров-кассиров, m
	3	4	5	6	7
Вероятность простоя кассиров	0,025	0,057	0,065	0,067	0,067
Среднее число покупателей в очереди	5,44	0,60	0,15	0,03	0,01
Относительная величина затрат	18,54	4,77	4,14	4,53	5,22

Как видно из табл., минимальные затраты получены при m = M_опт = 5 контролерах-кассирах.

Определим характеристики обслуживания узла расчета при m = M_опт = 5. Получим P_оч = 0,091; =0,198; T_оч = 0,146 (мин.); L_c = 2,90; T_сист = 2,15 (мин); = 2,7; k₃ = 0,54.

Как видим, при m = 5 по сравнению с m = 3 существенно уменьшились вероятность возникновения очереди P_оч, длина очереди и среднее время пребывания в очереди T_оч и соответственно среднее число покупателей L_c и среднее время нахождения в узле расчета T_сист , а также доля занятых обслуживанием контролеров k_3. Но среднее число занятых обслуживанием контролеров-кассиров и абсолютная пропускная способность узла расчета Q естественно не изменилось.

в) Вероятность того, что в очереди будет не более 3 покупателей, определится как:

где каждое слагаемое найдем по формулам (23)-(25). Получим при m = 5:

(В случае m = 3 контролеров-кассиров та же вероятность существенно меньше: P(r ? 3) = 0,464).

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

Рассматриваем m - канальную систему обслуживания, длина очереди которой ограничена числом N < ?.

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

Математическая модель одноканальной СМО:

Множество возможных состояний системы S_k, k=1,...,m+N конечно, а интенсивность ухода заявок из очереди нулевая ? = 0 > ? = 0. Учитывая вышесказанное, получаем при стационарном режиме функционирования СМО:

(36)

Вероятность отказа P_отк = p_m+N. (37)

Относительная пропускная способность: q = 1- P_отк .

Абсолютная пропускная способность : Q = ?*q.

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

. (38)

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

. (39)

Среднее число заявок в системе: . (40)

Для одноканальной системы формулы упрощаются:

; .

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

Относительная пропускная способность:

Абсолютная пропускная способность: .

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

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

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

Задача 6. На станцию текущего ремонта автомашин поступает простейший поток заявок с интенсивностью ? = 0,5 (машин в час). Имеется одно помещение для ремонта. Во дворе станции могут одновременно находиться, ожидая очереди, не более трех машин. Среднее время ремонта одной машины t_об = 1/? = 2 (часа). Определить: а) пропускную способность системы, б) среднее время простоя станции, в) определить, насколько изменятся эти характеристики, если оборудовать второе помещение для ремонта.

Решение. Имеем: ? = 0,5, ? = 0,5, ? = 1, N = 3.

а) По формуле (37), полагая m = 1, находим вероятность того, что пришедшая заявка покинет систему необслуженной:

Относительная пропускная способность системы q = 1- P_н = 0,80.

Абсолютная пропускная способность: Q = ?q = 0,4 (машины в час).

б) среднюю долю времени, которое система будет простаивать: .

в) полагая m = 2, найдем:

q = 1- P_н ? 0,979 (т.е. удовлетворяться будет около 98% всех заявок),

Q = ?q ? 0,49 (машины в час).

Относительное время простоя: (т.е. оборудование будет простаивать около 34% всего времени).

Практика

Анализируется работа междугородного переговорного пункта в небольшом городке. Пункт имеет один телефонный аппарат для переговоров. В среднем за сутки поступает 240 заявок на переговоры. Средняя длительность переговоров (с учётом вызова абонента в другом городе) составляет 5 мин. Никаких ограничений на длину очереди нет. Потоки заявок и обслуживаний простейшие. Определить предельные вероятности состояний и характеристики обслуживания переговорного пункта в стационарном режиме

Литература

1. Т.Л. Саати. Элементы теории массового обслуживания и ее приложения. - М.: Изд-во “Советское радио”, 1971 г., 520 с.

2. Л. Клейнрок. Теория массового обслуживания. - М.: Машиностроение, 1979 г., 432 с.

3. В.Ф. Матвеев, В.Г. Ушаков. Системы массового обслуживания. - М.: Изд-во МГУ, 1984 г., 240 с.

4. О.А. Новиков, С.И. Петухов. Прикладные вопросы теории массового обслуживания. - М.: Изд-во “Советское радио”,1969 г., 240 с.

5. В.Я Розенберг, А.И. Прохоров. Что такое теория массового обслуживания. - М.: Изд-во “Советское радио”,1965 г., 256 с.

6. Г.И. Ивченко, В.А. Каштанов. Теория массового обслуживания. - М.: Высш. Школа, 1982 г., 256 с.

7. И.К. Волков, С.М. Зуев. Случайные процессы: Учеб. для вузов. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2000 г., 448 с.

8. Е.С. Вентцель. Теория вероятностей: Учеб. для вузов. - М.: Высш. Школа, 2002 г., 576 с.

Размещено на Allbest.ru