ВВЕДЕНИЕ

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

1.1 Общие понятие теории массового обслуживания

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

1.3 Графы состояний СМО

1.4 Случайные процессы

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

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

2.2 Процессы «рождения – гибели»

2.3 Экономико-математическая постановка задач массового обслуживания

Глава III. МОДЕЛИ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ

3.1 Одноканальная СМО с отказами в обслуживании

3.2 Многоканальная СМО с отказами в обслуживании

3.3 Модель многофазной системы обслуживания туристов

3.4 Одноканальная СМО с ограниченной длиной очереди

3.5 Одноканальная СМО с неограниченной очередью

3.6 Многоканальная СМО с ограниченной длиной очереди

3.7 Многоканальная СМО с неограниченной очередью

3.8 Анализ системы массового обслуживания супермаркета

ЗАКЛЮЧЕНИЕ

Введение

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

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

Теория массового обслуживания - область прикладной математики, занимающаяся анализом процессов в системах производства, обслуживания, управления, в которых однородные события повторяются многократно, например, на предприятиях бытового обслуживания; в системах приема, переработки и передачи информации; автоматических линиях производства и др. Большой вклад в развитие этой теории внесли российские математики А.Я. Хинчин, Б.В. Гнеденко, А.Н. Колмогоров, Е.С. Вентцель и др.

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

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

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

Глава I . Постановка задач массового обслуживание

1.1 Общие понятие теории массового обслуживания

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

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

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

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

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

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

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

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

Действительно, продолжительность пребывания покупателя в супермаркете зависит, с одной стороны, от личностных качеств покупателя, его запросов, от ассортимента товаров, который он собирается приобрести, а с другой - от формы организации обслуживания и обслуживающего персонала, что может значительно повлиять на время пребывания покупателя в супермаркете и интенсивность обслуживания. Например, овладение кассирами-контролерами работы «слепым» методом на кассовом аппарате позволило увеличить пропускную способность узлов расчета в 1,3 раза и сэкономить время, затрачиваемое на расчеты с покупателями по каждой кассе более чем на 1,5 ч в день. Внедрение единого узла расчета в супермаркете дает ощутимые преимущества покупателю. Так, если при традиционной форме расчетов время обслуживания одного покупателя составляло в среднем 1,5 мин, то при введении единого узла расчета - 67 с. Из них 44 с уходят на оформление покупки в секции и 23 с непосредственно на расчеты за покупки. Если покупатель делает несколько покупок в разных секциях, то потери времени сокращаются при приобретении двух покупок в 1,4 раза, трех - в 1,9, пяти - в 2,9 раза.

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

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

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

23 октября 2013 в 14:22

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

• Программирование ,
• ООП ,
• Параллельное программирование

На Хабре крайне мало информации о таком языке программирования как Squeak . Я попытаюсь рассказать о нем в контексте моделирования систем массового обслуживания . Покажу как написать простой класс, расскажу его структуру и использую его в программе, которая будет обслуживать заявки посредством нескольких каналов.

Пару слов о Squeak

Squeak это открытая, кросс-платформенная реализация языка программирования Smalltalk-80 c динамической типизацией и сборщиком мусора. Интерфейс довольно специфический, но вполне удобный для отладки и анализа. Squeak полностью отвечает концепции ООП. Все состоит из объектов, даже конструкции if-then-else, for, while реализованы с их помощью. Весь синтаксис сводится к посылке объекту сообщения в виде:

<объект> <сообщение>

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

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

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

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

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

Немного математики

Для пуассоновского потока число событий X , попадающих в интервал длины τ (тау), примыкающий к точке t , распределено по закону Пуассона:
где a (t, τ) - среднее число событий, наступающих на интервале времени τ .
Среднее число событий, наступающих в единицу времени, равно λ(t) . Следовательно, среднее число событий на интервале времени τ , примыкающему к моменту времени t , будет равно:

Время T между двумя событиями при λ(t) = const = λ распределено по закону:
Плотность распределения случайной величины T имеет вид:
Для получения псевдослучайных пуассоновских последовательностей интервалов времени t i решают уравнение:
где r i - равномерно распределенное на интервале случайное число.
В нашем случае это дает выражение:

По генерации случайных чисел можно писать целые тома. Здесь же, для генерации равномерно распределенных на интервале целых чисел используем следующий алгоритм:
где R i - очередное случайное целое число;
Р - некоторое большое простое число (например 2311);
Q - целое число - верхняя граница интервала, например, 2 21 = 2097152;
rem - операция получения остатка от деления целых чисел.

Начальное значение R 0 обычно задают произвольно, например, используя показания таймера:
Time totalSeconds
Для получения равномерно распределенных на интервале чисел воспользуемся оператором языка:

Класс Rand

Для получения равномерно распределенных на интервале случайных чисел создаем класс - генератор вещественных чисел:

Float variableWordSubclass: #Rand "имя класса" instanceVariableNames: "" "переменные экземпляра" classVariableNames: "R" "переменные класса" poolDictionaries: "" "общие словари" category: "Sample" "имя категории"
Методы:

"Инициализация" init R:= Time totalSeconds.next "Следующее псевдослучайное число" next R:= (R * 2311 + 1) rem: 2097152. ^(R/2097152) asFloat
Для установки начального состояния датчика посылаем сообщение Rand init .
Для получения очередного случайного числа посылаем Rand next .

Программа обработки заявок

Итак, в качестве простенького примера сделаем следующее. Пусть нам необходимо промоделировать обслуживание регулярного потока заявок от одного источника со случайным интервалом времени между заявками. Имеется два канала различной производительности, позволяющих обслуживать заявки за 2 и 7 единиц времени соответственно. Необходимо зарегистрировать число заявок, обслуженных каждым каналом на интервале 100 единиц времени.

Код на Squeak

"Объявление временных переменных" | proc1 proc2 t1 t2 s1 s2 sysPriority queue continue r | "Начальные установки переменных" Rand init. SysTime:= 0. s1:= 0. s2:= 0. t1:= -1. t2:= -1. continue:= true. sysPriority:= Processor activeProcess priority. "Текущий приоритет" queue:= Semaphore new. "Модель очереди заявок" "Создание процесса - модели канала 1" (Process forContext: [ proc1:= Processor activeProcess. whileTrue: "Цикл обслуживания" [ queue wait. "Ждать заявку" t1:= SysTime + 2. "Следующее время активизации" s1:= s1 + 1. proc1 suspend. "Приостановить процесс в ожидании окончания обслуживания" ]. proc1:= nil. "Удалить ссылку на процесс 1" ] priority: (sysPriority + 1)) resume. "Новый приоритет больше фонового" "Создание процесса - модели канала 2" (Process forContext: [ proc2:= Processor activeProcess.. whileTrue: [ queue wait. t2:= SysTime + 7. s2:= s2 + 1. proc2 suspend. ]. proc2:= nil. ] priority: (sysPriority + 1)) resume. "Продолжение описания главного процесса и модели источника" whileTrue: [ r:= (Rand next * 10) rounded. (r = 0) ifTrue: . ((SysTime rem: r) = 0) ifTrue: . "Послать заявку" "Коммутатор процессов обслуживания" (t1 = SysTime) ifTrue: . (t2 = SysTime) ifTrue: . SysTime:= SysTime + 1. "Тикает модельное время" ]. "Показать состояние счетчика заявок" PopUpMenu inform: "proc1: ",(s1 printString),", proc2: ",(s2 printString). continue:= false.

