ЗАДАЧИ СИНТЕЗА СИСТЕМ С ПОТЕРЯМИ
57
УДК 681.2
Т. И. АЛИЕВ
ЗАДАЧИ СИНТЕЗА СИСТЕМ С ПОТЕРЯМИ
Формулируются задачи синтеза систем с потерями при наличии различных ограничений на характеристики их функционирования. В процессе синтеза определяются емкость накопителя и производительность устройства, обеспечивающие минимальную стоимость системы. Ключевые слова: система с потерями, накопитель ограниченной емкости, производительность, вероятность потери, время пребывания, стоимость системы.
Введение. Проектирование дискретных систем со стохастическим характером функционирования, примерами которых могут служить информационно-управляющие системы, серверы локальных вычислительных сетей, сетевое оборудование (маршрутизаторы, коммутаторы) и т.п., осуществляется с использованием различных моделей и методов в зависимости от класса проектируемой системы, ее особенностей и требований, предъявляемых к качеству ее функционирования. При проектировании технических систем в качестве моделей целесообразно использовать системы и сети массового обслуживания с потерями, которые имеют накопители ограниченной емкости [1]. При некоторых предположениях могут быть получены аналитические зависимости для расчета характеристик дискретных систем со стохастическим характером функционирования, что позволяет эффективно решать задачи оптимального синтеза.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 10
58 Т. И. Алиев
К основным характеристикам, определяющим эффективность функционирования сис-
тем с потерями, относятся: вероятность потери заявок π , среднее время пребывания заявок в
системе u и стоимость системы S .
Требуемое качество функционирования системы, задаваемое в виде ограничений, нала-
гаемых на характеристики, обеспечивается в процессе синтеза за счет выбора структурно-
функциональной организации системы.
Описание системы. Положим, что исследуемая система содержит одно устройство, об-
рабатывающее заявки (запросы, команды, транзакции, детали и т.п.), поступающие в систему
в случайные моменты времени из неограниченного источника заявок. Поступающие заявки
образуют однородный поток и создают в системе однородную нагрузку. Средний интервал
между заявками равен a. Средняя ресурсоемкость, измеряемая количеством работы, которое
затрачивается на обработку одной заявки, равна θ . Скорость обработки одной заявки устрой-
ством (производительность, или быстродействие, устройства), измеряемая количеством рабо-
ты, выполняемой устройством за единицу времени, равна V . В каждый момент времени уст-
ройство может обрабатывать только одну заявку. Заявки, поступившие в систему во время
обработки устройством ранее поступившей заявки, располагаются в накопителе емкостью E,
при этом обрабатываемая заявка также занимает одно место в накопителе. Заявка, поступив-
шая в систему, теряется, если накопитель заполнен.
Расчет характеристик системы с потерями. Положим, что в систему поступает про-
стейший поток заявок с интенсивностью λ = 1 a , длительность обработки которых распреде-
лена по экспоненциальному закону со средним значением b, причем нагрузка может прини-
мать любые положительные значения:
y
=
λθ V
>
0
.
(1)
В этом случае вероятность того, что в системе с накопителем емкостью E находится k
заявок k = 0, 1, 2, ..., E, рассчитывается в зависимости от значения нагрузки:
pk
=
⎧ ⎪⎪ ⎨
yk (1 − y) 1 − yE+1
,
⎪ ⎪⎩
E
1 +
1
,
y ≠ 1, y = 1.
Тогда вероятность потери заявки из-за ограниченной емкости накопителя:
(2)
π
=
⎧ ⎪⎪ ⎨
yE (1 − y) 1 − yE+1
,
⎪ ⎩⎪
E
1 +
1
,
Соответственно загрузка системы составит
y ≠ 1, y = 1.
(3)
⎧⎛ ρ = λ0b = ⎪⎪⎨⎜⎜⎝1 −
yE (1 − y) 1 − yE+1
⎞ ⎟⎠⎟
y,
⎪ ⎪⎩
E E+
1
,
y ≠ 1, y = 1,
(4)
где λ0 = (1 − π)λ — интенсивность потока обслуженных заявок.
Среднее число заявок, находящихся в системе, и следовательно в накопителе, определяет-
ся через вероятности состояний (2):
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 10
Задачи синтеза систем с потерями
59
∑ ∑E
m = k pk
k =1
=
1
1 −
−y y E+1
E
k yk
k =1
,
из этого соотношения после некоторых преобразований получим:
m
=
⎧ ⎪⎪⎨1 −
y y E+1
⎡1 − yE
⎢ ⎣⎢
1−
y
−
E
y
E
⎤ ⎥
,
⎦⎥
⎪ ⎩⎪
E 2
,
Тогда среднее время пребывания заявок в системе:
y ≠ 1, y = 1.
(5)
u
=
m λ0
=
⎧ b ⎡1− yE
⎪ ⎪(1 − ⎨
π)(1 −
y E+1)
⎢ ⎢⎣
1−
y
⎪ ⎩⎪
2 (1
E −
π)λ
,
−
E
y
E
⎤ ⎥
,
⎦⎥
y ≠ 1, y = 1.
(6)
Анализ свойств системы. Одной из основных характеристик, определяющих эффек-
тивность функционирования систем с потерями, является вероятность потери заявок π
вследствие переполнения накопителя. Очевидно, что значение этого параметра зависит от
емкости накопителя E и производительности устройства V: π = f (E, V ) , чем больше E и V ,
тем меньше π .
На рис. 1 показан характер зависимостей вероятности потери заявок от емкости накопи-
теля (рис. 1, а) и производительности устройства (рис. 1, б) для системы с низкой (y11).
а) б) ππ 11
π2 π1 V1 > V2
E1 > E2
π∞
π1 = f(V)
π2 = f(V)
01
0 E0
V
Рис. 1
Вероятность потери заявок в случае единичной емкости накопителя (E=1) определяется
как
πi
=
1
yi + yi
(i = 1, 2) .
Заметим,
что
для
высоконагруженных
систем
( y2 > 1)
вероятность
потери заявок с увеличением емкости накопителя (E → ∞) стремится к некоторому пределу
π∞ . Этот предел обусловлен тем, что в случае λ2 > µ2 даже при неограниченной емкости накопителя доля обработанных заявок за единицу времени, равная отношению интенсивности
обработки µ2 = 1 b2 к интенсивности поступления λ2 , составит π0 = µ2 λ2 = 1 y2 . Следова-
тельно, доля необработанных заявок π∞ = 1 − y2−1 может рассматриваться как доля потерян-
ных заявок. Уменьшение вероятности потери заявок в системе за счет увеличения производительно-
сти V устройства и емкости E накопителя приводит к увеличению стоимости системы, кото-
рая может быть рассчитана как
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 10
60 Т. И. Алиев
S = Sу + Sн = αV β + s0 E ,
(7)
где Sу = αV β — стоимость устройства ( α и β — стоимостные коэффициенты пропорцио-
нальности и нелинейности соответственно); Sн = s0 E — стоимость накопителя ( s0 — стои-
мость единицы накопителя, предназначенной для одной заявки).
Постановка задачи синтеза. При отсутствии ограничений на характеристики функ-
ционирования системы в качестве обобщенного критерия эффективности может использо-
ваться функция следующего вида:
F = γ1π + γ2u + γ3S ,
(8)
где γ1, γ2 , γ3 — весовые коэффициенты, определяющие степень ценности (важности) соот-
ветствующей характеристики для синтезируемой системы и удовлетворяющие условию
γ1 + γ2 + γ3 = 1, а π, u и S — определяются соответственно выражениями (3), (6) и (7).
В этом случае задача синтеза формулируется следующим образом: определить емкость
накопителя и производительность устройства, при которых критерий эффективности (8) при-
нимает минимальное значение.
На рис. 2 иллюстрируется задача определения оптимальных значений емкости накопи-
теля и производительности устройства. Здесь представлены графики, показывающие зависи-
мость вероятности потерь π(E,V ) , среднего времени пребывания u(E) и u(V ) , стоимости
системы S = αV (предполагается, что β = 1) и критерия эффективности (8) от вектора опти-
мизируемых параметров (E,V ) . Значения (E,V )opt , соответствующие минимуму критерия
эффективности F , являются оптимальными.
π, u, S, F
1
F
u(V) π1
u(E)
S
π(E, V)
0 (E, V)opt
(E, V)
Рис. 2
Отметим, что зависимости среднего времени пребывания заявок в системе u(E) и u(V ) ,
представленные на рис. 2 пунктирными кривыми, ведут себя по-разному при увеличении со-
ответственно емкости накопителя Е и производительности устройства V: среднее время пре-
бывания заявок в системе растет с увеличением емкости и снижается с увеличением произво-
дительности. При этом зависимость u(E) может иметь разный характер — возрастающий,
убывающий или любой другой.
При наличии ограничений на характеристики задача синтеза системы с одним устройст-
вом и накопителем ограниченной емкости может быть сформулирована в четырех постановках
в зависимости от ограничений, а именно — определить производительность V устройства и
емкость E накопителя, обеспечивающие выполнение ограничений (обозначено звездочкой):
1) на вероятность потери заявок π ≤ π* при минимальной стоимости системы S ;
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 10
Задачи синтеза систем с потерями
61
2) на вероятность потери заявок π ≤ π* и среднее время пребывания заявок в системе
u ≤ u* при минимальной стоимости системы S ;
3) на вероятность потери π ≤ π* и стоимость системы S < S* при минимальном значении среднего времени пребывания заявок в системе u ;
4) на среднее время пребывания заявок в системе u ≤ u* и на стоимость системы S ≤ S* при минимальном значении вероятности потери заявок π .
Алгоритм синтеза. Рассмотрим задачу синтеза применительно к первой и второй постановкам.
Выражение (2) позволяет определить емкость накопителя для заданного ограничения
π* при известной нагрузке y , т.е. при известной производительности V устройства:
E
≥
⎧⎪log ⎪
y
1
−
⎨ ⎪1 ⎩⎪
− π* π*
,
π* y(1 −
π*
)
,
y ≠ 1, y = 1.
В общей постановке задачи синтеза производительность устройства неизвестна и под-
лежит определению. Поскольку получить решение задачи оптимального синтеза в явном ана-
литическом виде с использованием зависимостей (1)—(6) не представляется возможным,
один из подходов к решению задачи ввиду небольшого числа оптимизируемых параметров
состоит в последовательном переборе значений емкости накопителя E. При этом для каждого
значения E с использованием выражения (3) может быть определена минимальная произво-
дительность устройства V, при которой выполняется заданное ограничение на вероятность
потери заявок:
yE (1 − y) 1 − yE+1
≤
π* .
С учетом (1) преобразуем последнее неравенство к виду:
V E+1
−
(λθ)E π*
V
+
(λθ)E
+1
⎛ ⎝⎜
1 π*
− 1⎞⎠⎟
≥
0.
Решив полученное неравенство относительно V при заданном значении емкости E , например, с использованием одного из численных методов [2], можно определить минимальное
значение производительности устройства V , при котором обеспечивается ограничение π* . В частности, при E = 1 последнее выражение примет вид:
V
2
−
λθ π*
V
+
(λθ)2
⎛ ⎝⎜
1 π*
− 1⎠⎟⎞
≥
0
,
откуда получим:
V
≥
1 − π* π*
λθ .
Рассмотрим пример со следующими исходными данными: λ = 1с–1; θ = 400 единиц (ед.); α = 100 ; β = 0,5 ; s0 = 50 ; π* = 0, 05 .
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 10
62 Т. И. Алиев
В таблице представлены результаты расчетов для разных значений емкости накопителя, из которой следует, что минимальная стоимость системы S = 2534 у.ед. достигается при E = 7 и V = 477 ед./с.
Е m u, c V, с–1 S, у.ед.
4 1,5 1,5 594 2637
5 1,9 2,0 537 2567
6 2,8 2,5 501 2538
7 2,9 3,0 477 2534
8 3,4 3,6 459 2542
9 3,9 4,1 446 2562
10 4,5 4,7 436 2588
11 5,1 5,3 428 2619
12 5,6 5,9 422 2654
Во второй постановке задачи синтеза дополнительное ограничение налагается на среднее время пребывания заявок: u ≤ u*. Если в результате синтеза на предыдущем этапе это ограничение не выполняется, необходимо увеличить производительность устройства, что приведет к повышению стоимости системы. При этом вероятность потери заявок уменьшится и, следовательно, можно попытаться снизить стоимость системы за счет уменьшения емкости накопителя.
Положим, что в нашем примере дополнительно задано ограничение u* = 2,5 с. Для того
чтобы при E = 7 выполнялось это условие, необходимо увеличить производительность устройства до V = 518 ед./с, что приведет к увеличению стоимости системы до S = 2626 у.ед.
В результате предпочтительным оказывается вариант построения системы с накопителем емкостью E = 6 (см. таблицу) и стоимостью S = 2538 у.ед.
Синтез систем с двумя устройствами. Предложенный подход может быть распространен на системы с двумя последовательно расположенными устройствами, в которых заявки после обработки в первом устройстве направляются ко второму устройству. Производительность 1-го и 2-го устройства и емкость накопителей обозначим как V1, V2 и E1, E2 . Тогда стоимость системы и вероятность потери заявок в системе:
S = α1V1β1 + α2V2β2 + s0 (E1 + E2 ) и π = π1 + π2 (1 − π1) .
С учетом ограничения на вероятность потери в системе π* и последнего выражения по-
лучим: π2 ≤ (π* − π1) (1 − π1) , где правая часть неравенства представляет собой ограничение на вероятность потери во втором устройстве при известном значении вероятности потери в первом устройстве. Таким образом, если известна вероятность потери заявок в первом устройстве, то задача синтеза для второго устройства при некоторых условиях может быть сведена к задаче синтеза системы с одним устройством.
Положим, что в первое устройство поступает простейший поток заявок с интенсивностью λ , а длительности обработки в устройствах распределены по экспоненциальному закону со средним значением bi = θi Vi (i = 1; 2) . При этих предположениях задача синтеза для
первого устройства решается с использованием выражений (1)—(6) для π1* = (0, 25⎯ 0, 75) π* .
В качестве результирующего принимается значение π1*, при котором обеспечивается минимальная стоимость первого устройства. Тогда ограничение на вероятность потери для второго устройства: π*2 = (π* − π1* ) (1 − π1*). Для того чтобы можно было воспользоваться выражениями (1)—(6) для второго устройства и решения задачи синтеза, необходимо выполнить анализ характера потока заявок, покидающих первое устройство и образующих входной поток заявок во второе устройство.
Многочисленные имитационные эксперименты показали, что коэффициент вариации ν выходящего потока из первого устройства зависит от нагрузки y1 и емкости E1 накопителя и
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 10
Задачи синтеза систем с потерями
63
принимает значения в интервале ν = 0,7—1 при E1 = 1 и ν = 0,95—1 при E1 = 4 (рис. 3), причем наименьшие значения коэффициента вариации достигаются при нагрузке y = 1. Другими
словами, чем больше E1, тем ближе к единице коэффициент вариации выходящего потока, что при E1 ≥ 4 позволяет использовать выражения (1)—(6) с высокой степенью точности для расчета характеристик функционирования второго устройства.
ν
1,0 Е=4
0,9 Е=2
0,8
Е=1 0,7
0,5 0,9 1 2
4 10 y
Рис. 3
Кроме того, предположение о простейшем потоке заявок ко второму устройству позво-
ляет получить верхнюю оценку вероятности потери во втором устройстве.
Заключение. Рассмотренный подход к решению задач синтеза систем с потерями и по-
лученные результаты позволяют определить не только емкость накопителей, но и оценить
требования к производительности устройств, входящих в состав системы, с учетом совокуп-
ных затрат на построение системы для широкого диапазона параметров нагрузки.
СПИСОК ЛИТЕРАТУРЫ
1. Алиев Т. И. Основы моделирования дискретных систем. СПб: СПбГУ ИТМО, 2009. 363 с.
2. Формалев В. Ф., Ревизников Д. Л. Численные методы. М.: Физматлит, 2006. 398 с.
Сведения об авторе Тауфик Измайлович Алиев — д-р техн. наук, профессор; Санкт-Петербургский национальный исследова-
тельский университет информационных технологий, механики и оптики, кафедра вычислительной техники; заведующий кафедрой; E-mail: aliev@d1.ifmo.ru
Рекомендована кафедрой вычислительной техники
Поступила в редакцию 08.02.12 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 10
УДК 681.2
Т. И. АЛИЕВ
ЗАДАЧИ СИНТЕЗА СИСТЕМ С ПОТЕРЯМИ
Формулируются задачи синтеза систем с потерями при наличии различных ограничений на характеристики их функционирования. В процессе синтеза определяются емкость накопителя и производительность устройства, обеспечивающие минимальную стоимость системы. Ключевые слова: система с потерями, накопитель ограниченной емкости, производительность, вероятность потери, время пребывания, стоимость системы.
Введение. Проектирование дискретных систем со стохастическим характером функционирования, примерами которых могут служить информационно-управляющие системы, серверы локальных вычислительных сетей, сетевое оборудование (маршрутизаторы, коммутаторы) и т.п., осуществляется с использованием различных моделей и методов в зависимости от класса проектируемой системы, ее особенностей и требований, предъявляемых к качеству ее функционирования. При проектировании технических систем в качестве моделей целесообразно использовать системы и сети массового обслуживания с потерями, которые имеют накопители ограниченной емкости [1]. При некоторых предположениях могут быть получены аналитические зависимости для расчета характеристик дискретных систем со стохастическим характером функционирования, что позволяет эффективно решать задачи оптимального синтеза.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 10
58 Т. И. Алиев
К основным характеристикам, определяющим эффективность функционирования сис-
тем с потерями, относятся: вероятность потери заявок π , среднее время пребывания заявок в
системе u и стоимость системы S .
Требуемое качество функционирования системы, задаваемое в виде ограничений, нала-
гаемых на характеристики, обеспечивается в процессе синтеза за счет выбора структурно-
функциональной организации системы.
Описание системы. Положим, что исследуемая система содержит одно устройство, об-
рабатывающее заявки (запросы, команды, транзакции, детали и т.п.), поступающие в систему
в случайные моменты времени из неограниченного источника заявок. Поступающие заявки
образуют однородный поток и создают в системе однородную нагрузку. Средний интервал
между заявками равен a. Средняя ресурсоемкость, измеряемая количеством работы, которое
затрачивается на обработку одной заявки, равна θ . Скорость обработки одной заявки устрой-
ством (производительность, или быстродействие, устройства), измеряемая количеством рабо-
ты, выполняемой устройством за единицу времени, равна V . В каждый момент времени уст-
ройство может обрабатывать только одну заявку. Заявки, поступившие в систему во время
обработки устройством ранее поступившей заявки, располагаются в накопителе емкостью E,
при этом обрабатываемая заявка также занимает одно место в накопителе. Заявка, поступив-
шая в систему, теряется, если накопитель заполнен.
Расчет характеристик системы с потерями. Положим, что в систему поступает про-
стейший поток заявок с интенсивностью λ = 1 a , длительность обработки которых распреде-
лена по экспоненциальному закону со средним значением b, причем нагрузка может прини-
мать любые положительные значения:
y
=
λθ V
>
0
.
(1)
В этом случае вероятность того, что в системе с накопителем емкостью E находится k
заявок k = 0, 1, 2, ..., E, рассчитывается в зависимости от значения нагрузки:
pk
=
⎧ ⎪⎪ ⎨
yk (1 − y) 1 − yE+1
,
⎪ ⎪⎩
E
1 +
1
,
y ≠ 1, y = 1.
Тогда вероятность потери заявки из-за ограниченной емкости накопителя:
(2)
π
=
⎧ ⎪⎪ ⎨
yE (1 − y) 1 − yE+1
,
⎪ ⎩⎪
E
1 +
1
,
Соответственно загрузка системы составит
y ≠ 1, y = 1.
(3)
⎧⎛ ρ = λ0b = ⎪⎪⎨⎜⎜⎝1 −
yE (1 − y) 1 − yE+1
⎞ ⎟⎠⎟
y,
⎪ ⎪⎩
E E+
1
,
y ≠ 1, y = 1,
(4)
где λ0 = (1 − π)λ — интенсивность потока обслуженных заявок.
Среднее число заявок, находящихся в системе, и следовательно в накопителе, определяет-
ся через вероятности состояний (2):
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 10
Задачи синтеза систем с потерями
59
∑ ∑E
m = k pk
k =1
=
1
1 −
−y y E+1
E
k yk
k =1
,
из этого соотношения после некоторых преобразований получим:
m
=
⎧ ⎪⎪⎨1 −
y y E+1
⎡1 − yE
⎢ ⎣⎢
1−
y
−
E
y
E
⎤ ⎥
,
⎦⎥
⎪ ⎩⎪
E 2
,
Тогда среднее время пребывания заявок в системе:
y ≠ 1, y = 1.
(5)
u
=
m λ0
=
⎧ b ⎡1− yE
⎪ ⎪(1 − ⎨
π)(1 −
y E+1)
⎢ ⎢⎣
1−
y
⎪ ⎩⎪
2 (1
E −
π)λ
,
−
E
y
E
⎤ ⎥
,
⎦⎥
y ≠ 1, y = 1.
(6)
Анализ свойств системы. Одной из основных характеристик, определяющих эффек-
тивность функционирования систем с потерями, является вероятность потери заявок π
вследствие переполнения накопителя. Очевидно, что значение этого параметра зависит от
емкости накопителя E и производительности устройства V: π = f (E, V ) , чем больше E и V ,
тем меньше π .
На рис. 1 показан характер зависимостей вероятности потери заявок от емкости накопи-
теля (рис. 1, а) и производительности устройства (рис. 1, б) для системы с низкой (y11).
а) б) ππ 11
π2 π1 V1 > V2
E1 > E2
π∞
π1 = f(V)
π2 = f(V)
01
0 E0
V
Рис. 1
Вероятность потери заявок в случае единичной емкости накопителя (E=1) определяется
как
πi
=
1
yi + yi
(i = 1, 2) .
Заметим,
что
для
высоконагруженных
систем
( y2 > 1)
вероятность
потери заявок с увеличением емкости накопителя (E → ∞) стремится к некоторому пределу
π∞ . Этот предел обусловлен тем, что в случае λ2 > µ2 даже при неограниченной емкости накопителя доля обработанных заявок за единицу времени, равная отношению интенсивности
обработки µ2 = 1 b2 к интенсивности поступления λ2 , составит π0 = µ2 λ2 = 1 y2 . Следова-
тельно, доля необработанных заявок π∞ = 1 − y2−1 может рассматриваться как доля потерян-
ных заявок. Уменьшение вероятности потери заявок в системе за счет увеличения производительно-
сти V устройства и емкости E накопителя приводит к увеличению стоимости системы, кото-
рая может быть рассчитана как
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 10
60 Т. И. Алиев
S = Sу + Sн = αV β + s0 E ,
(7)
где Sу = αV β — стоимость устройства ( α и β — стоимостные коэффициенты пропорцио-
нальности и нелинейности соответственно); Sн = s0 E — стоимость накопителя ( s0 — стои-
мость единицы накопителя, предназначенной для одной заявки).
Постановка задачи синтеза. При отсутствии ограничений на характеристики функ-
ционирования системы в качестве обобщенного критерия эффективности может использо-
ваться функция следующего вида:
F = γ1π + γ2u + γ3S ,
(8)
где γ1, γ2 , γ3 — весовые коэффициенты, определяющие степень ценности (важности) соот-
ветствующей характеристики для синтезируемой системы и удовлетворяющие условию
γ1 + γ2 + γ3 = 1, а π, u и S — определяются соответственно выражениями (3), (6) и (7).
В этом случае задача синтеза формулируется следующим образом: определить емкость
накопителя и производительность устройства, при которых критерий эффективности (8) при-
нимает минимальное значение.
На рис. 2 иллюстрируется задача определения оптимальных значений емкости накопи-
теля и производительности устройства. Здесь представлены графики, показывающие зависи-
мость вероятности потерь π(E,V ) , среднего времени пребывания u(E) и u(V ) , стоимости
системы S = αV (предполагается, что β = 1) и критерия эффективности (8) от вектора опти-
мизируемых параметров (E,V ) . Значения (E,V )opt , соответствующие минимуму критерия
эффективности F , являются оптимальными.
π, u, S, F
1
F
u(V) π1
u(E)
S
π(E, V)
0 (E, V)opt
(E, V)
Рис. 2
Отметим, что зависимости среднего времени пребывания заявок в системе u(E) и u(V ) ,
представленные на рис. 2 пунктирными кривыми, ведут себя по-разному при увеличении со-
ответственно емкости накопителя Е и производительности устройства V: среднее время пре-
бывания заявок в системе растет с увеличением емкости и снижается с увеличением произво-
дительности. При этом зависимость u(E) может иметь разный характер — возрастающий,
убывающий или любой другой.
При наличии ограничений на характеристики задача синтеза системы с одним устройст-
вом и накопителем ограниченной емкости может быть сформулирована в четырех постановках
в зависимости от ограничений, а именно — определить производительность V устройства и
емкость E накопителя, обеспечивающие выполнение ограничений (обозначено звездочкой):
1) на вероятность потери заявок π ≤ π* при минимальной стоимости системы S ;
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 10
Задачи синтеза систем с потерями
61
2) на вероятность потери заявок π ≤ π* и среднее время пребывания заявок в системе
u ≤ u* при минимальной стоимости системы S ;
3) на вероятность потери π ≤ π* и стоимость системы S < S* при минимальном значении среднего времени пребывания заявок в системе u ;
4) на среднее время пребывания заявок в системе u ≤ u* и на стоимость системы S ≤ S* при минимальном значении вероятности потери заявок π .
Алгоритм синтеза. Рассмотрим задачу синтеза применительно к первой и второй постановкам.
Выражение (2) позволяет определить емкость накопителя для заданного ограничения
π* при известной нагрузке y , т.е. при известной производительности V устройства:
E
≥
⎧⎪log ⎪
y
1
−
⎨ ⎪1 ⎩⎪
− π* π*
,
π* y(1 −
π*
)
,
y ≠ 1, y = 1.
В общей постановке задачи синтеза производительность устройства неизвестна и под-
лежит определению. Поскольку получить решение задачи оптимального синтеза в явном ана-
литическом виде с использованием зависимостей (1)—(6) не представляется возможным,
один из подходов к решению задачи ввиду небольшого числа оптимизируемых параметров
состоит в последовательном переборе значений емкости накопителя E. При этом для каждого
значения E с использованием выражения (3) может быть определена минимальная произво-
дительность устройства V, при которой выполняется заданное ограничение на вероятность
потери заявок:
yE (1 − y) 1 − yE+1
≤
π* .
С учетом (1) преобразуем последнее неравенство к виду:
V E+1
−
(λθ)E π*
V
+
(λθ)E
+1
⎛ ⎝⎜
1 π*
− 1⎞⎠⎟
≥
0.
Решив полученное неравенство относительно V при заданном значении емкости E , например, с использованием одного из численных методов [2], можно определить минимальное
значение производительности устройства V , при котором обеспечивается ограничение π* . В частности, при E = 1 последнее выражение примет вид:
V
2
−
λθ π*
V
+
(λθ)2
⎛ ⎝⎜
1 π*
− 1⎠⎟⎞
≥
0
,
откуда получим:
V
≥
1 − π* π*
λθ .
Рассмотрим пример со следующими исходными данными: λ = 1с–1; θ = 400 единиц (ед.); α = 100 ; β = 0,5 ; s0 = 50 ; π* = 0, 05 .
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 10
62 Т. И. Алиев
В таблице представлены результаты расчетов для разных значений емкости накопителя, из которой следует, что минимальная стоимость системы S = 2534 у.ед. достигается при E = 7 и V = 477 ед./с.
Е m u, c V, с–1 S, у.ед.
4 1,5 1,5 594 2637
5 1,9 2,0 537 2567
6 2,8 2,5 501 2538
7 2,9 3,0 477 2534
8 3,4 3,6 459 2542
9 3,9 4,1 446 2562
10 4,5 4,7 436 2588
11 5,1 5,3 428 2619
12 5,6 5,9 422 2654
Во второй постановке задачи синтеза дополнительное ограничение налагается на среднее время пребывания заявок: u ≤ u*. Если в результате синтеза на предыдущем этапе это ограничение не выполняется, необходимо увеличить производительность устройства, что приведет к повышению стоимости системы. При этом вероятность потери заявок уменьшится и, следовательно, можно попытаться снизить стоимость системы за счет уменьшения емкости накопителя.
Положим, что в нашем примере дополнительно задано ограничение u* = 2,5 с. Для того
чтобы при E = 7 выполнялось это условие, необходимо увеличить производительность устройства до V = 518 ед./с, что приведет к увеличению стоимости системы до S = 2626 у.ед.
В результате предпочтительным оказывается вариант построения системы с накопителем емкостью E = 6 (см. таблицу) и стоимостью S = 2538 у.ед.
Синтез систем с двумя устройствами. Предложенный подход может быть распространен на системы с двумя последовательно расположенными устройствами, в которых заявки после обработки в первом устройстве направляются ко второму устройству. Производительность 1-го и 2-го устройства и емкость накопителей обозначим как V1, V2 и E1, E2 . Тогда стоимость системы и вероятность потери заявок в системе:
S = α1V1β1 + α2V2β2 + s0 (E1 + E2 ) и π = π1 + π2 (1 − π1) .
С учетом ограничения на вероятность потери в системе π* и последнего выражения по-
лучим: π2 ≤ (π* − π1) (1 − π1) , где правая часть неравенства представляет собой ограничение на вероятность потери во втором устройстве при известном значении вероятности потери в первом устройстве. Таким образом, если известна вероятность потери заявок в первом устройстве, то задача синтеза для второго устройства при некоторых условиях может быть сведена к задаче синтеза системы с одним устройством.
Положим, что в первое устройство поступает простейший поток заявок с интенсивностью λ , а длительности обработки в устройствах распределены по экспоненциальному закону со средним значением bi = θi Vi (i = 1; 2) . При этих предположениях задача синтеза для
первого устройства решается с использованием выражений (1)—(6) для π1* = (0, 25⎯ 0, 75) π* .
В качестве результирующего принимается значение π1*, при котором обеспечивается минимальная стоимость первого устройства. Тогда ограничение на вероятность потери для второго устройства: π*2 = (π* − π1* ) (1 − π1*). Для того чтобы можно было воспользоваться выражениями (1)—(6) для второго устройства и решения задачи синтеза, необходимо выполнить анализ характера потока заявок, покидающих первое устройство и образующих входной поток заявок во второе устройство.
Многочисленные имитационные эксперименты показали, что коэффициент вариации ν выходящего потока из первого устройства зависит от нагрузки y1 и емкости E1 накопителя и
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 10
Задачи синтеза систем с потерями
63
принимает значения в интервале ν = 0,7—1 при E1 = 1 и ν = 0,95—1 при E1 = 4 (рис. 3), причем наименьшие значения коэффициента вариации достигаются при нагрузке y = 1. Другими
словами, чем больше E1, тем ближе к единице коэффициент вариации выходящего потока, что при E1 ≥ 4 позволяет использовать выражения (1)—(6) с высокой степенью точности для расчета характеристик функционирования второго устройства.
ν
1,0 Е=4
0,9 Е=2
0,8
Е=1 0,7
0,5 0,9 1 2
4 10 y
Рис. 3
Кроме того, предположение о простейшем потоке заявок ко второму устройству позво-
ляет получить верхнюю оценку вероятности потери во втором устройстве.
Заключение. Рассмотренный подход к решению задач синтеза систем с потерями и по-
лученные результаты позволяют определить не только емкость накопителей, но и оценить
требования к производительности устройств, входящих в состав системы, с учетом совокуп-
ных затрат на построение системы для широкого диапазона параметров нагрузки.
СПИСОК ЛИТЕРАТУРЫ
1. Алиев Т. И. Основы моделирования дискретных систем. СПб: СПбГУ ИТМО, 2009. 363 с.
2. Формалев В. Ф., Ревизников Д. Л. Численные методы. М.: Физматлит, 2006. 398 с.
Сведения об авторе Тауфик Измайлович Алиев — д-р техн. наук, профессор; Санкт-Петербургский национальный исследова-
тельский университет информационных технологий, механики и оптики, кафедра вычислительной техники; заведующий кафедрой; E-mail: aliev@d1.ifmo.ru
Рекомендована кафедрой вычислительной техники
Поступила в редакцию 08.02.12 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 10