Содержание . Введение . 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 PA S CKAL. 1. Теория массового обслуживания . Основные положения. 1.1. Предмет и задачи теории массового обслуживания. Теория массового обслуживания опирается на теорию вероятностей и математическую статистику. На первичное развитие теории массового обслуживания оказали особое влияние работы датского ученого А.К . Эрланга (1878-1929). Теория массового обслуживания – область прикладной математики , занимающаяся ан а лизом процессов в системах производства , обслуживания , управления , в котор ых однородные события повторяются многократно , например , на предприятиях бытового обслуживания ; в с и стемах приема , переработки и передачи информации ; автоматических линиях производства и др . Предметом теории массового обслуживания является установление за висимостей между характером потока заявок , числом каналов обслуживан 6ия , производительностью отдельного к а нала и эффективным обслуживанием с целью нахождения наилучших путей управления этими процессами. Задача теории массового обслуживания – установить зав исимость результирующих п о казателей работы системы массового обслуживания (вероятности того , что заявка будет обсл у жена ; математического ожидания числа обслуженных заявок и т.д .) от входных показателей (к о личества каналов в системе , параметров входящего по тока заявок и т.д .). Результирующими п о казателями или интересующими нас характеристиками СМО являются – показатели эффекти в ности СМО , которые описывают способна ли данная система справляться с потоком заявок. Задачи теории массового обслуживания носят опти мизационный характер и в конечном итоге включают экономический аспект по определению такого варианта системы , при котором будет обеспечен минимум суммарных затрат от ожидания обслуживания , потерь времени и р е сурсов на обслуживание и простоев каналов обслуж ивания. 1.2. Система массового обслуживания. Система обслуживания считается заданной , если известны : 1) поток требований , его характер ; 2) множество обслуживающих приборов ; 3) дисциплина обслуживания (совокупность правил , задающих процесс обслужив ания ). Каждая СМО состоит из какого-то числа обслуживающих единиц , которые называются каналами обслуживания . В качестве каналов могут фигурировать : линии связи , различные пр и боры , лица , выполняющие те или иные операции и т.п Всякая СМО предназначена для о бслуживания какого-то потока заявок , поступающих в какие-то случайные моменты времени . Обслуживание заявок продолжается какое-то случайное время , после чего канал освобождается и готов к приему следующей заявки . Случайный характер потока заявок и времен о б служивания приводит к тому , что в какие-то периоды времени на входе СМО скапливается излишне большое число заявок (они либо становятся в очередь , либо пок и дают СМО не обслуженными ); в другие же периоды СМО будет работать с недогрузкой или в о обще простаиват ь. Процесс работы СМО представляет собой случайный процесс с дискретными состояниями и непрерывным временем ; состояние СМО меняется скачком в моменты появления каких-то с о бытий ( или прихода новой заявки , или окончания обслуживания , или момента , когда заяв ка , к о торой надоело ждать , покидает очередь ). 1.3. Классификация СМО . Для облегчения процесса моделирования используют классификацию СМО по различным признакам , для которых пригодны определенные группы методов и моделей теории массового обслуживания , упр ощающие подбор адекватных математических моделей к решению задач о б служивания в коммерческой деятельности .(см . рис .1) 1. 4. Характеристики СМО. Перечень характеристик систем мас сового обслуживания можно представить следующим образом : · среднее время обслуживания ; · среднее время ожидания в очереди ; · среднее время пребывания в СМО ; · средняя длина очереди ; · среднее число заявок в СМО ; · количество каналов обслуживания ; · интенс ивность входного потока заявок ; · интенсивность обслуживания ; · интенсивность нагрузки ; · коэффициент нагрузки ; · относительная пропускная способность ; · абсолютная пропускная способность ; · доля времени простоя СМО ; · доля обслуженных заявок ; · доля потер янных заявок ; · среднее число занятых каналов ; · среднее число свободных каналов ; · коэффициент загрузки каналов ; · среднее время простоя каналов. 2.Постановка задачи на проектирование. 2.1.Формулировка задачи. Построить модель СМО и исследовать поведен ие характеристик её эффективности. Описание системы : Имеется двухканальная СМО с отказами , на которую поступает два произвольных потока заявок . Поток I имеет интенсивность 1 . Поток II имеет интенсивность 2 (будем кратко имен о вать заявки этих потоков : Заявки I и Заявки II ). Заявки I имеют пред Заявками II приоритет , с о стоящий в том , что если Заявка I приходит в систему , когда все каналы заняты и хотя бы один из них обслуживает Заявку II , то прише дшая Заявка I «вытесняет» (выгоняет ) Заявку II , становится на её место , а та покидает систему необслуженной . Если Заявка I приходит в момент , когда оба канала обслуживают Заявки I , то она получает отказ и покидает СМО . Заявка II получает отказ , если она пр иходит в систему в момент , когда оба канала заняты (безразлично какими заявками ). Данные для варианта : 1 =3, 2 =1, 1 =2, 2 =1. 2.2Теоретическое представление задачи. На двухканальную СМО поступают заявки двух простейших потоков. Простейшим потоком называется поток , обладающий следующими свойствами : 1.стационарность ; 2.ординарность ; 3.отсутствие последействия. Поток событий наз ывается стационарным , если вероятность попадания того или иного числа событий на участок времени длиной зависит только от длины участка и не з а висит от того , где именно на оси времени расположен этот участок. Поток событий н азывается ординарным, если вероятность попадания на элемента р ный участок t двух или более событий пренебрежимо мала по сравнению с вероятностью попадания одного события . Ординарность означает , что поток прореженный , т.е . между л ю быми двумя событиями есть временной интервал. Поток событий называется потоком без последействия , если для любых , не пер е крывающихся участков времени число событий , попадающих на один из них , не зависит от числа событий , попадающих на другие . Это означа ет , что заявки попадают в систему не зав и симо друг от друга. Интенсивность поступления заявок 1-го потока - 1. Интенсивность поступления з а явок 2-го потока - 2. Простейшие потоки поступления з аявок характеризуются показател ь ным законом распределения . Тогда интервал времени поступления заявок 1-го потока пре д ставляет собой случайную величину с одним и тем же распределением вероятностей F ( t ). , (1) где 1 0 – постоянная. Плотность распределения показательного закона задается формулой : где 1>0, - интенсивность поступления заявок 1-го потока. Аналогично , интервал времени поступления заявок 2-го потока представляет с о бой случайную величину с одним и тем же распреде лением вероятностей F(t). , (1) где 2 0 – постоянная. Плотность распределения показательного за кона задается формулой : где 2>0, - интенсивность поступления заявок 2-го потока. Необходимо также учесть , что моделируемая си стема массового обслуживания явл я ется СМО с отказами и с абсолютным приоритетом . Т.е . заявки 1 имеют перед заявками 2 приоритет , состоящий в том , что если заявка 1 приходит в систему , когда все каналы заняты и хотя бы один из них обслуживает заявку 2, то п ришедшая заявка 1 вытесняет заявку 2, ст а новится на ее место , а та покидает систему не обслуженной . Если заявка 1 приходит в сист е му в момент , когда оба канала обслуживают заявку 1, то она покидает СМО . Заявка 2 получ а ет отказ , если она приходит в систему в момент , когда оба канала заняты , безразлично как и ми заявками. Длительность обслуживания заявок 1-го и 2-го потока также представляют собой сл у чайные величины , подчиняющиеся показательному закону распределения . Интенсивность обслуживания заявок 1-го поток а - 1. Интенсивность обслуживания заявок 2-го потока - 2. Длительность обслуживания заявок 1-го потока представляет собой случайную величину с одним и тем же распределением вероятностей F (t). , (1) где 1 0 – постоянная. Плотность распределения показательного закона задается формулой : где 1>0, - интенсивность обслуживания заявок 1-го потока. Аналогично , длительность обслуживания заявок 2-го потока представляе т собой сл у чайную величину с одним и тем же распределением вероятностей F(t). , (1) где 2 0 – п остоянная. Плотность распределения показательного закона задается формулой : где 2>0, - интенсивность обслуживания заявок 2-го потока. В рассматриваемой задаче СМО имеет 2 входа , на один из которых поступает случайный поток Заявок I , на другой вход - поток Заявок II . 3. Решение задачи. 3.1. Алгоритм моделирования СМО. Начальные условия : 1) Рассматриваемая в задаче СМО пред ставляет собой СМО с : · Двухканальным обслуживанием ; · Двухканальным входным потоком ( имеет 2 входа , на один из которых поступают случа й ный поток Заявок I , на другой вход – поток Заявок II ). 2) Определение времен поступления и обслуживания заявок : · В ремена поступления и обслуживания заявок генерируются случайно с заданным показател ь ным законом распределения ; · Интенсивности поступления и обслуживания заявок заданы ; 3) Функционирование рассматриваемой СМО : · Каждый канал обслуживает в каждый момент в ремени одну заявку ; · Если в момент поступления новой заявки свободен хотя бы один канал , то пришедшая зая в ка поступает на обслуживание ; · Если отсутствуют Заявки то система простаивает. 4) Дисциплина обслуживания : · Приоритет Заявок I : если система за нята (оба канала обслуживают заявки ), причем один из каналов занят Заявкой II , Заявка I вытесняют Заявку II ; Заявка II покидает систему необсл у женной ; · Если к моменту поступления Заявки II оба канала заняты , Заявка II не обслуживается ; · Если к моменту поступления Заявки I оба канала обслуживают Заявки I , поступившая Заявка I покидает систему необслуженной ; Задача моделирования : зная параметры входных потоков заявок промоделировать повед е ние системы и вычислить её основные характеристики её эффек тивности . Меняя величину Т от меньших значений до больших (интервал времени , в течении которого происходит случайный процесс поступления заявок 1-го и 2-го потока в СМО на обслуживание ), можно найти изм е нения критерия эффективности функционирования и в ыбрать оптимальный. Критерии эффективности функционирования СМО : · Вероятность отказа ; · Относительная пропускная способность ; · Абсолютная пропускная способность ; Принцип моделирования : · Вводим начальные условия : общее время работы системы , значен ия интенсивностей потоков заявок ; число реализаций работы системы ; · Генерируем моменты времени , в которые прибывают заявки , последовательность прихода Заявок I Заявок II , время обслуживания каждой пришедшей заявки ; · Считаем сколько заявок было обслуже но , а сколько получило отказ ; · Рассчитываем критерий эффективности СМО : 4. Программная реализация. Программа была разработана в среде программирования Turbo Pascal . Алгоритм функци о нирования программы заключается в следующем : после считывани я введенных пользователем параметров , производится генерация моментов появления Заявок . Затем выполняется процед у ра , реализующая СМО , представляющая собой цикл с условием выхода по истечению времени функционирования СМО . Значения интенсивностей появления з аявок в системе и обслуживания заявок заданы в программе в виде констант. Отсчёт внутреннего времени СМО выполняется с помощью приращения переменной . В текущий момент времени производится проверка моментов появления заявки . Если заявка п оявилась , когда один из каналов был свободен , заявка поступает на обслуживание в свободный канал . В противном случае при появлении заявки II , она получает отказ (соответственно увел и чивается число необслуженных заявок ). При появлении Заявки I , она не обслу живается в случае занятости обоих каналов заявками I . При занятости хотя бы одного канала Заявкой II , Заявка I становится на место Заявки II , ( Заявка II покидает систему необслуженной , увеличивается кол и чество необслуженных заявок ). Описание интерфейса : При каждом новом запуске программы сначала вводится число реализаций работы с и стемы , затем при каждой новой реализации вводится время функционирования СМО – Т . При поступлении новой заявки программа выводит сообщение (Поступила заявка 1, Поступила Зая в ка 2) .Программа выводит сообщения об обслуживании /необслуживании вновь поступившей з а явки . Затем , по окончании времени функционирования системы выводится сколько заявок п о ступило и сколько из них было обслужено , а сколько получило отказ . Далее программой прои з в одится расчет и вывод основных выбранных характеристик СМО. Листинг программы представлен в приложении 6. Работа программы и получение данных для анализа работы СМО. Чтобы исследовать поведение смоделированной СМО при различных значениях времени функцион ирования , зададим число реализаций программы равным 18. Причем , при каждой н о вой реализации , будем задавать больший интервал времени функционирования системы . Интересно также пронаблюдать поведение СМО при изменяющихся значениях инте н сивностей появления заявок в системе . Поэтому изменим значения этих констант в программе и пронаблюдаем поведение СМО . Значения интенсивностей поступления заявок 1 уменьшим на 1, а заявок 2- увеличим на 1. Новые значения интенсивностей : : 1 =2, 2 =2, 1 =2, 2 =1. Т.о . исследуем работу системы при следующих вариантах : 1 2 1 2 Вариант 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,0 33 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. Приложение 3. Приложение 4. Приложение 5. Приложение 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 := FR EE; 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 i nc(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); w riteln(' Канал 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. Список литературы. 1. Фомин Г.П ., Математические методы и модели в коммерческой деятельности . М : Финансы и статистика , 2001. 2. Вентцель Е.С ., Овчаров Л.А . Теория вероятностей и её инженерные прилож е ния , М : Наука , 1988. 3. Вентцель Е.С . Исследование операци й , М :Наука , 1980. 4. Лифшиц А.Л . Статистическое моделирование СМО , М ., 1978. 5. Советов Б.А ., Яковлев С.А . Моделирование систем , М : Высшая школа , 1985. 6. Гмурман В.Е . Теория вероятностей и математическая статистика , М : Высшая школа , 2001.