Курсовая. Н. В. Сергеева Заведующий кафедрой д ф. м н., доцент
 Скачать 186.1 Kb.
|
|
МИНОБРНАУКИ РОССИИ Федеральное государственное бюджетное образовательное учреждение высшего образования ѕСАРАТОВСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ Н. Г. ЧЕРНЫШЕВСКОГОї Кафедра теории функций и стохастического анализа МОДЕЛИРОВАНИЕ И АНАЛИЗ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ ПУАССОНОВСКИМ ВХОДЯЩИМ ПОТОКОМ ТРЕБОВАНИЙ И РАЗЛИЧНОЙ ДЛИТЕЛЬНОСТЬЮ ИХ ОБСЛУЖИВАНИЯ АВТОРЕФЕРАТ БАКАЛАВРСКОЙ РАБОТЫ студентки 4 курса 412 группы направления 01.03.02 Прикладная математика и информатика механико-математического факультета Ольховой Анны Юрьевны Научный руководитель старший преподаватель Н. В. Сергеева Заведующий кафедрой д. ф.-м. н., доцент С. П. Сидоров Саратов 2019 ВВЕДЕНИЕ Актуальность темы. Каждый день мы сталкиваемся с различными формами обслуживания и обслуживающими системами. В качестве таких си- стем могут выступать телефонные станции, диспетчерские службы таксопар- ков, магазины, салоны красоты, банки, рестораны быстрого обслуживания и т.д. Все эти системы состоят из определенного числа обслуживающих прибо- ров, в качестве которых могут фигурировать различные приборы, аппараты, линии связи, люди и т. п. Главная функция систем массового обслуживания заключается в удовлетворении поступающего в нее потока заявок. Заявки поступают в систему одна за одной в случайные моменты времени, время обслуживания каждой заявки так же случайно. Данная тема актуальна так как имитационное моделирование является мощным инструментом исследования поведения реальных систем. Постро- енные имитационные модели систем массового обслуживания могут приме- няться для расчета экономических характеристик эффективности функцио- нирования реальных систем обслуживания. Методы имитационного модели- рования позволяют собрать необходимую информацию о поведении системы с помощью создания ее компьютеризованной модели. Эта информация так же используется далее для проектирования системы. Целью бакалаврской работы является моделирование и анализ си- стем массового обслуживания с ожиданием с пуассоновским входящим по- током заявок и различной (экспоненциальной, нормальной,постоянной) дли- тельностью их обслуживания. Объект исследования система массового обслуживания с ожиданием с пуассоновским входящим потоком заявок и различной длительностью их обслуживания. Предмет исследования обслуживание заявок поступающих в систе- му массового обслуживания с ожиданием. Для достижения поставленной цели в работе необходимо решить сле- дующие задачи: определить основные понятия, связанные с системами массового обслу- живания; 2 рассмотреть систему массового обслуживания с произвольным распре- делением длительности их обслуживания; построить модель системы массового обслуживания с ожиданием с пуас- соновским входящим потоком заявок и различной длительностью их обслуживания; рассчитать основные практические и теоретические характеристики дан- ной системы; провести сравнительный анализ практических и теоретических харак- теристик. Практическая значимость проводимого исследования состоит в том, что на основании построенной компьютеризированной модели системы массо- вого обслуживания с ожиданием с пуассоновским входящим потоком заявок и различной длительностью их обслуживания можно проводить исследова- ния реально существующих обслуживающих систем, рассчитывать экономи- ческие характеристики эффективности функционирования этих систем. По результатам этих вычислений можно делать выводы о состоятельности и эф- фективности предприятий. Структура и содержание бакалаврской работы. Работа состоит из введения, четырех разделов, заключения, списка использованных источ- ников, состоящего из 20 наименований, и трех приложений.Общий объем ра- боты составляет 54 страницы, включая 3 таблицы и приложения. ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обосновывается актуальность темы работы, формулиру- ется цель работы и решаемые задачи, отмечается практическая значимость полученных результатов. В первом разделе рассмотрены основные понятия теории массового обслуживания. Система массового обслуживания (СМО) производит обслу- живание требований, поступающих в нее из источника требований и возвра- щающихся после обслуживания в источник. Обслуживание требований в си- стеме производится обслуживающими приборами. Система может содержать от одного до бесконечного числа приборов. Система массового обслужива- 3 ния,содержащая один прибор, называется однолинейной, система, содержа- щая не менее двух приборов, многолинейной. В зависимости от реализации в системе возможности ожидания посту- пившими требованиями их обслуживания системы массового обслуживания делятся на три типа: 1) системы с потерями, в которых требования, не нашедшие в момент поступления ни одного свободного прибора, теряются (возвращаются в ис- точник без обслуживания); 2) системы с ожиданием, в которых возможно ожидание любого чис- ла требований, при этом ожидающие требования образуют очередь, длина которой не ограничена; 3) системы с ожиданием и ограничениями, в которых допускается воз- можность образования очереди ограниченной длины. При этом требования, поступившие в систему, когда отсутствуют свободные места для ожидания в очереди, теряются (возвращаются в источник без обслуживания). В системах с ожиданием очередь в общем случае может иметь сложную структуру, являясь некоторым набором очередей. Выбор очередного требо- вания из очереди на обслуживание производится с помощью некоторой дис- циплины обслуживания. Дисциплина обслуживания заключается в правиле постановки заявок в очередь и порядке их выбора из очереди на обслужива- ние, распределении приборов между заявками. Случайная последовательность требований, которые поступают в си- стему обслуживания и которые необходимо обслужить, называется потоком требований. Пуассоновские потоки на практике встречаются очень часто, так как к их образованию приводит суммирование случайных потоков с большими интервалами времени между поступлением требований. Пуассоновский по- ток выделяется особо не только из-за его простоты, но и потому, что при суммировании пуассоновских потоков результирующий поток также будет пуассоновским. Параметры и характеристики систем обслуживания. Системы обслуживания характеризуются пятью величинами: A/S/k/B/Z 4 Буква A характеризует поток требований. В работе рассмотрены только A = M (M arkov) пуассоновский поток требований. Буква S характеризует случайные последовательности длительностей обслуживания на отдельных приборах обслуживания. Будем рассматривать только S = G последова- тельность одинаково распределенных длительностей обслуживания, распре- деление произвольное . Буква k обозначает число обслуживающих приборов в СМО. Буква B - число мест для ожидания в очереди (маскимальная дли- на очереди). Значение B = 0 характеризует систему с потерями, значение 0 6 B 6 ? - комбинированную систему с ожиданием и потерями, а B = ? - чистую систему с ожиданием, то есть бесконечным числом мест для ожи- дания. Буква Z указывает число источников требований. При рассмотрении конкретной системы обслуживания всегда предполагается, что потоки требо- ваний стохастически независимы от последовательности интервалов обслу- живания. В системах массового обслуживания используются следующие обозна- чения: ? - интенсивность входящего потока требований; µ - интенсивность обслуживания требований одним прибором; ? - число приборов в системе; ? - коэффициент использования обслуживающих приборов системы; n - число требований в СМО; n - математическое ожидание (м. о.) числа требований в СМО; b - число требований в очереди СМО; b - м.о числа требований в очереди; g - м.о числа свободных приборов в СМО; h - м.о числа занятых приборов в СМО; u - м.о длительности пребывания требований в СМО; ? - м.о длительности обслуживания требования прибором, ? = 1 µ ; w - м.о длительности пребывания требований в очереди (времени ожи- дания); Z - число источников требований в замкнутой СМО; B - максимальное число требований, которые могут находиться в оче- реди; p n - стационарная вероятность пребывания в СМО точно n требований. 5 Основными числовыми характеристиками для стационарного режима СМО,где V - общее число требований в источниках до начала работы СМО; V может быть конечным или бесконечным, являются: n = V P n=0 np n - м.о. числа требований в СМО; b = V P n=k+1 (n ? ?)p n - м.о. числа требований в очереди; g = ? P n=0 (? ? n)p n -м.о. числа свободных приборов в СМО; h = ? P n=0 np n + ? V P n=?+1 p n - м.о. числа занятых приборов в СМО. Также имеют место соотношения: h + g = ?, h + b = n, ? + w = u. Известен закон сохранения среднего потока требований, согласно которому в стационарном режиме СМО интенсивность выходящего потока равна интенсивности входящего потока. Большое значение для исследования открытых систем, когда входящие требования независимы от выходящих, имеет формула Литтла: n = ?u или b = ?w Система обслуживания типа M/G/1. Эволюция системы массового обслуживания типа M/G/1 описывается немарковским случайным процес- сом. Для анализа этой системы используется метод вложенных цепей Мар- кова, разработанный Пальмом и Кендаллом. Входящий поток требований в систему является пуассоновским с функцией распределения длительности интервалов времени между последовательными требованиями F (t) = 1 ? exp(??t), t ? 0 В системе используется дисциплина обслуживания F CF S. Матрица переходов P = [p ij ](i, j = 0, 1, 2, ...) имеет следующий вид: 6 P = ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 0 ? 1 ? 2 ? 3 ? 0 ? 1 ? 2 ? 3 0 ? 0 ? 1 ? 2 0 0 ? 0 ? 1 0 0 0 ? 0 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? , где ? k def = P (v n+1 = k) Формула Полячека Хинчина, позволяющая вычислить среднее число требований в системе типа M/G/1 имеет вид q = ? + ? 2 (1 + C 2 b ) 2(1 ? ?) Величины n для среднего числа требований в системе и b для среднего числа требований в очереди (не считая обслуживаемого требования) связаны соотношением b = n ? ?. (1) Ожидаемое число требований, остающихся при уходе обслуженного тре- бования для системы M/M/1: q = ? 1 ? ? (2) Для системы M/D/1: q = ? (1 ? ?) ? ? 2 2(1 ? ?) Таким образом система типа M/D/1 в среднем содержит на ? 2 /2(1 ? ?) тре- бований меньше, чем система M/M/1. Известно, что q описывает также среднее число требований в случайный момент времени, поэтому можно записать q = n. К этому среднему значению можно применить результат Литтла и получить среднее время, проведенное 7 требованием в системе (очередь плюс обслуживание). Таким образом, n = ? + ? 2 (1 + C 2 b ) 2(1 ? ?) = ?u. Решая относительно u, получаем среднее время пребывания требования в системе u = x + ?x(1 + C 2 b ) 2(1 ? ?) (3) Среднее время пребывания в очереди w = ?x(1 + C 2 b ) 2(1 ? ?) , или w = w 0 1 ? ? , (4) где w 0 def = ?x 2 /2 это среднее остаточное время обслуживания для требо- вания (если такое есть), находящегося в обслуживающем приборе в момент поступления нового требования (последняя формула может быть получена из общей формулы для среднего остаточного времени). w x = ? 1 ? ? , M/M/1; (5) w x = ? 2(1 ? ?) , M/D/1. (6) Заметим, что система с регулярным обслуживанием (M/D/1) характеризует- ся средним временем ожидания вдвое меньшим, чем система с показательным обслуживанием (M/M/1). Это закономерно, так как время пребывания в си- стеме, так же, как и число требований в системе, пропорционально дисперсии времени обслуживания. Третий раздел посвящен принципам построения имитационных моде- лей систем массового обслуживания. Имитационное моделирование есть про- цесс конструирования модели реальной системы и постановки эксперимен- тов на этой модели с целью либо понять поведение системы, либо оценить (в рамках ограничений, накладываемых некоторым критерием или совокупно- 8 стью критериев) различные стратегии, обеспечивающие функционирование данной системы. Таким образом, процесс имитационного моделирования это процесс, включающий и конструирование модели, и аналитическое примене- ние модели для изучения некоторой проблемы. Система € S состоит из объектов: источник требований, очередь требо- ваний системы обслуживания, прибор системы обслуживания, требование. Объектам системы € S ставятся в соответствие объекты имитационной моде- ли. Требования. В общем случае требования представляют собой переме- щаемые по системе объекты, различающиеся классом, приоритетом, номером и другими параметрами. Из всего набора параметров требования реальной системы в модели необходимо отобразить только те, которые способствуют достижению цели моделирования. Необходимы следующие атрибуты требо- вания модели: момент поступления требования t n в очередь системы из ис- точника, момент начала обслуживания требования t nac , момент завершения обслуживания требования t zav Разность моментов t zav и t nac определяет длительность пребывания тре- бования в системе обслуживания, а разность моментов t nac и t n - длительность ожидания требования в очереди системы обслуживания. Для получения ста- тистически значимых оценок характеристик u и b потребуется определенное число обслуженных требований. Их хранение в модели организуется следую- щим образом. Прибор, завершив обслуживание требования, будет направлять его не в источник, а в специально организованную очередь обслуженных требова- ний Q obsl . Тогда признаком окончания эксперимента с имитационной моделью будет достижение заранее определенного числа обслуженных требований в очереди Q obsl Очереди. Очереди являются самостоятельными объектами имитацион- ных моделей систем обслуживания и служат для хранения требований, ожи- дающих обработки. Основным набором характеристик очереди являются: максимальное число требований в очереди, дисциплина установления тре- бований в очередь и выбора их из очереди, приоритет требований, которым разрешается пребывать в очереди. В рассматриваемом случае имитационная 9 модель системы € S содержит очередь Q требований, ожидающих обслужива- ния, и очередь Q obsl обслуженных требований. Модельное время в имитационной модели представлено глобальной пе- ременной вещественного типа, принимающей значения на интервале [0, ?) и обеспечивающей имитацию параллельного развития процессов системы € S Событие - мгновенное изменение состояния модели системы € S . В ими- тационной модели различаются события трех типов: поступление требования в систему массового обслуживания, начало обслуживания требования прибо- ром системы обслуживания и уход требования из системы массового обслу- живания после завершения обслуживания. Процесс функционирования системы € S в имитационной модели пред- ставляется в виде логически связанной последовательности событий на оси модельного времени. Эта последовательность характеризуется интервалами времени между событиями и типом событий. В четвертом разделе построенна модель системы массового обслу- живания типа M/G/1.В данную систему поступает поток заявок, имеющий пуассоновское распределение с параметром ?, длительность обслуживания заявок имеет экспоненциальное распределение с параметром µ. В системе имеется 1 работающий обслуживающий прибор. Если в момент поступления очередной заявки в системе уже находится одна и более заявок, то эта заяв- ка помещается в очередь и ждет начала обслуживания. Дисциплина обслу- живания F CF S. Вместимость системы не ограничена. Емкость источника бесконечна. Требуется определить следующие характеристики работы системы: 1) e ? - коэффициент использования системы; 2) eb среднее число заявок в очереди; 3) e w - среднее время ожидания в очереди; 4) e u - среднее время пребывания заявки в системе. Для нахождения указанных характеристик в программе Matlab была написана программа, моделирующая работу данной системы (описание про- граммы,листинг и результаты программы представлены в приложениях А и Б соответственно). Входными данными программы являются следующие: ?, µ. 10 Выходными данными программы являются следующие: количество об- служенных прибором требований ; суммарное время обслуживания прибо- ром; суммарное время нахождения требований в очереди и вообще в системе; e ? - коэффициент использования системы; eb - среднее число требований в оче- реди; e w - среднее время ожидания в очереди (в часах); e u - среднее время пребывания требования в системе (в часах). Коэффициент использования (загрузки) системы считается по форму- ле: e ? = суммарное время обслуживания время моделирования Среднее число заявок в очереди (в часах) считается по формуле: e b = суммарное время ожидания в очереди время моделирования Среднее время ожидания заявки в очереди (в часах) считается по фор- муле: e w = суммарное время ожидания в очереди количество заявок Среднее время пребывания заявки в системе (в часах): e u = суммарное время пребывания заявок в системе количество заявок Для оценки полученных характеристик в программе были введены фор- мулы, рассчитывающие те же параметры с использованием теоретических результатов раздела 2. Проведен сравнительный анализ полученных практических и теорети- ческих результатов (таблица 1). На основании результатов таблицы 1 видно, что при увеличении числа требований характеристики системы, полученные на основе дискретной модели, отличаются от соответствующих характери- стик, полученных на основе теоретических формул, менее чем на 5 %.Если сравнивать характеристики, полученные на основе дискретной модели, для n = 100 с соответствующими характеристиками, полученными на основе тео- ретических формул, то видно, что они отличаются более чем на 30%. Это 11 говорит о том, что при небольшом числе требований, система не успевает достичь стационарного режима поэтому разница между соответствующими характеристиками существенна. Таблица 1 Характеристики системы M/G/1 Расчет на основании дискретной модели Расчет на основании теоретических формул Характеристики ? = 3 , µ = 4, n = 100000 ? = 3 , µ = 4 коэффициент использова- ния системы e ? M = 0.75086 , e ? N = 0.74848 , e ? D = 0.74996 ? = 0.75000 среднее время ожидания в очереди e w M = 0.77132 , e w N = 0.72544 , e w D = 0.37340 w M = 0.75000 , w N = 0.75000 , w D = 0.37500 среднее время пребывания требования в системе e u M = 1.0216 , e u N = 0.97496 , e u D = 0.62340 u M = 1 , u N = 1 , u D = 0.62500 среднее число требований в очереди e b M = 2.3138 , e b N = 2.1762 , e b D = 1.1201 b M = 2.2500 , b N = 2.2500 , b D = 1.1250 ? = 5 , µ = 8, n = 100000 ? = 5, µ = 8 коэффициент использова- ния системы e ? M = 0.61936 , e ? N = 0.62120 , e ? D = 0.62251 ? = 0.62500 среднее время ожидания в очереди e w M = 0.20201 , e w N = 0.20720 , e w D = 0.10590 w M = 0.20833 , w N = 0.20833 , w D = 0.10417 среднее время пребывания требования в системе e u M = 0.32638 , e u N = 0.33194 , e u D = 0.23090 u M = 0.33333 , u N = 0.33333 , u D = 0.22917 среднее число требований в очереди e b M = 1.0060 , e b N = 1.0319 , e b D = 0.52737 b M = 1.0417 , b N = 1.0417 , b D = 0.52083 12 Если сравнивать полученные характеристики с точки зрения закона распределения времени обслуживания, то можно увидеть, что коэффициент использования системы примерно одинаковые для всех трех распределений (таблица 1), а среднее время проведенное требованием в очереди или в си- стеме для постоянного времени обслуживания требований в два раза меньше чем для экспоненциального и нормального распределений. Это подтверждает теоретические рассуждения, что говорит о правильности построения имита- ционной модели. С точки зрения требований выгоднее, чтобы обслужива- ние было постоянной величиной. Хотя на практике, наверное, этого добиться практически невозможно. В результате, полученная модель полностью имитирует работу рассмот- ренной системы массового обслуживания, и в дальнейшем может быть при- менена для расчета экономических характеристик эффективности функцио- нирования реально существующих систем массового обслуживания. В заключении описаны результаты проделанной работы. ОСНОВНЫЕ РЕЗУЛЬТАТЫ 1. Определены основные понятия, связанные с системами массового об- служивания. Изучены системы обслуживания с ожиданием с пуассоновским входящим потоком заявок и различной длительностью их обслуживания. 2. Изучены принципы и алгоритмы построения имитационной модели систем массового обслуживания. 3. Построена математическая модель изученной системы массового об- служивания. Разработана программа, моделирующая работу такой системы, и позволяющая вычислять основные характеристики системы. Программный код и результаты работы программы приводятся в приложении Б. Так же разработана программа, позволяющая вычислять основные характеристики системы массового обслуживания с ожиданием с пуассоновскими входящим потоком требований и различной длительностью их обслуживания на осно- ве теоретических формул. Текст программы и результат работы программы приводятся в приложении В. Рассмотрен конкретный пример системы мас- сового обслуживания с пуассоновскими входящим и выходящим потоками требований с одним обслуживающими прибором. 13 4. Вычислены основные характеристики системы массового обслужива- ния с ожиданием с пуассоновскими входящим потоком требований и различ- ной длительность их обслуживания на основе дискретной модели и на основе теоретических формул для одних и тех же входных параметров. Проведен сравнительный анализ практических и теоретических характеристик. 14 |