КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Расчет систем массового обслуживания с отказами методом Монте-КарлоРассмотрим одну из самых простых систем массового обслуживания. Система эта состоит из n-линий (или каналов, или пунктов обслуживания), каждый из которых может обслуживать потребителей. В систему поступают заявки, причем моменты их поступления случайные. Каждая заявка поступает на линию № 1. Если в момент поступления k-й заявки (назовем его Тк) эта линия свободна, то она приступает к обслуживанию заявки, что продолжается t3 мин. (t3 – время занятости линии). Если в момент Тк линия № 1 занята, то заявка мгновенно передается на линию № 2. и т.д… Если все n-линии в момент Тк заняты, то система выдает отказ. Требуется определить, сколько (в среднем) заявок обслужит система за время Т и сколько отказов она даст. Ясно, что задачи такого типа встречаются при исследовании организации работы любых предприятий, а не только предприятий бытового обслуживания. Здесь метод Монте-Карло является единственным методом расчета. Схема расчета. Каждой линии поставим в соответствие ячейку внутреннего накопителя ЭВМ, в которую будем записывать момент, когда эта линия освобождается. Обозначим момент освобождения i-й линии через ti. За начальный момент расчета выберем момент поступления первой заявки T1=0. Можно считать, что в этот момент все ti равны T1: все линии свободны. Время окончания расчета Ткон =Т1+Т. Первая заявка поступает на линию №1. Значит, в течение t3 линия эта будет занята. Поэтому заменяем t1 на новое значение (t1)нов = Т1+t3 , добавить единицу к счетчику выполненных заявок и перейти к рассмотрению второй заявки. Предположим, что к заявок уже рассмотрены. Тогда разыграем момент поступления (к+1)-й заявки. Для этого выбираем очередное значение γ и по формуле τ = 1/а lnγ вычисляем очередное значение τ = τк. А затем вычисляем момент поступления Тк+1 = Тк+τк. Свободна ли в этот момент первая линия? Для установления этого надо проверить условие t1 <=Tk+1. Если это условие выполнено, то значит, к моменту Тк+1 линия уже освободилась и может обслуживать эту заявку. Мы должны заменить t1 на Tk+1+t3, добавить единицу к счетчику выполненных заявок и перейти к следующей заявке. Если условие t1 <=Tk+1не выполнено, то значит, что первая линия в момент Tk+1 занята. Тогда проверяем, свободна ли вторая линия t2 <=Tk+1. Если условие t2 <=Tk+1 выполнено, то заменяем t2 на Tk+1+t3, добавляем единицу к счетчику выполненных заявок и переходим к следующей заявке. Если предыдущее условие не выполнено, то переходим к проверке условия t3 <=Tk+1. Может оказаться, что при всех i от 1 до n ti > Tk+1, т.е. все линии в момент Тк+1 заняты. Тогда надо добавить единицу в счетчик отказов и потом перейти к рассмотрению следующей заявки. Каждый раз, вычислив Тк+1, надо проверять еще условие окончания опыта Тk+1 > Ткон .Когда это условие окажется выполненным, опыт заканчивается. В счетчике выполненных заявок и в счетчике отказов будут стоять числа μвып и μотк. Такой опыт повторяется N раз (с использованием различных γ). И результаты всех опытов усредняются: ; , где μвып (j) и μотк (j) – значения μвып и μотк, полученные в j-ом опыте. Представим блок-схему программы, реализующий расчет СМО методом Монте-Карло на рис. 7. [17]
Рисунок 7 - Блок-схема программы, осуществляющей расчет СМО методом Монте-Карло Пример. В трехканальную систему массового обслуживания с отказами поступает пуассоновский поток заявок. Время между поступлениями двух последовательных заявок распределено по показательному закону f(τ) = 5e-5τ . Длительность обслуживания каждой заявки равна 0,5мин. Найти методом Монте-Карло математическое ожидание а числа обслуженных заявок за время Т=4мин. Решение: Пусть Т1=0 – момент поступления первой заявки. Заявка поступит в первый канал и будет им обслужена. Момент окончания обслуживания первой заявки Т1+0,5=0+0,5=0,5. В счетчик обслуженных заявок записываем единицу. Моменты поступления последующих заявок найдем по формуле: Тi=Ti-1+τi. где τi - длительность времени между двумя последовательными заявками с номерами i-1 и i. Возможные значения τi разыгрываем по формуле Учитывая, что, по условию, λ=5, получим τi=0,2 (ln ri). Случайные числа ri берем из таблицы приложения 1, начиная с первой строки сверху. Для нахождения времени между поступлениями первой и второй заявок возьмем случайное число r1=0,10. Тогда вычислим: τ2=0,2*(ln0,10)=0,2*2,30=0,460. Первая заявка поступила в момент Т1 = 0. Следовательно, вторая заявка поступит в момент Т2 = Т1+0,460=0,460. В этот момент первый канал ещё занят обслуживанием первой заявки, поэтому вторая заявка поступит во второй канал и будет им обслужена. Момент окончания обслуживания второй заявки Т2+0,5=0,460+0,5=0,960. В счетчик обслуженных заявок добавляем единицу. По очередному случайному числу r2=0,09 разыграем время τ3 между поступлениями второй и третьей заявок: τ3 = 0,2*(-ln 0,09) = 0,2*2,41=0,482. Вторая заявка поступила в момент Т2=0,460. Поэтому третья заявка поступит в момент Т3=Т2+0,482=0,460+0,482=0,942. В этот момент первый канал уже свободен, и третья заявка поступит в первый канал. Момент окончания обслуживания третьей заявки Т3+0,5=1,442. В счетчик обслуженных заявок добавляем единицу. Дальнейшие расчеты производят и результаты записывают в таблице, причем если в момент поступления заявки все каналы заняты (момент поступления заявки меньше каждого из моментов окончания обслуживания), то в счетчик отказов добавляют единицу. Заметим, что обслуживание 20-й заявки закончится в момент 4,148>4, поэтому эта заявка получает отказ. Таблица 1
Испытания прекращают (в таблице записывают «стоп»), если момент поступления заявки Т>4. Из таблицы находим, что за 4 мин. всего поступило 20 заявок; обслужено х1=12 заявок. Выполнив аналогично ещё пять испытаний, получим: х2=15, х3=14, х4=12, х5=13, х6=15. В качестве оценки искомого математического ожидания а числа обслуженных заявок примем выборочную среднюю =(2*12+13+14+2*15)/6=13,5 Пример. В одноканальную систему массового обслуживания с отказами поступает пуассоновский поток заявок. Время между моментами поступления двух последовательных заявок распределено по закону f(τ)=0,8е-0,8τ; время обслуживания заявок случайное и распределено по закону f1(t)=1,5е-1,5t. Найти методом Монте-Карло за время Т=30мин: среднее число обслуженных заявок; среднее время обслуживания одной заявки; вероятность обслуживания; вероятность отказа. Произвести 6 испытаний. Решение. Время между моментами поступления двух последовательных заявок распределено по закону f(τ)=0,8е-0,8τ, поэтому значения τi разыграем по формуле: τi = -(1/0,8)ln ri =1,25(-ln ri). Случайные числа ri берем из таблицы равномерно распределенных случайных чисел, начиная с первой строки снизу. Время обслуживания заявок распределено по закону f1(t)=1,5е-1,5t, поэтому значения ti разыгрываем по формуле: ti = -(1/1,5)ln Ri = 0,67 (-ln Ri). Случайные числа Ri, берем из той же таблицы, начиная с первой строки сверху. Пусть Т1=0 – момент поступления первой заявки. По случайному числу R1=0,10 разыгрываем длительность времени обслуживания первой заявки (в мин): t1 = 0,67 (-ln 0,10) = 0,67*2,30 = 1,54. Момент окончания обслуживания первой заявки Т1=1,54=0+1,54=1,54. В счетчик обслуженных заявок записываем единицу. По случайному числу r2=0,69 разыграем время (в мин) между моментами поступления первой и второй заявок: τi = 1,25 (-ln 0,69) = 1,25*0,37=0,46. Первая заявка поступила в момент Т1=0. Следовательно вторая заявка поступит в момент Т2=Т1+0,46=0+0,46=0,46. В этот момент канал занят обслуживанием первой заявки (0,46<1,54), поэтому вторая заявка получит отказ. В счетчик отказов записываем единицу. По очередному случайному числу r3=0,07 разыгрываем время между моментами поступления второй и третьей заявок: τ3 = 1,25 (-ln 0,07) = 1,25*2,66 = 3,32. Вторая заявка поступила в момент Т2=0,46. Следовательно, третья поступит в момент Т3=Т2+3,32=0,46+3,32=3,78. В этот момент канал уже свободен (3,78>1,54), поэтому он обслужит третью заявку. В счетчик обслуженных заявок добавляем единицу. Дальнейший расчет ясен из таблиц 2 и 3. Испытание заканчивается, когда момент поступления заявки Тi>30. Например, в первом испытании, как видно из табл. 2, 23-я заявка поступила в момент Т23=31,35>30, поэтому эту заявку исключаем («Стоп») и первое испытание заканчиваем [2]. Таблица 2
Таблица 3
Таблица 4
Используя таблицу 4, найдем искомые величины: а) среднее число обслуженных за 30мин заявок Nобсл. =93/6=15,5; б) среднее время обслуживания одной заявки tобсл. =4,49/6=0,748; в) вероятность обслуживания Робсл.=3,974/6=0,662; г) вероятность отказа Ротк. =1-Робсл.=1-0,662=0,338. Таким образом, примерно 66% заявок будут обслужены, а 34% получат отказ.
|