программно реализованная марковская модель массового обслуживания с переменными параметрами поступления и обслуживания для анализа сложных систем

В.Н. Тарасов, Н.Ф. Бахарева

ПРОГРАММНО РЕАЛИЗОВАННАЯ МАРКОВСКАЯ МОДЕЛЬ МАССОВОГО ОБСЛУЖИВАНИЯ С ПЕРЕМЕННЫМИ ПАРАМЕТРАМИ ПОСТУПЛЕНИЯ И ОБСЛУЖИВАНИЯ ДЛЯ АНАЛИЗА СЛОЖНЫХ СИСТЕМ

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

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

Для анализа вышеуказанных систем рассмотрим такую же область распределения двумерного диффузионного процесса (х1,х2), как и для СМО 01/0/1/ш с потерями /4,5/ (рисунок 1а). При этом траектория процесса (х1,х2), достигнув границы Г2 (поглощающий экран), остается там случайное время, равное времени дообслуживания текущей заявки, а потом распределяется в области, определенной условиями N>0 и Кшах=ш, пока не достигнет поглощающей границы Г1 (ш-емкость накопителя). Область между границами Г1и Г2 разобьем на квадраты Ок (рисунок 1 б), где Ок означает, что в СМО находится К заявок (к=1,...,ш; 1=1,2,...).

Область Б'и характеризуется своими интенсивно-

к __1 __1

стями и поступления заявок Цк = %т и Хк = Т—,

а также дисперсиями этих времен Бтк и ОЯк , зависящими от состояния системы.

Следовательно, диффузионные процессы х1 и х2 в области Огк характеризуются переменными

коэффициентами сноса а(к) = Як, а2' = Цк и коэффициентами диффузии

Ь(к}= О1к -Я—3, ь2к}= Отк .

Распределения ординат процессов х^) и х2(1;) в моменты достижения ими уровней х1=к+1 и

х2 = к — ф'к (у 2) и (у1), выраженные через решение уравнения Колмогорова ю(1,х1,х2) в области Б позволяют определить все основные характеристики узла типа 01/0/1/ш с переменными параметрами. При этом распределения (р'к (у2) и (у1) определяются рекуррентными формулами аналогично СМО с бесконечной очередью. Для этого подробно рассмотрим область О'к (рисунок 1б), где

Лк

обозначены распределения р'к (у2), р'к—1

(2 ),

У (у1), Ум (у1 ), а также функции вероятностей переходов ординат процессов х1 и х2 - Qр Qр 0>¥, Qy. Функция Qр и Qy определяются аналогично функциям Qр и Qy из /4, 5/:

^р(У2/ У1 )=—У=еХР р ЬЬ

а- у1+^ (1—У2) Ь1 Ь2

Ь1

К1 К1ШЛ;

= (1) ( — У2 )2 Я1 (у1 )2 , (1 + У2 )2

_ ; и2 = +

2Ь

2Ь2 ' 2Ь1 + 2Ь2

у.

а а0

2Ь1 2Ь

; У2 е [0,1], у1 е [0,1];

у1 )=-

^л/ьТЬ

гехр

—+ — Ь1 Ь2

