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

Содержание.

Введение.	2
1. Теория массового обслуживания.	3
1.1.Предмет и задачи теории массового обслуживания.	3
1.2. Система массового обслуживания (СМО).	3
1.3. Классификация СМО.	3
1.4. Характеристики СМО.	5
2. Постановка задачи на проектирование.	5
2.1. Формулировка задачи.	5
2.2. Теоретическое представление задачи	5
3.Решение задачи.	7
3.1. Алгоритм моделирования СМО	7
4. Программная реализация.	8
5. Выводы.	9
Заключение.	10
Приложение 1. Результаты работы СМО.	11
Приложение 2. График зависимость абсолютной пропускной способности системы от времени. Зависимость абсолютной пропускной способности системы от времени.	12
Приложение 3. График зависимость относительной пропускной способности системы от времени.	12
Приложение4. График зависимости вероятности отказа системы от времени.	13
Приложение 5. График зависимости количества поступивших и обслуженных заявок в системе от времени.	13
Приложение 6. Листинг программы.	14
Приложение 7. Блок-схемы.
Список литературы.	16

Введение.

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

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

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

Теория массового обслуживания. Основные положения.

1.1. Предмет и задачи теории массового обслуживания.

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

На первичное развитие теории массового обслуживания оказали особое влияние работы датского ученого А.К. Эрланга (1878-1929).

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

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

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

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

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

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

1) поток требований, его характер;

2) множество обслуживающих приборов;

3) дисциплина обслуживания (совокупность правил, задающих процесс обслуживания).

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

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

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

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

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

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

Разомкнутые

Замкнутые

С ожиданием

С отказами

Многоканальные

Одноканальные

Организация отбора заявок

Характер образования очереди

Количество каналов

С ожиданием

Смешанного типа

Без приоритета

С приоритетом

Однородные

Неоднородные

Параллельно

Последовательно

Наличие ограничений на очередь

Дисциплина очереди

Характеристики каналов

Расположение каналов

На длину очереди

На время пребывания в очереди

Первый пришел- первый обслужен

Последний пришел- первый обслужен

Случайный отбор

Абсолютный приоритет

Относительный приоритет

Специальные правила приоритета

Вид ограничения

Правило отбора заявок

Характеристика приоритета

Рис.1 Классификация систем массового обслуживания

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.Постановка задачи на проектирование.

2.1.Формулировка задачи.

Построить модель СМО и исследовать поведение характеристик её эффективности.

Описание системы:

Имеется двухканальная СМО с отказами, на которую поступает два произвольных потока заявок. Поток I имеет интенсивность l₁. Поток II имеет интенсивность l₂ (будем кратко именовать заявки этих потоков: Заявки I и ЗаявкиII). Заявки I имеют пред Заявками II приоритет, состоящий в том, что если Заявка I приходит в систему, когда все каналы заняты и хотя бы один из них обслуживает Заявку II, то пришедшая Заявка I «вытесняет» (выгоняет) Заявку II, становится на её место, а та покидает систему необслуженной. Если Заявка I приходит в момент, когда оба канала обслуживают Заявки I, то она получает отказ и покидает СМО. Заявка II получает отказ, если она приходит в систему в момент, когда оба канала заняты (безразлично какими заявками).

Данные для варианта : l₁ =3, l₂ =1, m₁ =2, m₂ =1.

2.2Теоретическое представление задачи.

На двухканальную СМО поступают заявки двух простейших потоков.

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

1.стационарность;

2.ординарность;

3.отсутствие последействия.

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

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

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

Интенсивность поступления заявок 1-го потока - l1. Интенсивность поступления заявок 2-го потока - l2. Простейшие потоки поступления заявок характеризуются показательным законом распределения. Тогда интервал времени поступления заявок 1-го потока представляет собой случайную величину с одним и тем же распределением вероятностей F (t).

, (1) где l1>0 – постоянная.

Плотность распределения показательного закона задается формулой:

где l1>0, - интенсивность поступления заявок 1-го потока.

Аналогично, интервал времени поступления заявок 2-го потока представляет собой случайную величину с одним и тем же распределением вероятностей F(t).

, (1) где l2>0 – постоянная.

Плотность распределения показательного закона задается формулой:

где l2>0, - интенсивность поступления заявок 2-го потока.

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

Длительность обслуживания заявок 1-го и 2-го потока также представляют собой случайные величины, подчиняющиеся показательному закону распределения. Интенсивность обслуживания заявок 1-го потока - m1. Интенсивность обслуживания заявок 2-го потока - m2. Длительность обслуживания заявок 1-го потока представляет собой случайную величину с одним и тем же распределением вероятностей F (t).

, (1) где m1>0 – постоянная.

Плотность распределения показательного закона задается формулой:

где m1>0, - интенсивность обслуживания заявок 1-го потока.

Аналогично, длительность обслуживания заявок 2-го потока представляет собой случайную величину с одним и тем же распределением вероятностей F(t).

, (1) где m2>0 – постоянная.

Плотность распределения показательного закона задается формулой:

где m2>0, - интенсивность обслуживания заявок 2-го потока.

В рассматриваемой задаче СМО имеет 2 входа, на один из которых поступает случайный поток Заявок I, на другой вход - поток Заявок II.

3. Решение задачи.

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

Начальные условия:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Программная реализация.

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

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

Описание интерфейса:

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

Листинг программы представлен в приложении 6.

Работа программы и получение данных для анализа работы СМО.

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

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

Новые значения интенсивностей:: l₁ =2, l₂ =2, m₁ =2, m₂ =1.

Т.о. исследуем работу системы при следующих вариантах:

	l₁	l₂	m₁	m₂
