Алгоритм определения средней длины очереди системы массового обслуживания через обобщенную формулу Хинчина-Поллячека
Рассмотрение стационарного потока заявок, поступающих на обработку в систему массового обслуживания. Определение средней доли недообслуживания через корреляционные моменты числа заявок на интервалах обслуживания. Поступление заявки для обработки.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 29.01.2020 |
| Размер файла | 66,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Алгоритм определения средней длины очереди системы массового обслуживания через обобщенную формулу Хинчина-Поллячека
Б.Я. Лихтциндер,
И.С. Макаров
Аннотация
Рассматривается стационарный ординарный поток заявок, поступающих на обработку в систему массового обслуживания. Определяется средняя доля недообслуживания через корреляционные моменты числа заявок на интервалах обслуживания.
Ключевые слова: система массового обслуживания; теория массового обслуживания; анализ трафика.
При анализе систем массового обслуживания (СМО) наиболее часто применяются две вероятностные характеристики распределения. Это распределение интервалов х между соседними заявками и распределение интервалов времени обработки заявок .
На основе указанных распределений легко определяются параметры
и ,
входящие в формулу Хинчина - Полячека:
, (1)
где - средняя длина очереди; - среднее время обслуживания заявки; - средний интервал между соседними заявками; - дисперсия времени обработки заявок.
Существенным ограничением формулы (1) является ее применимость исключительно к простейшим потокам, для которых интервалы между заявками распределены экспоненциально.
Имеется много попыток модернизации формулы (1) с целью ее применения для неэкспоненциальных потоков заявок [1]. Однако все полученные результаты применимы лишь для слабо изменяющихся входных потоков, для которых коэффициент вариации интервалов между заявками не превышает единицу. Современные мультисервисные телекоммуникационные сети имеют входные потоки пакетов, для которых коэффициент вариации в несколько раз превышает единицу. К таким потокам применение аналитических соотношений, указанных в [1], становится невозможным.
Вместе с тем Л. Клейнроком [2] показано, что длина очереди одноприборной СМО в общем случае определяется случайной величиной m - числом поступивших заявок, приходящихся на одну обработанную заявку.
Рассмотрим предлагаемый алгоритм [3] на конкретном примере. Предположим, что все заявки, поступающие в СМО, имеют одинаковое время обслуживания и алгоритм обслуживания FIFO. Поток заявок показан на рис. 1.
Процесс обработки заявок в любой СМО всегда состоит из последовательности чередующихся периодов занятости обслуживающего прибора (прибор обрабатывает заявки) и периодов простоя, в течение которых заявки в обслуживающем приборе отсутствуют.
Предположим, что перед началом рассмотрения СМО была свободной, поэтому с приходом первой заявки период простоя завершается и начинается период занятости (заявка начинает обрабатываться обслуживающим прибором). В течение интервала временивначале поступают четыре заявки (первая, вторая, третья и четвертая) (рис. 2).
Заявка с номером один сразу же поступает в обслуживающий прибор, а остальные три заявки становятся в очередь (рис. 3). В течение следующего интервала времени в обслуживающем приборе находится заявка с номером два, при этом очередь уменьшается на одну заявку. Аналогичное уменьшение очереди происходит при поступлении в обслуживающий прибор заявки с номером три. В течение следующего интервала ф, когда происходит обработка четвертой заявки, в СМО поступают еще две с номерами пять и шесть, которые становятся в очередь.
Так последовательно происходит непрерывная обработка всех заявок, включая заявку с номером девять. Если интервал между очередными заявками 9 и 10 окажется достаточно большим, таким, что во время обработки заявки с номером 9 не успеет поступить очередная заявка с номером 10, то непрерывный процесс обработки (период занятости) закончится и наступит период простоя. Период простоя длится до момента появления заявки с номером 10.
Рис. 1. Поступление заявок в систему
Рис. 2. Поступление заявки в течение интервалов обработки
Рис. 3. Формирование очередей на каждом интервале обработки
Поступление любой заявки в систему сопровождается появлением некоторой работы, связанной со временем, необходимым на обслуживание заявки.
Обозначим число заявок, поступивших в -й интервал , через . Так, в течение первого интервала в систему поступило заявки. Поскольку первый интервал начинается непосредственно после периода простоя (система свободна), заявка с номером один сразу попадает на обслуживание, а заявки вторая, третья и четвертая образуют очередь. Обозначим длину очереди, образующуюся на -м интервале обработки, через . Следовательно, очередь на первом интервале . Очевидно, что очередь на интервале , предшествующем первому и расположенном в периоде простоя, .
Из анализа рис. 3 следует простое рекуррентное соотношение
(2)
Здесь необходимо подчеркнуть, что все переменные составляют целые, неотрицательные числа заявок.
Очевидно, что на всех участках , соответствующих периодам простоя, значения будут равны нулю и указанные временные участки из рассмотрения исключаются автоматически.
Однако очередь может отсутствовать и в период занятости системы, как это происходит на промежутке времени обработки заявки с номером 9, показанном на рис. 3. Об окончании периода занятости обслуживающего прибора и начале периода простоя на промежутке свидетельствует одновременное равенство нулю величин и .
Уравнения (2) могут быть объединены в одно уравнение:
, (3)
где , если ; , если .
Обозначим , поскольку - это постоянное время обработки одной заявки. заявка корреляционный обработка
Обратим внимание на то, что ; .
Введем обозначение: - средняя длина очереди на всех промежутках , включая промежутки простоя процессора.
Из соотношения (3) определим второй начальный момент.
Учитывая, что при достаточно больших значениях
,
а также, что , возведя в квадрат левую и правую части (3), после соответствующих преобразований получим
. (4)
Определим
.
Следовательно,
. (5)
Определим ковариацию последовательностей и на интервале времени :
Подставляя в (4), получим
.
Обозначим .
Получим окончательно:
. (6)
Выражение (6) обобщает известную формулу Хинчина - Полячека и справедливо для СМО с непуассоновскими потоками заявок. В частности, для пуассоновского потока заявок зависимость между величинами и отсутствует, поэтому , а , и мы приходим к формуле Хинчина - Полячека в ее обычном виде.
Библиографический список
1. Вентцель Е.С. Исследование операций. - М.: Наука, Главная редакция физико-математической литературы, 1980. - 208 с.
2. Клейнрок Л. Теория массового обслуживания / Пер. с англ. - М.: Мир, 1979.
3. Лихтциндер Б.Я., Макаров И.С. Определение средней длины очереди СМО через корреляционные моменты числа заявок на интервалах обслуживания // Инфокоммуникационные технологии. - № 1. - 2011. - С. 72-77.
Размещено на Allbest.ru
...Подобные документы
Изучение понятия многофазовых систем. Рассмотрение примеров разомкнутых и замкнутых систем массового обслуживания с ожиданием и с неограниченным потоком заявок. Определение значений среднего времени ожидания заявки при неэкспоненциальном распределении.
контрольная работа [151,5 K], добавлен 16.09.2010Общая характеристика системы массового обслуживания, исходные данные для ее создания. Особенности построения алгоритма имитационной модели задачи о поступлении заявок (клиентов) в канал (парикмахерскую). Описание функционирования математической модели.
курсовая работа [154,1 K], добавлен 19.05.2011Характеристика системы массового обслуживания, куда поступают заявки обслуживания. Особенности моделирования системы массового обслуживания. Имитация работы системы массового обслуживания с относительными приоритетами. Отчеты полного факторного плана.
курсовая работа [1,1 M], добавлен 14.07.2012Определение характеристик системы массового обслуживания – вероятность обслуживания заявки, занятости любого канала системы, среднее число занятых каналов. Описание блок-схемы алгоритма. Разработка имитационной и аналитической моделей и их сравнение.
курсовая работа [860,4 K], добавлен 24.12.2013Основное назначение систем массового обслуживания (СМО): обслуживание потока заявок. Моделирование СМО для стоянки такси, определение характеристик эффективности работы в качестве статистических результатов моделирования. Схема процесса функционирования.
курсовая работа [1,2 M], добавлен 27.12.2011Функционирование систем массового обслуживания с разными типами заявок. Построение математической модели, постановка задачи оптимизации среднего времени ожидания. Решение задачи оптимизации системы. Разработка программного кода для оптимизации системы.
дипломная работа [581,7 K], добавлен 27.10.2017Торговый центр как однофазная многоканальная система с одной очередью конечной длины Структура и элементы моделей системы массового обслуживания. Очередь и дисциплины ее обслуживания. Принципы и этапы моделирования средств массового обслуживания на ЭВМ.
лабораторная работа [93,2 K], добавлен 04.06.2009Программа, моделирующая систему массового обслуживания. Изучение режима функционирования обслуживающей системы и исследование явлений, возникающих в процессе обслуживания. Описание программного модуля, руководство пользователя для работы с программой.
курсовая работа [277,5 K], добавлен 20.01.2010Системы, описывающие массовое обслуживание. Разработка системы массового обслуживания для магазинов. Постановка в очередь, порядок обслуживания, выбывание из очереди, периодичность попадания в нее. Описание программного модуля, листинг программы.
курсовая работа [171,8 K], добавлен 20.01.2010Система массового обслуживания как одна из основных моделей, используемых инженерами-системотехниками, примеры: телефонные станции, ремонтные мастерские, билетные кассы. Характеристика и особенности многоканальной системы массового обслуживания.
контрольная работа [404,2 K], добавлен 19.11.2012Построение имитационной модели системы массового обслуживания, список и содержание ее активностей. Блок-схема алгоритма моделирования и текст процедуры. Моделирование случайных независимых величин и процессов. Оптимизация системы массового обслуживания.
курсовая работа [4,0 M], добавлен 28.05.2013Построение модели системы массового обслуживания с помощью ЭВМ с использованием методов имитационного моделирования. Моделирование проводилось с помощью GPSS World Student version, позволяющего достоверно воссоздать систему массового обслуживания.
курсовая работа [555,7 K], добавлен 29.06.2011Моделирование дневного стационара - многоканальной системы массового обслуживания с ожиданием. Определение оптимального числа койко-мест для данного количества клиентов. Практическое решение задачи с помощью программы, реализованной в среде Delphi 7.
курсовая работа [1,9 M], добавлен 15.01.2010Проектирование системы массового обслуживания, состоящей из двух генераторов псевдослучайных величин и электронной вычислительной машины, обрабатывающей поступающие заявки. Разработка структурной схемы и алгоритмической модели проектируемой системы.
курсовая работа [194,5 K], добавлен 30.10.2013Определение назначения и описание функций имитационных моделей стохастических процессов систем массового обслуживания. Разработка модели описанной системы в виде Q-схемы и программы на языке GPSS и C#. Основные показатели работы имитационной модели.
курсовая работа [487,4 K], добавлен 18.12.2014Served Time Generator как генератор интервалов времени обслуживания, общая характеристика. Способы построения модели многоканальной сети массового обслуживания с отказами с использованием блоков библиотеки SimEvents, рассмотрение особенностей сетей.
лабораторная работа [176,8 K], добавлен 20.05.2013Компоненты и классификация систем массового обслуживания. Разработка СМО для лечебно-профилактического центра. Графическое представление СМО регистратуры ЛПЦ. Исследование режима функционирования обслуживающей системы. Алгоритм работы поликлиники.
курсовая работа [715,3 K], добавлен 28.01.2016Технология разработки и тестирования программного обеспечения в среде Visual Studio на примере создания программы моделирования систем массового обслуживания. Аналитические и имитационные методы моделирования с разными дисциплинами обслуживания заявок.
дипломная работа [1,1 M], добавлен 09.09.2012Программа, моделирующая систему массового обслуживания (СМО). Моделирование программы имитации работы турникетов на стадионе (многоканальная СМО) в визуальной среде Delphi 7. Описание программного модуля, листинг программы и руководство пользователя.
курсовая работа [3,8 M], добавлен 20.08.2009Основные направления в численном анализе ТМО. Системы массового обслуживания, поведение которых описывается марковскими процессами при некотором расширении пространства состояний. Метод имитационного моделирования для исследования произвольных СМО.
учебное пособие [785,1 K], добавлен 12.10.2010
