Лр2 Моделирование. 2. Имитационное моделирование систем массового обслуживания
 Скачать 0.65 Mb.
|
|
2. Имитационное моделирование систем массового обслуживания В разных областях техники, в организации производства, в экономике и медицине, в социальной сфере, в военном деле и во многих других сферах человеческой деятельности постоянно возникает необходимость решения вероятностных задач, связанных с работой систем массового обслуживания (СМО). Многообразие приложений теории массового обслуживания определяет постоянно растущий интерес к ней, а сложность возникающих задач не позволяет получить исчерпывающие решения на базе аналитических методов. В таких ситуациях часто прибегают к имитационному моделированию. Для имитации подобных систем предназначен язык моделирования GPSS, а также создаются сложные программные системы (ObjectSim, Pigrim [10]), позволяющие реализовать модели систем массового обслуживания с помощью развитой CASE- оболочки путем выбора и связи различных строительных блоков. Среди работ, описывающих моделирование СМО с помощью электронных таблиц можно привести следующие - [3-7]. Авторы рассматривают моделирование систем с неограниченным, ограниченным по времени и/или длине очереди ожиданием, которые располагают от 1 до 12 обслуживающими устройствами [7]. При этом различают два основных подхода к моделированию СМО: ориентированный на события и ориентированный на процессы. Событийный подход имеет преимущества в отношении гибкости и эффективности вычислений, однако менее подходит для обучения, поскольку скрывает «жизненный цикл» заявок и является менее понятным на интуитивном уровне. Кроме того, для его реализации требуется управляющая событиями подпрограмма, что приводит к необходимости использования внутреннего языка VBA [11]. Рассмотренные ниже модели будут реализованы с использованием процессно-ориентированного подхода. Рассмотрим структуру СМО. Каждая СМО состоит из определенного числа обслуживающих единиц, которые называются каналами обслуживания. На вход СМО поступает поток требований (заявок). Таким образом, различают следующие элементы СМО: 1. входной поток заявок; 2. очередь; 3. узел обслуживания; 4. выходной поток. На рис. 2.1 указаны эти элементы для следующей СМО: бензоколонка занимается заправкой автомобилей. Рис. 2.1 – Пример системы массового обслуживания Входной поток заявок может быть случайным или детерминированным. В первом случае время между поступлением двух заявок является случайной величиной, а во втором – величиной детерминированной (поступление происходит в соответствие с определенным графиком). Интенсивность потока λ – частота появления событий, поступающих в СМО в единицу времени. В СМО может поступать несколько входных потоков, имеющих различные характеристики (интервал поступления, приоритет и т.д.). Очередь – место, где поступившие заявки ждут начала обслуживания. В том случае, если элемент очередь в системе отсутствует, то данная система без ожидания. Это означает, что в том случае, если в момент поступления заявки все каналы обслуживания заняты, то эта заявка покидает систему необслуженной. Очередь может иметь ограниченную или неограниченную длину. Кроме того, время ожидания в очереди может быть ограничено (говорят, что рассматриваются нетерпеливые заявки). Следующая характеристика очереди – дисциплина очереди. Она связана с правилом, в соответствии с которым обслуживаются клиенты. Различают следующие дисциплины: первый пришел – первый ушел, первый пришел – последний ушел, а также существуют дисциплины с приоритетами. Рассмотрим теперь характеристики средств обслуживания. Системы обслуживания характеризуются по числу каналов обслуживания (например, если на рис. 2.1 машины могут быть обслужены несколькими устройствами, то система будет многоканальной), числу фаз обслуживания. Время обслуживание может быть случайной величиной или детерминированным. Также существую системы, в которых обслуженные требования после некоторой задержки опять поступают на вход. Такие системы называются замкнутыми. В качестве показателей эффективности СМО рассматриваются: среднее время, которое клиент проводит в очереди, средняя длина очереди, среднее время, которое клиент проводит в системе обслуживания ( TotalTimeSystem TimeSystem N = , где TotalTimeSystem - общее время пребывания в системе для всех заявок, а N -число заявок), среднее число клиентов в системе обслуживания, вероятность того, что система окажется свободной и т.д. 2.1 Одноканальная система массового обслуживания Рассмотрим простую систему массового обслуживания: число каналов равно единице, время ожидания неограниченно, время между заявками и время обслуживания заявок являются случайными величинами с показательным законом распределения (среднее значение времени обслуживания равно to , среднее время между заявками - tz ) (рис.2.2). Рис. 2.2 – Одноканальная система массового обслуживания Рассмотрим процесс поступления десяти заявок, если tz =0,5 ч., to =1 ч. В[6]использован следующий способ моделирования такой системы (рис.2.3). Величины времени обслуживания и между заявками рассчитываются согласно способу моделирования случайной величины с показательным законом распределения D7=-$F$3*LN(СЛЧИС()) E7=-$F$2*LN(СЛЧИС()). В последнем столбце рассчитывается величина Wn Xn Yn + − F7=C7+D7-E7. Если ее значение является отрицательным, то это означает, что следующая заявка поступит после того, как будет обслужена текущая и потому время ее ожидания будет равно нулю, а в противном случае, время ожидания составит Wn Xn Yn + − С8=ЕСЛИ(F7>0;F7;0). Изменим исходные данные ( tz =1 ч., to =0,5 ч.). Из рис. 2.4 можно увидеть, что в этом случае уменьшится время ожидания обслуживания. Рис.2.3 – Результаты моделирования одноканальной СМО при tz =0,5 ч., to =1 ч. Рис. 2.4 – Результаты моделирования одноканальной СМО при tz =1 ч., to =0,5 ч. Теперь выполним моделирование, учитывая начальное время tn . Пусть tz =8 мин., to =7 мин.; tn =9 ч. Рассмотрим процесс поступления семи заявок (рис.2.5). Определение времени между заявками и времени обслуживания (мин.) остается без изменения. Для того чтобы перевести эти значения в используемый формат времени необходимо осуществить следующие операции F8=E8/1440 D8=D7+C8/1440. Т.е. время поступления очередной заявки равно сумме времени прибытия предыдущей и случайной величины, распределенной по показательному закону. Время начала обслуживания первой поступившей заявки равно времени ее поступлению G8=D8. Начиная со второй заявки, эта величина будет определяться как максимальное значение из момента окончания обслуживания предыдущей заявки и времени поступления текущей G9=ЕСЛИ(D9>=H8;D9;H8). Время окончания обслуживания рассчитывается по формуле H8=G8+F8. Период ожидания равен разности времени начала обслуживания и времени поступления I8=G8-D8. Также встречаются системы, в которых новая заявка может поступить только после того, как была обслужена предыдущая. В качестве примера, можно назвать систему, которая периодически может выходить из строя и требовать ремонта (ее отказы в данном случае рассматриваются как заявки): время между ее отказами и время обслуживания распределено по показательному закону. Очевидно, что не может произойти выход из строя системы прежде, чем будет выполнен ремонт предыдущего отказа. Такие заявки будем называть не перекрывающимися. Для того чтобы выполнить моделирование данной СМО необходимо изменить только расчет времени прибытия заявки, которое будет равно сумме момента окончания обслуживания предыдущей заявки и случайной величины, распределенной по показательному закону D9=H8+C9/1440. Результаты моделирования представлены на рис.2.6 ( tz =5 мин., to =6 мин.). Можно заметить, что в Диаграмме заявок теперь отсутствуют периоды ожидания обслуживания. Рис. 2.5 – Моделирование одноканальной СМО с учетом начального времени Рис. 2.6 – Моделирование одноканальной СМО с не перекрывающимися заявками Задание 1. Выполните имитацию работы банка, осуществляющего прием вкладов. Размер депозита является случайной величиной с нормальным законом распределения (среднее значение - MD ; среднее квадратическое отклонение - SD ). Время между приходом двух вкладчиков – случайная величина с показательным законом распределения (среднее значение - tz ), а время обслуживания равномерно распределено на интервале [ a ; b ]. Пусть исходные значения равны величинам: MD =30000 руб.; SD =10000 руб.; tz =1 час; a =20 мин.; b =30 мин.; tn =9 ч., число заявок равно 5. Определите время прихода последнего клиента, среднее время пребывания клиента в системе. Какой общий размер вкладов будет осуществлен а) после прихода пяти клиентов; б) к моменту времени 12:00 ч.? Рис.2.7 – Система массового обслуживания «Банк» 2. Проведите 10 экспериментов и рассчитайте величины: • среднее время ожидания; • среднее число обслуженных заявок за период с 9:00 до 15:00 ч. 3. Предположите, что tn =0 и выполните имитацию описанным на рис. 2.3 способом. 4. Пусть банковская автоматизированная система может выходить из строя, что приводит к необходимости вызова специалистов, устраняющих неполадку. Выполните имитацию периодов нормальной работы системы и ее ремонта, если данные величины являются случайными с показательным законом распределения, а tz =30 дней, to =3 ч. Рассмотрите процесс поступления 5 заявок (отказов). 2.2 Двухканальная система массового обслуживания В том случае, если обслуживание заявок может происходить в нескольких узлах, то говорят, что данная система является многоканальной. Рассмотрим двухканальную СМО (рис.2.8). Предположим, что вновь поступившая заявка поступает в тот канал, который раньше других освободился (а при одновременном освобождении заявка поступит в первый узел), тогда процесс моделирования можно представить следующим образом (рис. 2.9) (исходные данные: tz =8 мин., to =7 мин.; 0 t =9 ч.). Рис. 2.8 – Двухканальная система массового обслуживания Рассмотрим основные отличия от предыдущей модели. Для каждого канала выполняется расчет времени начала и окончания обслуживания. Решение о том, в каком канале будет происходить обслуживание, принимается на основе данных о времени освобождения каждого из них. Время начала обслуживания заявки равно максимальному значению из следующих величин: время освобождения найденного канала и время прибытия заявки Е8=ЕСЛИ(МАКС(F$7:F7)<=МАКС(H$7:H7);МАКС(F$7:F7;C8);"") F8=ЕСЛИ(ЕТЕКСТ(E8);"";E8+D8) G8=ЕСЛИ(МАКС(F$7:F7)>МАКС(H$7:H7);МАКС(H$7:H7;C8);"") H8=ЕСЛИ(ЕТЕКСТ(G8);"";G8+D8). Время ожидания обслуживания определяется по формуле I8=ЕСЛИ(ЕТЕКСТ(E8);G8-C8;E8-C8). Рис. 2.9 - Моделирование двухканальной системы массового обслуживания Задание 1. Магазин, располагающий двумя кассами, занимается продажей продовольственных товаров (рис. 2.10). Время между приходом двух покупателей – случайная величина с показательным законом распределения (среднее значение - tz ), а время обслуживания равномерно распределено на интервале [ a ; b ]. Сумма покупки является случайной величиной с нормальным законом распределения (среднее значение - MD ; среднее квадратическое отклонение - SD ). Пусть исходные значения равны величинам: MD =400 руб.; SD =100 руб.; tz =10 мин.; a =3 мин.; b =7 мин.; tn =9 ч. Выполните моделирование поступления семи заявок (покупателей). Определите время прихода седьмого клиента. Какой размер выручки получит магазин а) после того, как было обслужено семь покупателей; б) к моменту времени 10:00 ч.? 2. Предположите, что рассматриваемый поток клиентов – это потенциальные покупатели, которые с вероятностью P могут совершить покупку ( P =0,6). 3. Пусть время обслуживания – дискретная случайная величина со следующим законом распределения Значение, мин. 1 2 3 4 Вероятность 0,2 0,2 0,4 0,2 Выполните имитацию, учитывая данное условие. 4. Проведите 10 экспериментов и рассчитайте величины: • среднее время ожидания; • средний размер выручки. Рис.2.10 – Система массового обслуживания «Магазин» 2.3 Система массового обслуживания с ограниченным по времени ожиданием Ожидание наступления обслуживания может быть ограничено двумя условиями: длиной очереди и временем. Во втором случае заявка покидает систему необслуженной, если время ее ожидание превысило некоторое значение TOMax , в противном случае – поступает в канал обслуживания (рис. 2.11). Если время ожидания заявок равно нулю, то система называется СМО без ожидания (рис. 2.12). В качестве примера можно привести поступление телефонных звонков в справочную службу: если оператор занят разговором с другим клиентом, то поступившие в этом период звонки получают отказ в обслуживании. Рис. 2.11– Система массового обслуживания с ограниченным по времени ожиданием Рис. 2.12 – Система массового обслуживания без ожидания Считая, что время между заявками и обслуживания является случайной величиной с показательным законом распределения, выполним имитацию данной системы со следующими исходными данными: tz =8 мин., to =7 мин.; 0 t =9 ч.; TOMax = 1 мин. Результаты представлены на рис. 2.13. В столбце «Поступление на обслуживание» принимается решение о том, будет ли начато обслуживание заявки. Для этого рассчитывается промежуток времени между поступлением заявки и освобождением канала и сравнивается с максимальным временем ожидания заявки Е9=ЕСЛИ((МАКС(G$8:G8)-C9)>$D$4;"Нет";"Да"). В случае поступления заявки на обслуживание определяется время его начала и окончания F9=ЕСЛИ(E9= «Да»;МАКС(C9;G$8:G8); «») G9=ЕСЛИ(ЕТЕКСТ(F9);»»;F9+D9). В последнем столбце «Ожидание» рассчитывается время ожидания (для всех заявок, независимо от, того были ли они обслужены) H9=ЕСЛИ(ЕТЕКСТ(G9);МАКС(G$8:G8;C9)-C9;F9-C9). Так, из рис.2.13 видно, что в данной реализации период ожидания шестой заявки превысил максимально допустимое значение, и поэтому обслуживания не произошло. Рис. 2.13 – Моделирование системы массового обслуживания с ограниченным по времени ожиданием Задание 1. Менеджер фирмы принимает заказы от клиентов на выполнение различных работ (рис.2.14). Заказы поступают посредством телефонной связи. Время между двумя звонками является случайной величиной с показательным законом распределения (среднее значение - tz ), время обслуживания (принятия заказа) – случайная величина с нормальным законом распределения (среднее значение - to , среднее квадратическое отклонение - sto ). В том случае, если звонок поступил в то время, когда менеджер занят приемом другого заказа, то он получает отказ в обслуживании. Стоимость заказа клиента равномерно распределена на интервале [ a ; b ]. Выполните моделирование данной системы при следующих исходных данных: tz =15 мин.; to =15 мин.; sto =2 мин.; a =5000 руб.; b =15000 руб.; tn =9 ч. Рассмотрите поступление шести звонков и определите следующие величины: число отказов в обслуживании; общая сумма заказов; время поступления последнего звонка. Рис.2.14 – Система обслуживания «Прием заказов» 2. Проведите 10 экспериментов и рассчитайте величины: • среднее число отказов в обслуживании; • среднюю сумму заказов; • среднее время завершения моделирования (время окончания обслуживания последней заявки). 3. Выполните моделирование, считая, что вероятность совершения заказа клиентом равна P ( P =0,7). 4. Предположите, что фирма наняла еще одного менеджера и вновь поступивший звонок направляется к свободному в данный момент работнику. 5. Пусть новое оборудование фирмы позволяет поступившим звонкам ожидать освобождения менеджера в течение времени TOMax . Выполните моделирование при TOMax =2 мин. (число каналов обслуживания равно единице), рассчитайте среднее число отказов (за 10 реализаций) и сравните данное значение с полученным во втором задании. 6. Рассмотрите ситуацию, когда максимальное время ожидания каждой заявки определяется также поведением клиентов и его значение – случайная величина с дискретным законом распределения: Значение 0 1 2 Вероятность 0,25 0,5 0,25 2.4 Система массового обслуживания с очередью Рассмотрим теперь другой тип систем с ожиданием – СМО с очередью. В этом случае заявка покидает систему необслуженной, если на момент ее поступления длина очереди превышает число LOMax (рис.2.15). Рис.2.15 – Система массового обслуживания с ограниченным по длине очереди ожиданием Выполним моделирование, используя следующие исходные данные: tz =8 мин., to =7 мин.; 0 t =9 ч.; LOMax =1 (время между заявками и обслуживания является случайными величинами с показательным законом распределения) (рис.2.16). Расчет значений столбцов «Время прибытия заявки», «Время обслуживания», «Ожидание» осуществляется тем же способом, что и в моделях рассмотренных выше. Значения столбца «Длина очереди» характеризуют число заявок, ожидающих обслуживания к моменту поступления текущей. Оно рассчитывается путем подсчета тех значений, в столбце «Начало обслуживания», которые превышают время поступления текущей заявки D9=СЧЁТЕСЛИ($G$8:$G8;">"&C9). В зависимости от полученного значения, определяется, поступит ли заявка на обслуживание Е9=ЕСЛИ(D9>$E$4;"Нет";"Да"). Расчет времени начала и окончания обслуживания осуществляется следующим образом G9=ЕСЛИ(E9="Да";МАКС(C9;H$2:H8);"") H9=ЕСЛИ(ЕТЕКСТ(G9);"";G9+F9). Рис. 2.16 – Моделирование системы массового обслуживания с очередью Задачи 1. Парикмахерская занимается обслуживанием клиентов (рис. 2.17). Время между приходом двух клиентов является случайной величиной с показательным законом распределения (среднее значение - tz ), а время обслуживания распределено по нормальному закону. В том случае, если в момент прихода нового клиента мастер занят, то клиент встает в очередь. При этом имеются места ожидания, число которых равно LOMax . Если же все места заняты, то клиент уходит и не ждет обслуживания. Выручка от одного клиента, а также его время обслуживания зависит от типа прически. В таблице 2.1 приведены характеристики этих данных. Таблица 2.1 – Характеристики причесок Тип прически 1 2 3 4 Стоимость, 100 120 140 150 руб. Среднее время обслуживания, мин. 15 20 20 25 СКО времени обслуживания, мин. 3 3 5 6 Кроме того, имеются следующие статистические данные о том, сколько людей выбрало тот или иной тип прически (всего 100 человек) Тип прически 1 2 3 4 Число людей 20 30 35 15 Выполните моделирование поступления 9 заявок, используя следующие исходные данные: tz =20 мин.; LOMax =2; tn =9 ч. Рис. 2.17 - Система массового обслуживания «Парикмахерская» 2. Рассчитайте следующие значения: максимальная длина очереди; общее время пребывания заявок в очереди; сумма выручки. 3. Проведите 10 экспериментов и рассчитайте величины: • среднее число отказов в обслуживании; • среднюю выручку; • среднее время завершения моделирования (время окончания обслуживания последней заявки). 2.5 Система с групповым обслуживанием заявок При групповом обслуживании поступающие заявки направляются в очередь, где они ожидают того момента, когда размер группы станет равным NGrup . После этого все заявки одновременно обслуживаются и покидают систему (рис.2.18). Рис.2.18 – СМО с групповым обслуживанием заявок Пусть время между заявками является случайной величиной с показательным законом распределения (среднее значение равно tz ), а обслуживания – с равномерным (нижняя граница интервала - a , верхняя - b ). На рис.2.19 представлены результаты моделирования при tz =5 мин., a =20 мин.; b =25 мин.; NGrup =3. Столбец «Размер группы» содержит число заявок в очереди к моменту прибытия текущей, а значения его ячеек рассчитываются следующим образом D10=0 D11 =ЕСЛИ(D10=$E$5-1;0;D10+1). Период обслуживания рассчитывается исходя из значения границ интервала распределения E10=ЕСЛИ(D10=$E$5-1;($E$3+СЛЧИС()*($E$4-$E$3))/1440;""). Если после поступления текущей заявки происходит обслуживание группы, то время ожидания рассчитывается как разность времени начала обслуживания и времени прибытия. В противном случае определяется время начала обслуживания группы (после поступления заявок в будущем) и от этого значения отнимается время поступления текущей заявки H10=ЕСЛИ(ЕТЕКСТ(G10);МАКС(МИН(F10:F$15);C10)-C10;F10-C10). Рис.2.19 – Моделирование системы с групповым обслуживанием заявок Задачи 1. Вы парке развлечений расположен аттракцион, стоимость билета на который составляет B руб. (рис.2.20). Время между приходом двух желающих попасть на него является случайной величиной с показательным законом распределения (среднее значение равно tz ). Обслуживание начинается после того, как пришло NGrup человек, а его продолжительность равна To . Расходы, связанные с использованием аттракциона в течение времени обслуживания, равны R руб. Выполните моделирование данной системы массового обслуживания при поступлении 10 заявок и исходных данных: B =50 руб.; tz =5 мин.; To =10 мин.; NGrup =3; R =70 руб.; tn =9 ч.Рассчитайте общую выручку и прибыль, время ожидания, время прихода последнего клиента. 2. Используя различные значения NGrup ( NGrup =1; 2; 3; 4), определите, как изменится прибыль и время ожидания. 3. Проведите 10 экспериментов и найдите: • среднее значение выручки; • среднее значение общего времени ожидания; • вероятность того, что общее время ожидания будет больше или равно 10 мин. Рис.2.20 – Система массового обслуживания «Аттракцион» 2.6 Система массового обслуживания с групповым поступлением заявок В данной системе прибытие заявок осуществляется группами, а обслуживается каждая заявка отдельно (рис.2.21). Рис. 2.21 – Система массового обслуживания с групповым поступлением заявок Моделирование данной системы аналогично моделированию простой одноканальной системы массового обслуживания (моделирование поступления группы аналогично имитации прибытия заявок) за исключением расчета времени обслуживания. Оно будет определяться исходя из количества заявок в группе, например, равно сумме случайных величин времени обслуживания одной заявки (число слагаемых равно размеру группы). Так, например, если в системе на рис.2.5 заявки поступают группами, размер которых равен двум, то время обслуживания группы будет равно E8=-($Е$3*LN(СЛЧИС())+$Е$3*LN(СЛЧИС())). Задачи 1. Такси занимается перевозкой людей (рис.2.22). Заявки от клиентов поступают через случайные промежутки времени, распределенные по показательному закону (среднее значение равно tz ). Время доставки в одном направлении является случайной величиной, равномерно распределенной на интервале [ a ; b ]. Число клиентов с различными направлениями, осуществивших один вызов, может быть 1, 2 или 3. В этом случае доставка ведется по различным направлениям. Стоимость доставки зависит от числа направлений, по которым нужно доставить пассажиров. В таблице 2.2 приведены значения вероятности появления группы определенного размера и стоимость доставки. Выполните моделирование работы такси (пусть поступило 8 заявок), используя следующие исходные данные: tz =30 мин.; a =15 мин.; b =30 мин.; tn =9 ч. Рассчитайте полученную таксистом выручку. Таблица 2.2 – Характеристики размера группы Число человек в группе Вероятность Стоимость доставки, руб. 1 0,5 100 2 0,4 150 3 0,1 200 2. Рассмотрите случай, когда оплата проезда производится пассажирами следующим образом: стоимость вызова равна 40 руб.; цена 1 мин. проезда составляет 40 руб. 3. Проведите 10 экспериментов и рассчитайте: • среднюю выручку; • среднее время ожидания; • вероятность того, что выручка будет менее 850 руб. Рис. 2.22 – Система массового обслуживания «Такси» |