Вариант 1	2	2	2	1
Вариант 2	3	1	2	1

Результаты работы системы представлены в приложении 1.

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

Для каждого варианта были построены графики зависимостей:
- относительной пропускной способности системы от времени работы;
- абсолютной пропускной способности от времени работы;
- вероятности отказа системы от времени;

- количества обслуженных и поступивших заявок от времени.

Графики представлены в приложениях 2-4.

5. Выводы.

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

1. При времени функционирования системы меньше 2000, работа системы нестабильна, трудно выявить какие-либо закономерности в поведении системы. Поэтому, чтобы сделать выводы об эффективности работы СМО, следует рассматривать её функционирование на временном интервале более 2000 единиц.

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

3. На интервале времени до 3000 значение абсолютной пропускной способности системы хаотически колебалось (особенно это заметно при втором варианте реализации). При времени больше 3000 амплитуда колебаний снизилась, а при времени Т~7000 значения абсолютной пропускной способности системы для обоих вариантов приобретают стационарный характер, и примерно равны 0,004 для первого варианта работы системы и 0,036- для второго.

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

5. Т. к. вероятность отказа системы величена обратная относительной пропускной способности системы, то их поведение аналогично. При малых значениях времени (до 7000) вероятность отказа хаотично колебалась. А при увеличении времени, амплитуда колебания значительно снизилась. Практически вероятность отказа принимает стационарный характер при значении времени больше 17000.

Заключение.

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

Проведенное исследование наиболее наглядно отображают графики, приведенные в приложениях 2-4.

Приложение 1.

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

Характеристики работы СМО	Вар 1	Вар 2	Вар 1	Вар 2	Вар 1	Вар 2	Вар 1	Вар 2	Вар 1	Вар 2	Вар 1	Вар 2	Вар 1	Вар 2	Вар 1	Вар 2
Время работы СМО	100	100	150	150	300	300	500	500	700	700	800	800	1000	1000	2000	2000
Поступило заявок	7	8	3	9	7	3	5	37	7	9	3	5	9	58	41	78
Обслужено заявок	5	3	1	6	4	3	4	21	6	5	2	3	7	36	28	40
Не обслужено заявок	2	5	2	3	3	0	1	16	1	4	1	2	2	22	13	38
Абсолютная пропускная способность системы	0,05	0,03	0,007	0,04	0,013	0,1	0,008	0,042	0,009	0,07	0,003	0,004	0,007	0,036	0,014	0,02
Относительная пропускная способность системы	0,714	0,37	0,33	0,667	0,571	0	0,8	0,568	0,857	0,556	0,667	0,6	0,778	0,62	0,683	0,513
Вероятность отказа, %	28,6	62,5	66,7	33,3	42,9	0	20	43,2	14,3	44,4	33,3	40	22,2	37,9	31,7	48,7

Вар 1	Вар 2	Вар 1	Вар 2	Вар 1	Вар 2	Вар 1	Вар 2	Вар 1	Вар 2	Вар 1	Вар 2	Вар 1	Вар 2	Вар 1	Вар 2	Вар 1	Вар 2	Вар 1	Вар 2
3000	3000	4000	4000	5000	5000	7000	7000	10000	10000	12000	12000	15000	15000	17000	17000	20000	20000	25000	25000
38	318	37	121	48	291	87	413	147	672	88	762	124	975	88	1120	129	989	218	1707
30	187	25	69	33	147	68	222	91	363	60	448	84	533	66	618	89	566	147	932
8	131	12	52	15	144	19	191	56	309	28	314	40	442	22	502	40	423	71	775
0,01	0,006	0,006	0,017	0,007	0,029	0,001	0,032	0,008	0,036	0,005	0,037	0,006	0,036	0,004	0,036	0,004	0,033	0,006	0,037
0,789	0,588	0,776	0,57	0,688	0,505	0,782	0,538	0,619	0,54	0,682	0,588	0,677	0,547	0,75	0,552	0,69	0,572	0,674	0,546
21,1	41,2	32,4	43	31,3	49,5	21,8	46,2	38,1	46	31,8	41,2	32,3	45,3	28	44,8	31	42,8	32,6	45,4

Приложение 2.

[image]

Приложение 3.

[image]

Приложение 4.

[image]

Приложение 5.

[image]

Приложение 6.

Листинг программы.

PROGRAM CAN_SMO;

TYPE

CHANNAL = (FREE, CLAIM1, CLAIM2);

TIME = word;

INTENSITY = word;

STATISTICS = word;

VAR

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;

End;

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

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

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

End;

BEGIN

M:=0;

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

READLN(N);

REPEAT

M:=M+1;

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

randomize;

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_);

repeat

if tc1 = t then

begin

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

CHANNAL1 := FREE;

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

end;

if tc2 = t then

begin

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

CHANNAL2 := FREE;

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

end;

if W(t,l1) then

begin

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;

end;

if W(t,l2) then

begin

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;

end;

inc(t);

until _T_ = t;

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);

readln;

UNTIL M>=N;

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

END.

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

Фомин Г.П., Математические методы и модели в коммерческой деятельности. М: Финансы и статистика, 2001.
Вентцель Е.С., Овчаров Л.А. Теория вероятностей и её инженерные приложения, М: Наука, 1988.
Вентцель Е.С. Исследование операций, М:Наука, 1980.
Лифшиц А.Л. Статистическое моделирование СМО, М., 1978.
Советов Б.А., Яковлев С.А. Моделирование систем, М: Высшая школа, 1985.
Гмурман В.Е. Теория вероятностей и математическая статистика, М: Высшая школа, 2001.

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

Похожие курсовые работы