При запуске видим, что процесс 1 успел обработать 31 заявку, а процесс 2 только 11:

Московский государственный технический университет

имени Н.Э. Баумана (Калужский филиал)

Кафедра высшей математики

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

по курсу «Исследование операций»

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

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

Число каналов обслуживания n; максимальная длина очереди т;

Поток поступающих в систему заявок простейший со средней интенсивностью λ и показательным законом распределения времени между поступлением заявок;

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

Сравнить найденные значения показателей с результатами. полученными путем численного решения уравнении Колмогорова для вероятностей состояний системы. Значения параметров СМО приведены в таблице.

Введение

Глава 1. Основные характеристики CМО и показатели их эффективности

1.1 Понятие марковского случайного процесса

1.2 Потоки событий

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

1.4 Финальные вероятности и граф состояний СМО

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

1.6 Основные понятия имитационного моделирования

1.7 Построение имитационных моделей

Глава 2. Аналитическое моделирование СМО

2.1 Граф состояний системы и уравнения Колмогорова

2.2 Расчет показатели эффективности системы по финальным вероятностям

Глава 3. Имитационное моделирование СМО

3.1 Алгоритм метода имитационного моделирования СМО (пошаговый подход)

3.2 Блок-схема программы

3.3 Расчет показателей эффективности СМО на основе результатов ее имитационного моделирования

3.4 Статистическая обработка результатов и их сравнение с результатами аналитического моделирования

Заключение

Литература

Приложение 1

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

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

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

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

В качестве показателей эффективности СМО используются:

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

Относительная пропускная способность (Q), т.е. средняя доля поступивших заявок, обслуживаемых системой;

Вероятность отказа обслуживания заявки (

);

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

Среднее число заявок в СМО (

);

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

);

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

);

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

);

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

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

Вероятность того, что число заявок в очереди превысит определенное значение и т.п.

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

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

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

Процесс называется процессом с дискретными состояниями, если его состояния

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

Процесс работы СМО – это случайный процесс с дискретными состояниями и непрерывным временем.

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

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

1.2 Потоки событий

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

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

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

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

.

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

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

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

За последние десятилетия в самых разных областях народного хозяйства возникла необходимость решения вероятностных задач, связанных с работой систем массового обслуживания. Примерами таких систем служат телефонные станции, ремонтные мастерские, торговые предприятия, билетные кассы и т.д. работа любой системы массового обслуживания состоит в обслуживании поступающего в нее потока требований (вызовы абонентов, при ход покупателей в магазин, требования на выполнение работы в мастерской и т. д.).
Математическая дисциплина, изучающая модели реальных систем массового обслуживания, получила название теории массового обслуживания. Задача теории массового обслуживания - установить зависимость результирующих показателей работы системы массового обслуживания (вероятности того, что требование будет обслужено; математического ожидания числа обслуженных требований и т. д.) от входных показателей (количество приборов в системе, параметров входящего потока требований и т. д.) установить такие зависимости в формульном виде можно только для простых систем массового обслуживания. Изучение же реальных систем проводится путем имитации, или моделирования их работы на ЭВМ с привлечением метода статистических испытаний.
Система массового обслуживания считается заданной, если определены:
1) входящий поток требований, или, иначе говоря, закон распределения, характеризующий моменты времени поступления требований в систему. Первопричину требований называют источником. В дальнейшем условимся считать, что источник располагает неограниченным числом требований и что требования однородны, т. е. различаются только моментами появления в системе;
2) система обслуживания, состоящая из накопителя и узла обслуживания. Последний представляет собой одно или несколько обслуживающих устройств, которые в дальнейшем будем называть приборами. Каждое требование должно поступить на один из приборов, чтобы пройти обслуживание. Может оказаться, что требованиям придется ожидать, пока приборы освободятся. В этом случае требования находятся в накопителе, образуя одну или несколько очередей. Положим, что переход требования из накопителя в узел обслуживания происходит мгновенно;
3) время обслуживания требования каждым прибором, которое является случайной величиной и характеризуется некоторым законом распределения;
4) дисциплина ожидания, т. е. совокупность правил, регламентирующих количество требований, находящихся в один и тот же момент времени в системе. Система, в которой поступившее требование получает отказ, когда все приборы заняты, называется системой без ожидания. Если требование, заставшее все приборы занятыми, становится в очередь и ожидает до тех пор,
пока освободиться один из приборов, то такая система называется чистой системой с ожиданием. Система, в которой требование, заставшее все приборы занятыми, становится в очередь только в том случае, когда число требований, находящихся в системе, не превышает определенного уровня (в противном случае происходит потеря требования), называется смешанной системой обслуживания;
5) дисциплина обслуживания, т. е. совокупность правил, в соответствии с которыми требование выбирается из очереди для обслуживания. Наиболее часто на практике используются следующие правила:
- заявки принимаются к обслуживанию в порядке очереди;
- заявки принимаются к обслуживанию по минимальному времени получения отказа;
- заявки принимаются к обслуживанию в случайном порядке в соответствии с заданными вероятностями;
6) дисциплина очереди, т.е. совокупность правил, в соответствии с которыми требование отдает предпочтение той или иной очереди (если их не сколько) и располагается в выбранной очереди. Например, поступившее требование может занять место в самой короткой очереди; в этой очереди оно может расположиться последним (такая очередь называется упорядоченной), а может пойти на обслуживание вне очереди. Возможны и другие варианты.

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

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

1 Внешнее проектирование

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

2 Внутреннее проектирование - проектирование отдельных элементов
системы

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

3 Формирование реализаций случайного потока заявок