К (2л/ЬТ Ь^Цг К (У

Ь3 = ( — У1)2 + ; Ь4 = ( + У1)2

2Ь

2Ь

2Ь

+

2Ь2>

У1 е[0,1].

Теперь можно записать рекуррентные формулы для распределений

(к (У2) и (У1): (к (У2 ) = ¡р'к—1 (2 ^р (2 /У2 ))2 +

+

¡угк— 1

1

0

166 ВЕСТНИК ОГУ 3 2002

Уг

(Л ) = (к-1 (у2 Ъу ( /У2 Ы

+

+

|Уг-1 ( Ъ (У21 У Уу1

Ро = 1/Е г • Рг

г=1

т 2

"1у Э

у(у1 ) = Еу1 & ) (см. рисунок 1а).

г =1

Средний интервал времени между заявками в выходном потоке

Ты = тт + РоТ1,

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

= Ро (тт + 4

1

+ Тх)+ Р1 •ТЦ2 + ••• + рт-1 'Тцт-

Бвых = р0

+ В1 + ( + Т У

т-1

+

+ Е Рг

г=1

(к=1,...,ш; 1=1,2,...).

Далее запишем формулы для определения основных характеристик системы через параметры двумерного диффузионного приближения, аналогично СМО с бесконечной очередью и СМО 01/0/ 1/ш с потерями /4, 5/. Вероятность Ро того, что обслуженная заявка оставляет узел свободным

Формулы (6) и (7) для параметров выходного потока отдельного узла могут быть получены при аналогичных рассуждениях, что и формулы в /5/.

Среднее количество заявок, прошедших через систему за время периода занятости

Nт = 1/Р0 .

Среднее время ожидания заявки в системе на периоде занятости

" 1

j(p1k (х)хёх

Ж

где Рг =|У'(У1 .

0

Среднее время простоя

Т = I =Ч- т¥,

а дисперсия этого времени

В = т¥+х1 • Бу,

где и среднее и дисперсия интервала времени между заявками во входном потоке; 1 1 ту = ¡УУЫ Ул ; Бу=\у2у(У1

¥ т

ЕЕ

г=1 к=1

0

Хтк / Nт

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

... 1 N '

я

=ЕЕ

г=1 к=1

| (к (х)хёх

0

Рк / ^

где рк - средняя загрузка системы при условии, что в ней находится К -заявок (к=1,.,ш). Средняя длина периода занятости

У =хт1 +(1 - Р1 )хт2 +(1

т2

Р1

Р2 У

тз

+ ••• .

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

т -1

определяются аналогично Ро и Е Р1 = 1. Диспер-

I=о

сия интервала времени между заявками в выходном потоке

Средний коэффициент загрузки узла

рср = У /

а среднее количество заявок в узле

N = N я +Рср.

Приведенная выше методика расчета характеристик СМО типа 01/0/1/ш с конечной очередью и параметрами, зависящими от состояния системы, реализована в виде программного модуля в пакете прикладных программ вероятностного моделирования сложных систем.

Области применения

Вычислительные системы

К анализу таких СМО приводят многие модели мультипрограммирования, в частности циклическая модель для мультипрограммирования (рисунок 2). Это модель с центральным обслуживающим прибором, которая позволяет включить периферийное устройство. Центральный обслуживающий прибор представляет собой центральный процессор (ЦП), а периферийное устройство (ПУ) может быть моделью любого устройства, обеспечивающего хранение данных (НМГД, НМЖД). В

0

0

0

0

Естественные науки

такой модели задания циркулируют между двумя устройствами, требуя обращения к ЦП, а затем к ПУ и обратно. В модели допускается ровно К заданий.

Автоматизированное поточное

производство изделий

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

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

Абстрактную операцию сборки можно представить как переработку информации о состоянии заготовок, участвующих в сборке. Пусть в сборке участвует узел (ведущий полуфабрикат) и т деталей (ведомых полуфабрикатов). Координаты их состояний до начала операции обозначим №ку,0а ,•••, акт. В результате операции сборки

получают сборный узел с новыми значениями ко*

ординат 0ку. Тогда математическое описание операции сборки задается соотношением

°ку =аку (аку, ак1, • • •, акт, А— р \ где Рг - п^Ра-

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

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

Комбинация операций обработки со сборкой изделия и с операциями управления и дает абст-

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

Во многих случаях в системе поточного производства следует учитывать тот факт, что в системе массового обслуживания время обслуживания зависит от характеристик входного потока (от свойств заготовок, отклонения их размеров от номинальных, температуры и других). Кроме этого необходимо учитывать ограниченность накопителей заготовок, деталей инструментов и местных складских ячеек. Все эти и другие особенности поточного производства в полной мере не могут быть проанализированы существующими методами аналитического вероятностного моделирования.

Анализ моделей равновесия

в рыночной экономике

Модели равновесия означают, что в идеале достигается совокупная пропорциональность: а) производства и потребления; б) ресурсов и их использования; в) предложения и спроса; г) факторов производства и его результатов; д) материально-вещественных и финансовых потоков. Существенную роль в разработку этих моделей внесли Л. Вальрас, В. Леонтьев, В. Парето и другие. Вкратце эти модели сводятся к схемам «затраты - выпуск», «предложение - спрос».

В таблице 1 приведены уравнения пяти групп моделей равновесия.

Здесь приняты следующие условные обозначения:

Р] - цена¡-готовара

- вектор цен выпускаемых товаров;

Р1 - цена 1-го фактора производства, 1=1.. .ш;

Р = ((1, РРт) - вектор цен факторов производства;

Б - число фирм, £=1,.,Р;

Н - число потребителей;

ап - количество первичного фактора, купленного на рынке и затрачиваемого на производство продукции в течение года фирмой

/ - а =(а(, а2 •••атп );

/

Я/ - объем выпуска ¡-го продукта;

яп = (я{,Я2 •••яЦ,);

Фп(яп,я2 •••яП,а{,а{••а{п )=Фп(яп,яП)= 0

- производственная функция каждой фирмы1;

168 ВЕСТНИК ОГУ 3*2002

Таблица 1.

Уравнения моделей поведения фирм, потребителей, общего равновесия и цели субъектов рынка

п т модель: р =ХPjqfj — XРга1*, .7=1 г=1 в векторной форме: к{ = pqf — paf; целевая производ- тах к f += pqf — ра^ ственная при Ф f (qf, а f) = 0, функция или в словесном выражении: прибыль каждой фирмы есть разность между валовым доходом от продажи производственной продукции за вычетом стоимости расходов на факторы производства;

для фирмы

т Р п модель: XРа + XSjf жf =£pJgj, *=1 f=l 7=1 в векторной форме: раj + 5 jк = pgj; целевая потреби- тах У4 (gj, аj) при тельская paj + = pgj, функция: или: общий расход потребителей на покупку товаров и услуг равен сумме их общего дохода от продажи или факторов производства фирмам и доходов потребителей как собственников капитала;

для потребителей

для рынка товаров потребления Н Р модель: Xgf Xqíj , j=l f=l или: сумма покупок товаров потребления равна сумме продаж фирм;

для рынка факторов производства Р Н модель: X а{ =X а1, f=l Ч=1 или: сумма потребленных фирмами производственных факторов равна сумме этих факторов, проданных потребителями;

для общего равновесия (закон Вальраса с добавлением варианта получения прибыли владельцами капитала) Н т Н Ч модель: XX piaj +к = XX Pjgjj, Ч=1 1=1 Ч=1 7=1 или: общий доход всех потребителей вместе с общей прибылью всех фирм равняется общей (суммарной) цене потребительских товаров (спрос равен предложению).

gj - общее количество_)-го товара, купленного потребителем Ь;

и j = ^ ^, g 2j ...gj, а1, а 2j ...а* )= ^ ^, aj) - функция общей полезности потребления товаров и услуг и от проданных факторов для потребителя Ь;

- доля участия потребителя Ь в капитале фирм Б;

ж - прибыль всех фирм - к=к ,к ...к ).

Приведенные модели равновесия (пять групп) можно анализировать с помощью СМО с переменными параметрами поступления и обслуживания (саморегулирующиеся системы), учитывая четыре следующих основных момента. Во-первых, в этих моделях на лицо действие случайных факторов (колебания на рынке, банкротства фирм, различные экзогенные перемены и другие). Во-вторых, по аналогии с длиной очереди N в виде разности [х1 ]—[х 2 ] здесь от равенств легко можно перейти к разности вследствие того, что эти равенства могут быть выполнены только в идеале, а не на практике. И, в-третьих, с появляющейся возможностью прогнозирования падения и роста этих показателей в зависимости от параметров распределений случайных факторов. В-четвертых - это наличие ограниченности ресурсов.

Масштабированием переменных, области решения уравнения Колмогорова можно привести к стандартной форме, показанной на рисунке 1.

Приведенная выше методика реализована в виде программного модуля в пакете прикладных программ вероятностного моделирования сложных систем.

Список использованной литературы:

1. Бусленко Н.П. Моделирование сложных систем. - М.:Наука, 1978. - 399с.

2. Смирнов А.Д. и др. Рыночная экономика.: Учебник.- М.: СОМИНТЭК, 1992. -256с.

3. Котлер Ф. Основы маркетинга. - С.Петербург.: АО «КОРУНА», АОЗТ «ЛИТЕРА ПЛЮС», 1994. - 699с.

4. Тарасов В.Н. Расчет сетевых моделей вычислительных систем с конечной очередью. Изв.ВУЗов СССР - Приборостроение, 1982, №11, - 53-57с.

5. Тарасов В.Н., Бахарева Н.Ф. Непрерывные диффузионные модели массового обслуживания и методика расчета их характеристик. Вестник ОГУ, 2002, №2.