При исследовании сложных систем методом имитационного моделирования существенное внимание уделяется учету случайных факторов.
В качестве математических схем, используемых для формализации действия этих факторов, используются случайные события, случайные величины и случайные процессы (функции). Формирование на ЭВМ реализаций случайных объектов любой природы сводится к выработке и преобразованию случайных чисел. Рассмотрим способ получения возможных значений случайных величин с заданным законом распределения. Для формирования возможных значений случайных величин с заданным законом распределения исходным материалом служат случайные величины, имеющие равномерное распределение в интервале (0, 1). Другими словами, возможные значения xi случайной величины £, имеющей равномерное распределение в интервале (0, 1), могут быть преобразованы в возможные значения yi случайной величины г), закон распределения которой задан. Способ преобразования состоит в том, что из равномерно распределенной совокупности отбираются случайные числа, удовлетворяющие некоторому условию таким образом, чтобы отобранные числа подчинялись заданному закону распределения.
Предположим, что необходимо получить последовательность случайных чисел yi , имеющих функцию плотности 1^(у). Если область определения функции f^y) не ограничена с одной или обеих сторон, необходимо перейти к соответствующему усеченному распределению. Пусть область возможных значений для усеченного распределения равна (a, b).
От случайной величины г), соответствующей функции плотности f ^ y), перейдем к f.
Случайная величина Ъ, будет иметь область возможных значений (0, 1) и функцию плотности f ^(z), задаваемую выражением.
Пусть максимальное значение f^(z) равно f m . Зададим равномерные распределения в интервалах (0, 1) случайных чисел x 2 i-1 и x 2 i. Процедура по лучения последовательности yi случайных чисел, имеющих функцию плотности ^(у), сводится к следующему:
1) из исходной совокупности выбираются пары случайных чисел x2i-1,
2) для этих чисел проверяется справедливость неравенства
х 21 <-- ^[а + (Ъ-а)х 2М ] (3)
m
3) если неравенство (3) выполнено, то очередное число yi определяется из соотношения
yi =a + (b-а)х 21 (4)
При моделировании процессов обслуживания возникает необходимость формирования реализаций случайного потока однородных событий (заявок). Каждое событие потока характеризуется моментом времени tj, в который оно наступает. Чтобы описать случайный поток однородных событий как случайный процесс, достаточно задать закон распределения, характеризующий последовательность случайных величин tj. Для того, чтобы получить реализацию потока однородных событий t1, t2..., tk, необходимо сформировать реализацию z b z 2 ,...,zk k-мерного случайного вектора ££2,..., Sk и вычислить значения ti в соответствии со следующими соотношениями:
t 2 =
Пусть стационарный ординарный поток с ограниченным последействием задан функцией плотности f(z). В соответствии с формулой Пальма (6) найдем функцию плотности f1(z1) для первого интервала z1.
1- Jf (u) du
Теперь можно сформировать случайное число z b как было показано выше, соответствующее функции плотности f1(z1), и получить момент появления первой заявки t1 = z1 . Далее формируем ряд случайных чисел, соответствующих функции плотности f(z), и при помощи соотношения (4) вычисляем значения величин t2, t3 ,.., tk.
4 Обработка результатов моделирования
При реализации моделирующих алгоритмов на ЭВМ вырабатывается информация о состояниях исследуемой системы. Эта информация является исходным материалом для определения приближенных значений искомых величин, или, как принято говорить, оценок для искомых величин.
Оценка вероятности события А вычисляется по формуле
p(A) = mN . (7)
Оценка среднего значения x случайной величины Ъ, вычисляется по
формуле
_ 1 n
k =1
Оценка S 2 для дисперсии случайной величины ^ вычисляется по формуле
1 N 1 (N Л 2
S 2 =1 YA xk 2-5> J (9)
Оценка корреляционного момента К^ для случайных величин Ъ, и ц с возможными значениями x k и y k соответственно вычисляется по формуле
1 N 1 NN
У> [ Ух

5 Пример моделирования СМО
Рассмотрим следующую систему:
1 Требования поступают в случайные моменты времени, при этом
промежуток времени Q между любыми двумя последовательными требованиями имеет показательный закон с параметром i, т. е. функция распределения имеет вид
>0. (11) Система обслуживания состоит из s одинаковых, пронумерованных приборов.
3 Время Т о бсл - случайная величина с равномерным законом распределения на отрезке .
4 Система без ожидания, т.е. требование, заставшее все приборы занятыми, покидает систему.
5 Дисциплина обслуживания такова: если в момент поступления k - го требования первый прибор свободен, то он приступает к обслуживанию требования; если этот прибор занят, а второй свободен, то требование обслуживается вторым прибором, и т.д.
Требуется оценить математические ожидания числа требований, обслуженных системой за время Т и получивших отказ.
За начальный момент расчета выберем момент поступления первого требования Т1=0. Введем следующие обозначения: Тk- момент поступления k-го требования; ti - момент окончания обслуживания требования i-м прибором, i=1, 2, 3, ...,s.
Предположим, что в момент T 1 все приборы свободны.
Первое требование поступает на прибор 1. Время обслуживания этим прибором имеет равномерное распределение на отрезке . Поэтому конкретное значение tобсл этого времени находим по формуле
(12)
где r- значение случайной величины R , равномерно распределенной на отрезке . Прибор 1 будет занят в течение времени t о бсл. Поэтому момент времени t 1 окончания обслуживания требования прибором 1 следует считать равным: t 1 = Т1+ t о бсл.
Затем следует добавить единицу в счетчик обслуженных требований и перейти к рассмотрению следующего требования.
Предположим, что k требований уже рассмотрено. Определим момент Т k+1 поступления (k+1)-го требования. Для этого найдем значение т промежутка времени между последовательными требованиями. Так как этот про межуток имеет показательный закон, то
12
х = - In r (13)
| Ll
где r -очередное значение случайной величины R . Тогда момент посту пления (k+1)-го требования: Т k +1 = Тк+ Т.
Свободен ли в этот момент первый прибор? Для ответа на этот вопрос необходимо проверить условие ti < Tk + i - Если это условие выполнено, то к моменту Т k +1 первый прибор освободился и может обслуживать требование. В этом случае t 1 заменяем на (Т k +1 + t обсл), добавляем единицу в счетчик об служенных требований и переходим к следующему требованию. Если t 1>Т k +1, то первый прибор в момент Т k +1 занят. В этом случае проверяем, свободен ли второй прибор. Если условие i 2< Tk + i выполнено, заменяем t2 на (Т k +1+ t о бсл), добавляем единицу в счетчик обслуженных требований и переходим к следующему требованию. Если t 2>Т k +1, то проверяем условие 1з<Тк+1 и т. д. Eсли при всех i от 1 до s имеет ti >Т k +1, то в момент Т k +1 все приборы заняты. В этом случае прибавляем единицу в счетчик отказов и переходим к рассмотрению следующего требования. Каждый раз, вычислив Т k +1, надо проверить еще ус ловие окончания реализации: Tk + i < T . Если это условие выполнено, то одна реализация процесса функционирования системы воспроизведена и испыта ние заканчивается. В счетчике обслуженных требований и в счетчике отказов находятся числа n обсл и n отк.
Повторив такое испытание n раз (с использованием различных r) и усреднив результаты опытов, определим оценки математических ожиданий числа обслуженных требований и числа требований, получивших отказ:
(14)
(Ji
n j =1
где (n обсл) j и (n отк) j - значения величин n обсл и n отк в j -ом опыте.
13

Список использованных источников
1 Емельянов А.А. Имитационное моделирование экономических процессов [Текст]: Учеб. пособие для вузов / А.А. Емельянов, Е.А. Власова, Р.В. Дума. - М. : Финансы и статистика, 2002. - 368с.
2 Бусленко, Н.П. Моделирование сложных систем [Текст]/ Н.П. Бусленко.- М. : Наука, 1978. - 399с.
3 Советов Б.Я. Моделирование систем [Текст]: Учеб. для вузов / Б.Я. Сове тов, С.А. Яковлев. -М. : Высш. школа, 1985. - 271 с.
4 Советов Б.Я. Моделирование систем [Текст]: Лабораторный практи кум: Учеб. пособие для вузов по специальности: "Автом. сист. обработ. инф. и управл." / Б.Я. Советов, С.А. Яковлев. -М. : Высш. шк., 1989. - 80 с.
5 Максимей И.В. Имитационное моделирование на ЭВМ [Текст]/ Максимей, И.В. -М: РАДИО И СВЯЗЬ, 1988. - 231с.
6 Вентцель Е.С. Теория вероятностей [ Текст ] : учеб. для вузов / Е.С. Вент цель.- М. : Высш. шк., 2001. - 575 с.
7 Гмурман, В.Е. Теория вероятностей и математическая статисти ка [ Текст ] : учеб. пособие / В.Е. Гмурман.- М. : Высш. шк., 2001. - 479 с.
Приложение А
(обязательное)
Примерные темы расчетно-графических работ
1 На травмопункте работает один врач. Длительность лечения больного
и промежутки времени между поступлениями больных - случайные величи ны, распределенные по пуассоновскому закону. По тяжести травм больные делятся на три категории, поступление больного любой категории - случай ное событие с равновероятным распределением. Врач вначале занимается больными с максимально тяжелыми травмами (в порядке их поступления), затем, если таковых нет, больными средней тяжести, и лишь затем - больны ми с легкими травмами. Смоделировать процесс и оценить средние времена ожидания в очереди больных каждой из категорий.
2 В городском автохозяйстве две ремонтные зоны. Первая обслуживает ремонты краткой и средней продолжительности, вторая - средней и долгой. По мере поломок в автохозяйство доставляют транспорт; промежуток време ни между доставками - случайная пуассоновская величина. Продолжительности ремонта - случайная величина с нормальным законом распределения. Смоделировать описанную систему. Оценить средние времена ожидания в очереди транспорта, требующие соответственно краткосрочного, среднесрочного и длительного ремонта.
3 Мини-маркет с одним контролером - кассиром обслуживает покупа телей, входящий поток которых подчиняется закону Пуассона с параметром 20 покупателей/час. Провести моделирование описанного процесса и определить вероятность простоя контролера - кассира среднюю длину очереди, среднее число покупателей в мини-маркете, среднее время ожидания обслуживания, среднее время пребывания покупателей в мини-маркете и дайте оценку его работы.
4 На АТС поступают заявки на междугородние переговоры. Поток зая вок является пуассоновским. В среднем за 1 час поступает 13 заявок. Найдите среднее число заявок, поступающих за сутки, среднее время между появлением заявок. На телефонной станции появляются сбои в работе, если за полчаса на нее поступит более 50 заявок. Найдите вероятность сбоя станции.
5 На станцию технического обслуживания поступает простейший по
ток заявок с интенсивностью 1 автомобиль за 2 ч. Во дворе в очереди может находиться не более 3 машин. Среднее время ремонта - 2 часа. Дайте оценку работы СМО и разработайте рекомендации по улучшению обслуживания.
6 Одна ткачиха обслуживает группу станков, осуществляя по мере необходимости краткосрочное вмешательство, длительность которого - случайная величина. Смоделировать описанную ситуацию. Какова вероятность простоя сразу двух станков. Как велико среднее время простоя одного станка.
7 На междугородней телефонной станции две телефонистки обслуживают общую очередь заказов. Очередной заказ обслуживает та телефонистка, которая первой освободилась. Если обе в момент поступления заказа заняты, звонок аннулируется. Смоделировать процесс, считая входные потоки пуассоновскими.
8 На травмопункте работают два врача. Длительность лечения больно
го и промежутки времени между поступлениями больных - случайные вели чины, распределенные по пуассоновскому закону. По тяжести травм больные делятся на три категории, поступление больного любой категории - случай ное событие с равновероятным распределением. Врач вначале занимается больными с максимально тяжелыми травмами (в порядке их поступления), затем, если таковых нет, больными средней тяжести, и лишь затем - больны ми с легкими травмами. Смоделировать процесс и оценить средние времена ожидания в очереди больных каждой из категорий.
9 На междугородней телефонной станции две телефонистки обслужи
вают общую очередь заказов. Очередной заказ обслуживает та телефонистка,
которая первой освободилась. Если обе в момент поступления заказа заняты, то формируется очередь. Смоделировать процесс, считая входные потоки пу- ассоновскими.
10 В системе передачи данных осуществляется обмен пакетами данных между узлами A и B по дуплексному каналу связи. Пакеты поступают в пункты системы от абонентов с интервалами времени между ними 10 ± 3 мс. Передача пакета занимает 10 мс. В пунктах имеются буферные регистры, ко торые могут хранить два пакета, включая передаваемый. В случае прихода пакета в момент занятости регистров пунктам системы предоставляется вы ход на спутниковую полудуплексную линию связи, которая осуществляет передачу пакетов данных за 10 ± 5 мс. При занятости спутниковой линии па кет получает отказ. Смоделировать обмен информацией в системе передачи данных в течение 1 мин. Определить частоту вызовов спутниковой линии и ее загрузку. В случае возможности отказов определить необходимый для безотказной работы системы объем буферных регистров.
11 Пусть на телефонной станции с одним входом используется обычная система: если абонент занят, то очередь не формируется и надо звонить сно ва. Смоделировать ситуацию: три абонента пытаются дозвониться до одного и того же владельца номера и в случае успеха разговаривают с ним некоторое (случайное по длительности) время. Какова вероятность того, что некто, пы тающийся дозвониться, не сможет это сделать за определенное время Т.
12 Торговая фирма планирует выполнять заказы на приобретение това ров по телефону, для чего необходимо установить соответствующую мини- АТС с несколькими телефонными аппаратами. Если заказ поступает, когда все линии заняты, то клиент получает отказ. Если в момент поступления за явки хотя бы одна линия свободна, то производится переключение на эту линию и оформляется заказ. Интенсивность входящего потока заявок составляет 30 заказов в час. Длительность оформления заявки в среднем равна 5 мин. Определите оптимальное число каналов обслуживания, чтобы обеспечить условие стационарной работы СМО.
13 В магазине самообслуживание 6 контролеров - кассиров. Входящий поток покупателей подчиняется закону Пуассона с интенсивностью 120 чел/час. Один кассир может обслужить 40 человек в час. Определите вероят ность простоя кассира, среднее число покупателей в очереди, среднее время ожидания, среднее число занятых кассиров. Дайте оценку работы СМО.
14 В магазин самообслуживания поступает пуассоновский поток с ин тенсивностью 200 покупателей в час. В течение дня их обслуживают 3 кон тролера-кассира с интенсивностью 90 покупателей в час. Интенсивность входного потока покупателей в часы пик возрастает до величины 400 поку пателей в час, а в часы спада достигает величины 100 покупателей в час. Определите вероятность образования очереди в магазине и среднюю длину очереди в течение дня, а также необходимое число контролеров-кассиров в часы пик и часы спада, обеспечивающие такую же длину очереди и вероятность ее образования, как и в номинальном режиме.
15 Среднее число покупателей, поступающих на узел расчета в магазин самообслуживания 100 чел/час. Кассир может обслужить 60 человек в час. Смоделируйте процесс и определите, какое число кассиров необходимо для того, чтобы вероятность появления очереди не превысила 0.6.
16 Провести моделирование очереди в магазине с одним продавцом при равновероятных законах распределения случайных величин: прихода по купателей и длительности обслуживания (при некотором фиксированном на боре параметров). Получить устойчивые характеристики: средние значения ожидания в очереди покупателем и простой продавца в ожидании прихода покупателей. Оценить их достоверность.
17 Провести моделирование очереди в магазине с одним продавцом при пуассоновских законах распределения случайных величин: прихода по купателей и длительности обслуживания (при некотором фиксированном на боре параметров). Получить устойчивые характеристики: средние значения ожидания в очереди покупателем и простой продавца в ожидании прихода покупателей. Оценить их достоверность.
18 Создайте модель бензоколонки. Найдите показатели качества обслуживания заявок. Определите количество стоек с тем, чтобы очередь не увеличивалась.
19 Среднее число покупателей, поступающих на узел расчета в магазин самообслуживания, 60 человек в час. Кассир может обслужить 35 человек в час. Смоделируйте процесс и определите, какое число кассиров необходимо для того, чтобы вероятность появления очереди не превысила 0.6.
20 Разработайте модель автобусного маршрута с n остановками. Определите показатели эффективности использования СМО.

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

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

ВВЕДЕНИЕ

ГЛАВА 1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

1.1 Системы массового обслуживания c отказами

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

1.3 Простейшая СМО с отказами

1.4 Одноканальная СМО с отказами

1.5 Многоканальная СМО с отказами

1.6 Одноканальная СМО с ограниченной длиной очереди

1.7 Одноканальная СМО с неограниченной очередью

1.8 Многоканальная СМО с ограниченной длиной очереди

1.9 Многоканальная СМО с неограниченной очередью

1.10 Алгоритм моделирования СМО

ГЛАВА 2. ПРАКТИЧЕСКАЯ ЧАСТЬ

ГЛАВА 3. ПРАВИЛА ТЕХНИКИ БЕЗОПАСНОСТИ

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

ВВЕДЕНИЕ

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

Примерами таких систем могут служить: телефонные станции, ремонтные мастерские, билетные кассы, стоянки такси, парикмахерские и т.п.

Темой данного курсового проекта как раз и является решение подобной задачи.

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

Также рассматриваемые процессы являются немарковскими, т.к. важен фактор времени.

Поэтому решение данной задачи построено не на аналитическом описании системы, а на статистическом моделировании.

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

Для достижения цели были поставлены следующие задачи: - Проанализировать особенности управления производственным процессом; - Рассмотреть организацию производственного процесса во времени; - Привести основные варианты сокращения длительности производственного цикла;

Провести анализ методов управления производственным процессом на предприятии;

Рассмотреть особенности моделирования производственного процесса с использованием теории СМО;

Разработать модель производственного процесса и оценить основные характеристики СМО, привести перспективы ее дальнейшей программной реализации.

Закрепления теоретических знаний и получения навыков их практического применения;

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

Во второй главе рассматриваются теоретические материалы системы массового обслуживания. А в третьей вычисляем задачу систем массового обслуживания.

ГЛАВА 1 . ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

1.1 Системы массового обслуживания c отказами

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

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

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

Вместо фразы “поток обслуживания - простейший” часто говорят “время обслуживания - показательное”. Всякая СМО, в которой все потоки простейшие, называется простейшей СМО.

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

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

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

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

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

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

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

Вероятность обслуживания поступившей заявки Q или относительная пропускная способность СМО; Q = А/л;

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

Среднее число заявок в СМО (обслуживаемых или ожидающих в очереди) ;

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

Среднее время пребывания заявки в СМО (в очереди или под обслуживанием) ;

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

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

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

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

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

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

где л - интенсивность потока заявок.

Аналогичная формула (называемая также формулой Литтла) связывает среднее время пребывания заявки в очереди и среднее число заявок в очереди:

Формулы Литтла очень полезны, так как позволяют вычислять не обе характеристики эффективности (среднее время пребывания и среднее число заявок), а только какую-нибудь одну из них.

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

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

где - интенсивность потока обслуживания.

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

Финальные вероятности состояний выражаются формулами:

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

· среднее время обслуживания;

· среднее время ожидания в очереди;

· среднее время пребывания в СМО;

· средняя длина очереди;

· среднее число заявок в СМО;

· количество каналов обслуживания;

· интенсивность входного потока заявок;

· интенсивность обслуживания;

· интенсивность нагрузки;

· коэффициент нагрузки;

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

· абсолютная пропускная способность;

· доля времени простоя СМО;

· доля обслуженных заявок;

· доля потерянных заявок;

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

· среднее число свободных каналов;

· коэффициент загрузки каналов;

· среднее время простоя каналов.

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

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

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

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

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

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

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

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

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

Pm, n= am_e-a ; (m=0,n),

где величина а = пр - среднее число событий, попадающих на промежуток времени t, которое можно определить через интенсивность потока событий X следующим образом: a= л ф

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

n= л t; p= ф/t

где t- весь промежуток времени, на котором рассматривается действие потока событий.

Необходимо определить распределение интервала времени Т между событиями в таком потоке. Поскольку это случайная величина, найдем ее функцию распределения. Как известно из теории вероятностей, интегральная функция распределения F(t) есть вероятность того, что величина T будет меньше времени t.

F(t)=P(T

По условию в течение времени T не должно произойти ни одного события, а на интервале времени t должно появиться хотя бы одно событие. Эта вероятность вычисляется с помощью вероятности противоположного события на промежутке времени (0; t), куда не попало ни одного события, т.е. m = 0, тогда

F(t)=1-P0=1-(a0*e-a)0!=1-e-Xt,t?0

Для малых?t можно получить приближенную формулу, получаемую заменой функции e-Xt, только двумя членами разложения в ряд по степеням?t, тогда вероятность попадания на малый промежуток времени?t хотя бы одного события составляет

P(T

Плотность распределения промежутка времени между двумя последовательными событиями получим, продифференцировав F(t) по времени,

f(t)= л e- л t ,t?0

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

М(Т)= л??0 t*e-лt*dt=1/ л; D(T)=1/ л2 ; у(T)=1/ л.

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

Pk(t)=(лt)k/ k! *e-л t,

где л - интенсивность поступления потока заявок, среднее число событий в СМО за единицу времени, например[чел/мин; руб./час; чеков/час; докум./день; кг./час; т./год] .

Для такого потока заявок время между двумя соседними заявками Т распределено экспоненциально с плотностью вероятности:

ѓ(t)= л e-л t.

Случайное время ожидания в очереди начала обслуживания t тоже можно считать распределенным экспоненциально:

? (tоч)=V*e-v tоч,

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

v=1/Точ,

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

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

?(t обс)=µ*е µ t обс,

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

µ=1/ t обс[чел/мин; руб./час; чеков/час; докум./день; кг./час; т./год] ,

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

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

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

Важным частным случаем потока Пальма является так называемый поток Эрланга.

Этот поток получается «прореживанием» простейшего потока. Такое «прореживание» производится путем отбора по определенному правилу событий из простейшего потока.

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

Можно получить потоки Эрланга любого к-го порядка. Очевидно, простейший поток есть поток Эрланга первого порядка.

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

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

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

1 . 3 Простейшая СМО с отказами

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

S0 - СМО свободна;

S1 - занят один канал, остальные свободны;

...;

Sk - занятоk каналов, остальные свободны (1k n );

…;

Sn - заняты все n каналов.

Финальные вероятности состояний выражаются формулами Эрланга:

где с=л/м.

Характеристики эффективности:

A=(1-pn ); Q = 1-pn ; Pотк= pn ; =(1-pn ).

При больших значениях п вероятности состояний (1*) удобно вычислять через табулированные функции:

(распределение Пуассона) и

,

из которых первую можно выразить через вторую:

Пользуясь этими функциями, формулы Эрланга (1*) можно переписать в виде

.

1.4 Одноканальная СМО с отказами

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

Работу одноканальной СМО n=1 можно представить в виде размеченного графа состояний (3.1).

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

Запишем систему дифференциальных уравнений Колмогорова для вероятностей состояния по изложенным выше правилам:

Откуда получим дифференциальное уравнение для определения вероятности р0(t) состояния S0:

Это уравнение можно решить при начальных условиях в предположении, что система в момент t=0 находилась в состоянии S0, тогда р0(0)=1, р1(0)=0.

В этом случае решение дифференциального уравнения позволяет определить вероятность того, что канал свободен и не занят обслуживанием:

Тогда нетрудно получить выражение для вероятности определения вероятности занятости канала:

Вероятность р0(t) уменьшается с течением времени и в пределе при t>? стремится к величине

а вероятность р1(t) в то же время увеличивается от 0, стремясь в пределе при t>? к величине

Эти пределы вероятностей могут быть получены непосредственно из уравнений Колмогорова при условии

Функции р0(t) и р1(t) определяют переходный процесс в одноканальной СМО и описывают процесс экспоненциального приближения СМО к своему предельному состоянию с постоянной времени характерной для рассматриваемой системы.

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

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

Действительно, р0(t) есть вероятность того, что заявка, пришедшая в момент t, будет принята к обслуживанию. Всего в единицу времени приходит в среднем л заявок и из них обслуживается лр0 заявок.

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

В пределе при t>? практически уже при t>3ф значение относительной пропускной способности будет равно

Абсолютная пропускная способность, определяющая число заявок, обслуживаемых в единицу времени в пределе при t>?, равна:

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

а общее число не обслуженных заявок равно

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

1.5 Многоканальная СМО с отказами

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

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

Туристические фирмы по продаже путевок имеют два, три, четыре и более каналов, как, например, фирма Express-Line.

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

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

S0 - все каналы свободны k=0,

S1 - занят только один канал, k=1,

S2 - заняты только два канала, k=2,

Sk - заняты k каналов,

Sn - заняты все n каналов, k= n.

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

Для перехода системы из состояния Skв Sk-1 безразлично, какой именно из каналов освободиться, поэтому поток событий, переводящий СМО, имеет интенсивность kм, следовательно, поток событий, переводящий систему из Snв Sn-1, имеет интенсивность nм.

Так формулируется классическая задача Эрланга, названная по имени датского инженера - математика- основателя теории массового обслуживания.

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

.

Вычислив все вероятности состояний n - канальной СМО с отказами р0 , р1, р2, …,рk,…, рn, можно найти характеристики системы обслуживания.

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

k=n.

В системах с отказами события отказа и обслуживания составляют полную группу событий, поэтому:

Ротк+Робс=1

На этом основании относительная пропускная способность определяется по формуле

Q = Pобс= 1-Ротк=1-Рn

Абсолютную пропускную способность СМО можно определить по формуле

А=л*Робс

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

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

Коэффициент занятости каналов обслуживанием определятся отношением среднего числа занятых каналов к их общему числу

Вероятность занятости каналов обслуживанием, которая учитывает среднее время занятости tзан и простоя tпр каналов, определяется следующим образом:

Из этого выражения можно определить среднее время простоя каналов

Среднее время пребывания заявки в системе в установившемся режиме определятся формулой Литтла

Тсмо= nз/л.

1.6 Одноканальная СМО с ограниченной длиной очереди

В коммерческой деятельности чаще встречаются СМО с ожиданием (очередью).

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

Граф этой СМО представлен на рис. 3.4 и совпадает с графом рис. 2.1 описывающим процесс «рождения--гибели», с тем отличием, что при наличии только одного канала.

Размеченный граф процесса «рождения - гибели» обслуживания все интенсивности потоков обслуживания равны

Состояния СМО можно представить следующим образом:

S0 - канал обслуживания свободен,

S, - канал обслуживания занят, но очереди нет,

S2- канал обслуживания занят, в очереди стоит одна заявка,

S3- канал обслуживания занят, в очереди стоят две заявки,

Sm+1 - канал обслуживания занят, в очереди все т мест заняты, любая следующая заявка получает отказ.

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

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

с= (1- с )

Эта формула справедлива для всех р, отличных от 1, если же р = 1, то р0 = 1/(т + 2), а все остальные вероятности также равны 1/(т + 2).

Если предположить т = 0, то мы переходим от рассмотрения одноканальной СМО с ожиданием к уже рассмотренной одноканальной СМО с отказами в обслуживании.

Действительно, выражение для предельной вероятности р0в случае т = 0 имеет вид:

pо = м / (л+м)

И в случае л =м имеет величину р0= 1 / 2.

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

Заявка получает отказ, если она поступает в момент времени, когда СМО уже находится в состоянии Sm+1 и, следовательно, все места в очереди да заняты и один канал обслуживает

Поэтому вероятность отказа определяется вероятностью появлением

Состояния Sm+1:

Pотк = pm+1 = сm+1 * p0

Относительная пропускная способность, или доля обслуживаемых заявок, поступающих в единицу времени, определяется выражением

Q = 1- pотк = 1- сm+1 * p0

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

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

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

1 - в очереди стоит одна заявка,

2 - в очереди две заявки,

т-в очереди все места заняты

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

Таблица 1. Закон распределения дискретной случайной величины

Математическое ожидание этой случайной величины равно:

Lоч = 1* p2 +2* p3 +...+ m* pm+1

В общем случае при p ?1 эту сумму можно преобразовать, пользуясь моделями геометрической прогрессии, к более удобному виду:

Lоч = p2 * 1- pm * (m-m*p+1) * p0

В частном случае при р = 1, когда все вероятности pkоказываются равными, можно воспользоваться выражением для суммы членов числового ряда

1+2+3+ m = m (m +1)

Тогда получим формулу

L"оч= m(m+1) * p0 = m(m+1) (p=1).

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

Точ = Lоч/А (при р? 1) и Т1оч= L"оч /А(при р = 1).

Такой результат, когда оказывается, что Точ ~ 1/ л, может показаться странным: с увеличением интенсивности потока заявок как будто бы должна возрастать длина очереди и уменьшается среднее время ожидания. Однако следует иметь в виду, что, во-первых, величина Lоч является функцией от л и м и, во-вторых, рассматриваемая СМО имеет ограниченную длину очереди не более mзаявок.

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

Если отказаться от ограничения на длину очереди, т.е. устремить m--> >?, то случаи р < 1 и р?1 начинают существенно различаться. Записанные выше формулы для вероятностей состояний преобразуются в случае р < 1 к виду

При достаточно большом к вероятностьpk стремится к нулю. Поэтому относительная пропускная способность будет Q= 1, а абсолютная пропускная способность станет равной А --л Q -- л следовательно, обслуживаются все поступившие заявки, причем средняя длина очереди окажется равной:

Lоч =p 2 1-p

а среднее время ожидания по формуле Литтла

Точ = Lоч/А

В пределе р << 1 получаем Точ = с / м т.е. среднее время ожидания быстро уменьшается с увеличением интенсивности потока обслуживания. В противном случае при р? 1 оказывается, что в СМО отсутствует установившийся режим. Обслуживание не успевает за потоком заявок, и очередь неограниченно растет со временем (при t > ?). Предельные вероятности состояний поэтому не могут быть определены: при Q= 1 они равны нулю. Фактически СМО не выполняет своих функций, поскольку она не в состоянии обслужить все поступающие заявки.

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

В качестве одной из характеристик СМО используют среднее время Тсмо пребывания заявки в СМО, включающее среднее время пребывания в очереди и среднее время обслуживания. Эта величина вычисляется по формулам Литтла: если длина очереди ограничена -- среднее число заявок, находящихся в очереди, равно:

Lсмо= m +1 ;2

Тсмо= L смо; при p ?1

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

Тсмо= m +1 при p ?1 2м

1.7 Одноканальная СМО с неограниченной очередью

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

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

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

Если количество товаров, предназначенных для продажи, велико, то в этом случае мы имеем дело с типичным случаем СМО с ожиданием.

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

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

Размеченный граф состояний такой системы приведен на рис. 3.5

Количество возможных состояний ее бесконечно:

Канал свободен, очереди нет, ;

Канал занят обслуживанием, очереди нет, ;

Канал занят, одна заявка в очереди, ;

Канал занят, заявка в очереди.

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

Следует заметить, что для СМО с ограниченной длиной очереди в формуле

имеет место геометрическая прогрессия с первым членом 1 и знаменателем.

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

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

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

Вероятность пребывания в очереди k заявок равна:

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

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

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

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

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

1.8 Многоканальная СМО с ограниченной длиной очереди

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

Все каналы свободны, ;

Занят только один канал (любой), ;

Заняты только два канала (любых), ;

Заняты все каналов, .

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

Заняты все каналов и одна заявка стоит в очереди,

Заняты все каналов и две заявки стоят в очереди,

Заняты все каналов и все мест в очереди,

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

Запишем выражения для предельных вероятностей состояний:

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

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

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

Поэтому вероятность образования очереди равна:

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

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

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

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

Среднее число простаивающих каналов -

Коэффициент занятости (использования) каналов -

Коэффициент простоя каналов -

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

В случае если, эта формула принимает другой вид -

Среднее время ожидания в очереди определяется формулами Литтла -

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

1.9 Многоканальная СМО с неограниченной очередью

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

Размеченный граф состояний представлен на рис 3.7 Он имеет бесконечное число состояний:

S - все каналы свободны, k=0;

S - занят один канал, остальные свободны, k=1;

S - заняты два канала, остальные свободны, k=2;

S - заняты все n каналов, k=n, очереди нет;

S - заняты все n каналов, одна заявка в очереди, k=n+1,

S - заняты все n каналов, r заявок в очереди, k=n+r,

Вероятности состояний получим из формул для многоканальной СМО с ограниченной очередью при переходе к пределу при m.

Следует заметить, что сумма геометрической прогрессии в выражении для p расходится при уровне загрузки p/n>1, очередь будет бесконечно возрастать, а при p/n<1 ряд сходится, что определяет установившийся стационарный режим работы СМО.

Очереди нет

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

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

среднее время ожидания в очереди -

среднее число заявок в СМО -

Вероятность того, что СМО находится в состоянии, когда нет заявок и не занято ни одного канала, определяется выражением

Эта вероятность определяет среднюю долю времени простоя канала обслуживания. Вероятность занятости обслуживанием k заявок -

На этом основании можно определить вероятность, или долю времени занятости всех каналов обслуживанием

Если же все каналы уже заняты обслуживанием, то вероятность состояния определяется выражением

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

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

Среднее время ожидания заявки в очереди по формуле Литтла:

и в системе

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

среднее число свободных каналов:

коэффициент занятости каналов обслуживанием:

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

1.10 Алгоритм моделирования СМО

Рассматриваемая в задаче СМО представляет собой СМО с:

Двухканальным обслуживанием;

Двухканальным входным потоком (имеет 2 входа, на один из которых поступают случайный поток Заявок I, на другой вход - поток Заявок II).

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

· Времена поступления и обслуживания заявок генерируются случайно с заданным показательным законом распределения;

· Интенсивности поступления и обслуживания заявок заданы;

Функционирование рассматриваемой СМО:

Каждый канал обслуживает в каждый момент времени одну заявку;

Если в момент поступления новой заявки свободен хотя бы один канал, то пришедшая заявка поступает на обслуживание;

Если отсутствуют Заявки то система простаивает.

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

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

Если к моменту поступления Заявки II оба канала заняты, Заявка II не обслуживается;

Если к моменту поступления Заявки I оба канала обслуживают Заявки I, поступившая Заявка I покидает систему необслуженной;

Задача моделирования:зная параметры входных потоков заявок промоделировать поведение системы и вычислить её основные характеристики её эффективности. Меняя величину Т от меньших значений до больших (интервал времени, в течении которого происходит случайный процесс поступления заявок 1-го и 2-го потока в СМО на обслуживание), можно найти изменения критерия эффективности функционирования и выбрать оптимальный.

Критерии эффективности функционирования СМО:

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

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

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

Принцип моделирования:

Вводим начальные условия: общее время работы системы, значения интенсивностей потоков заявок; число реализаций работы системы;

Генерируем моменты времени, в которые прибывают заявки, последовательность прихода Заявок I Заявок II, время обслуживания каждой пришедшей заявки;

Считаем сколько заявок было обслужено, а сколько получило отказ;

Рассчитываем критерий эффективности СМО;

ГЛАВА 2 . ПРАКТИЧЕСКАЯ ЧАСТЬ

Рисунок 1. Зависимость ОПСС от времени

PROGRAM CAN_SMO;

CHANNAL = (FREE, CLAIM1, CLAIM2);

INTENSITY = word;

STATISTICS = word;

CHANNAL1, CHANNAL2: CHANNAL;{Каналы }

T_, t, tc1, tc2: TIME; {Время}

l1, l2, n1, n2: INTENSITY;{Интенсивности }

served1, not_served1,

served2, not_served2,

S: STATISTICS; {Статистика}

M,N:INTEGER;{число реализаций}

FUNCTION W(t: TIME; l: INTENSITY) : boolean;{Определяет появилась ли заявка}

Begin {по интенсивности потока l}

if random < l/60 then W:= TRUE else W:= FALSE;

FUNCTION F(t: TIME; n: INTENSITY) : TIME;{Определяет сколько будет обрабатываться заявка}

Begin {по интенсивности обслуживания заявок n}

F:= t +round(60/(n));

Рисунок 2. Зависимость ОППС от времени

WRITELN("ВВЕДИТЕ ЧИСЛО РЕАЛИЗАЦИЙ РАБОТЫ СМО");

writeln(M, "-ая реализация");

CHANNAL1:= FREE; CHANNAL2:= FREE;

l1:= 3; l2:= 1; n1:= 2; n2:= 1;

served1:= 0; not_served1:= 0;

served2:= 0; not_served2:= 0;

write("Введите время исследования СМО - Т: "); readln(_T_);

if CHANNAL1 = CLAIM1 then inc(served1) else inc(served2);

CHANNAL1:= FREE;

writeln("Канал1 выполнил заявку");

if CHANNAL2 = CLAIM1 then inc(served1) else inc(served2);

CHANNAL2:= FREE;

writeln("Канал2 выполнил заявку");

Рисунок 3. График зависимости вероятности отказа в системе от времени

writeln("Поступила заявка1");

if CHANNAL1 = FREE then

begin CHANNAL1:= CLAIM1; tc1:= F(t,n1); writeln("Канал1 принял заявку1"); end

else if CHANNAL2 = FREE then

begin CHANNAL2:= CLAIM1; tc2:= F(t,n1); writeln("Канал2 принял заявку1"); end

else if CHANNAL1 = CLAIM2 then

begin CHANNAL1:= CLAIM1; tc1:= F(t,n1); inc(not_served2); writeln("Канал1 принял заявку1 вместо заявки2"); end

else if CHANNAL2 = CLAIM2 then

begin CHANNAL2:= CLAIM1; tc2:= F(t,n1); inc(not_served2); writeln("Канал2 принял заявку1 вместо заявки2"); end

else begin inc(not_served1); writeln("заявка1 не обслужена"); end;

Рисунок 4. Зависимость числа заявок от времени

writeln("Поступила заявка2");

if CHANNAL1 = FREE then

begin CHANNAL1:= CLAIM2; tc1:= F(t,n2); writeln("Канал1 принял заявку2");end

else if CHANNAL2 = FREE then

begin CHANNAL2:= CLAIM2; tc2:= F(t,n2); writeln("Канал2 принял заявку2");end

else begin inc(not_served2); writeln("заявка2 не обслужена"); end;

S:= served1 + not_served1 + served2 + not_served2;

writeln("время работы СМО ",_T_);

writeln("обслужено каналом1: " ,served1);

writeln("обслужено каналом2: ",served2);

writeln("Поступило заявок: ",S);

writeln("Обслужено заявок: ",served1+served2);

writeln("Не обслужено заявок: ",not_served1+not_served2);

{writeln("Интенсивность поступления заявок в систему: ",(served1+served2)/_T_:2:3);}

writeln("Абсолютная пропускная способность системы: ",(served1+served2)/T:2:3);

writeln("Вероятность отказа: ",(not_served1+not_served2)/S*100:2:1,"%");

writeln("Относительная пропускная способность системы: ",(served1+served2)/S:2:3);

writeln("моделирование закончено");

Таблица 2. Результаты работы СМО

Характеристики работы СМО

Время работы СМО

Поступило заявок

Обслужено заявок

Не обслужено заявок

Абсолютная пропускная способность системы

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

ГЛАВА 3. ПРАВИЛА ТЕХНИКИ БЕЗОПАСНОСТИ

Общее положения

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

· В случае нарушения инструкции студент отстраняется от работы и допускается к занятию только по письменному разрешению преподавателя.

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

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

Перед началом работы:

· Перед началом работы следует убедиться в отсутствии видимых повреждений аппаратуры и проводов. Компьютеры и периферийные устройства должны находиться на столах в устойчивом положении.

· Учащимся категорически запрещается проникать внутрь устройств. Включать устройства можно только по разрешению преподавателя.

При работе в компьютерном классе запрещается:

1. Входить и выходить из класса без разрешения учителя.

2. Опаздывать на урок.

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

4. Работать на компьютере влажными руками.

5. Класть на рабочее место посторонние предметы.

6. Вставать во время работы, поворачиваться по сторонам, разговаривать с соседом.

7. Включать и выключать аппаратуру без разрешения учителя.

8. Нарушать порядок включения и выключения аппаратуры.

9. Трогать клавиатуру и мышь при выключенном компьютере, передвигать мебель и аппаратуру.

10. Трогать экран дисплея, кабели, соединительные провода, разъёмы, вилки и розетки.

11. Подходить к рабочему месту учителя без разрешения

Главная угроза для здоровья человека при работе с ПК - это угроза поражения электрическим током. Поэтому запрещается:

1. Работать на аппаратуре, имеющей видимые дефекты. Открывать системный блок.

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

3. Прикасаться к экрану и к тыльной стороне монитора, клавиатуры.

4. Пытаться самостоятельно устранять неисправности в работе аппаратуры.

5. Работать во влажной одежде и влажными руками

6. Выполнять требования преподавателя и лаборанта; Соблюдать тишину и порядок;

7. Находясь в сети работать только под своим именем и паролем;

8. Соблюдать режим работы (согласно Санитарных правил и норм);

9. Начало и окончание работы производить только по разрешению преподавателя.

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

11. Соблюдать чистоту рабочего места.

12. Окончание работы произвести по разрешению преподавателя.

13. Сдать выполненную работу.

14. Завершить все активные программы и корректно выключить компьютер.

15. Привести рабочее место в порядок.

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

При эксплуатации оборудования необходимо остерегаться: - поражения электрическим током;

- механических повреждений, травм

При возникновении аварийных ситуаций:

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

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

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

Подобные документы

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

курсовая работа , добавлен 07.09.2009


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

курсовая работа , добавлен 15.02.2009


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

контрольная работа , добавлен 01.07.2015


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

курсовая работа , добавлен 08.01.2009


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

реферат , добавлен 08.01.2013


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

дипломная работа , добавлен 23.12.2012


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

курсовая работа , добавлен 25.02.2012


Составление имитационной модели и расчет показателей эффективности системы массового обслуживания по заданны параметрам. Сравнение показателей эффективности с полученными путем численного решения уравнений Колмогорова для вероятностей состояний системы.

курсовая работа , добавлен 17.12.2009


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

курсовая работа , добавлен 26.01.2014


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