Автоматика и телемеханика, № 11, 2021
© 2021 г. Ю.А. ДОРОФЕЮК, канд. техн. наук (dorofeyuk_julia@mail.ru),
В.А. ЛАПТИН (straqker@bk.ru)
(МГУ им. М.В. Ломоносова),
А.С. МАНДЕЛЬ, д-р техн. наук (almandel@yandex.ru)
(Институт проблем управления им. В.А. Трапезникова РАН, Москва)
ОЦЕНКА ПАРАМЕТРОВ И СТРУКТУРЫ СИСТЕМ МАССОВОГО
ОБСЛУЖИВАНИЯ С ПЕРЕКЛЮЧЕНИЕМ КАНАЛОВ
Рассматривается задача оценки структуры и параметров системы мас-
сового обслуживания при реализации системы оптимального переклю-
чения основных каналов обслуживания в моменты контроля, отстоящие
друг от друга на фиксированный временной шаг. Для решения задачи
оценки структуры и параметров модели предложены процедуры эксперт-
но-классификационного анализа, структурного прогнозирования и экс-
пертно-статистической обработки данных.
Ключевые слова: управляемые системы массового обслуживания, мар-
ковский входящий поток, оценивание структуры и параметров, эксперт-
но-классификационный анализ, структурное прогнозирование, эксперт-
но-статистическая обработка данных.
DOI: 10.31857/S0005231021110040
1. Введение
Рассматривается задача оценки структуры и параметров модели опти-
мального управления системой массового обслуживания (СМО), описанной
в [1], где сделано предположение о скачкообразном марковском пошаговом из-
менении интенсивности простейшего входящего потока. В результате сделан
вывод о том, что классические методы статистического оценивания не вполне
пригодны для исследования структуры (числа элементов множества и зна-
чений различных интенсивностей входящего потока), а также вероятностей
перехода из состояния в состояние. В качестве альтернативы предлагается
набор процедур экспертно-классификационного анализа [2, 3], структурного
прогнозирования [4] и экспертно-статистической обработки данных [5].
2. Модель системы массового обслуживания
Как отмечено в [1], в исследуемой СМО число рабочих каналов обслужи-
вания может изменяться в моменты контроля, отстоящие друг от друга на
фиксированное время — шаг контроля. При этом считается, что в СМО по-
ступает простейший входящий поток, интенсивность которого λ(t) на протя-
жении шага постоянна, а в моменты контроля претерпевает скачкообразные
68
марковские изменения, принимая конечное число k значений λi из дискрет-
ного множества Λ = {λi, i ∈ 1, k}. Задача заключается в том, чтобы сформи-
ровать стратегию переключения рабочих каналов (отключения части работа-
ющих каналов или введение в действие дополнительных резервных каналов),
которая минимизирует средние затраты СМО на заданном N-шаговом перио-
де планирования. Задана матрица вероятностей перехода соответствующей
однородной марковской цепи P = ∥pij∥, где pij - это вероятность перехода
(в момент контроля) от интенсивности λi, i ∈ 1, k, на предыдущем шаге к
интенсивности λj , j ∈ 1, k, на следующем шаге.
В [1] показано, что решение задачи о выборе оптимальной стратегии пере-
ключения каналов сводится к решению следующей системы уравнений дис-
кретного динамического программирования:
(1)
C∗1(λi,m) = min C(1)(λi
,m,u),
u≥ui
⎧
⎫
⎨
∑
⎬
(2)
C∗n(λi,m) = min
C(1)(λi,m,u) + α
pijC∗n-1(λj,u)
,
n ∈ 2,N,
u≥ui
⎩
⎭
j=1
где C∗n(λi, m) - минимальное возможное значение суммарных средних затрат
на n последних шагах процесса управления, когда математическое ожидание
берется по траектории изменения интенсивности входящего потока, интен-
сивность которого совершает марковские скачки. Переменная u в уравнениях
(1)-(2) определяет текущее (за n шагов до конца процесса) значение управ-
ляющего решения о числе включаемых рабочих каналов.
3. Постановка задачи
Главное, что предстоит оценить в процессе практического использования
модели (1), (2), - это точки множества значений интенсивностей входящего
потока Λ = {λi}, i ∈ 1, k (структура системы) и значения вероятностей пе-
рехода (параметры системы) соответствующей однородной марковской цепи
P = ∥pij∥, где pij - это вероятность перехода (в момент контроля) от ин-
тенсивности λi, i ∈ 1, k, на предыдущем шаге к интенсивности λj , j ∈ 1, k,
на следующем шаге. При этом важно понимать, что модель (1)-(2) являет-
ся лишь приближением к описанию реальной ситуации, в которой четких
скачков не наблюдается (процесс, конечно, размыт во времени, да и сами
значения λi из множества Λ могут “ползти”, постепенно изменяясь от шага
к шагу). Поэтому довольно сложно представить себе процедуру статистиче-
ского оценивания указанных параметров и вероятностей перехода в рамках
классической статистической теории.
В связи с этим для решения проблемы оценки структуры системы и ее па-
раметров в работе была избрана концепция структурного прогнозирования
в понимании публикации [4] с привлечением методов экспертно-классифи-
кационного анализа [2, 3] и элементов экспертно-статистической обработки
данных [5].
69
3.1. Результаты наблюдений для управляемых СМО
Естественно, что результаты наблюдений сильно связаны с предметной об-
ластью, к которой относятся соответствующие СМО. При этом эти данные
могут быть чрезвычайно разнородны, что представляет собой дополнитель-
ную проблему [6]. Как минимум, они представляют собой данные о средних
интенсивностях входящих потоков на каждом шаге, сведения о конкретных
СМО (бюджет, положение на рынке, приоритеты обслуживания различных
требований, конъюнктура рынка и т.д.). Например, если СМО представля-
ет собой кассовый зал кинотеатра, то привлекательность услуги по продаже
билета может обусловливаться жанром фильма, его бюджетом, названием
студии-производителя, именами режиссера и актеров и другими признаками.
При этом в качестве разных объектов могут выступать отдельные отрезки
времени с результатами наблюдений за одной и той же системой массового
обслуживания. Каждый раз задача выбора набора наблюдений решается в
зависимости от указанных обстоятельств.
Следует понимать, что последующие применения результатов обработки
этих данных представляют собой предложение вариантов управляющих ре-
шений для некой системы поддержки принятия решений (СППР), что также
порождает необходимость учитывать различные особенности СППР. Прежде
всего приходится иметь в виду наличие объектов нечисловой природы [7],
обязательность выполнения экспертных оценок [8], включая проведение в
некоторых случаях многовариантной экспертизы [9], и, наконец, особенности
инженерии информационно-управляющих систем [10].
В результате решения задачи выбора наблюдений образуется совокупность
объектов. Каждый объект описывается набором параметров и представля-
ется отрезком траектории в пространстве состояний. Соответствующий на-
бор отрезков траекторий назовем обучающей выборкой. Изучается поведе-
ние этого множества объектов (отрезков траекторий) в дискретные момен-
ты времени. Вводится в рассмотрение m-мерное (по числу параметров) про-
странство параметров X, в котором j-й объект в момент времени n представ-
ляется точкой xj(n) = {x(1)j(n), x(2)j(n), . . . , x(m)j(n)}. Совокупность векторов
{xj(1), xj(2), . . . , xj(n)} представляет отрезок траектории движения (динами-
ки) j-го объекта.
3.2. Формирование начального приближения к структуре кластеров
Начальное приближение к структуре кластеров, в которую отображает-
ся рассматриваемая совокупность объектов, строится с использованием ком-
плексного алгоритм автоматической классификации [4].
Критериальной функцией при построении начального кластерного разбие-
ния является функционал вида
∑
pi
(3)
J1 =
K(Ai, Aj
) (r
- число классов),
p
i=1
70
где через Ai обозначены кластеры точек, r - число этих кластеров, а
∑∑
2
(4)
K(Ai, Aj ) =
K(xi, xj )
pi(1 - pi)
i=1 j>i
— мера близости между собой отдельных кластеров, которая рассчитывается
с помощью классической потенциальной функции близости двух точек [11]:
1
(5)
K(x, y) =
,
1 + αRm(x,y)
где Rm(x, y) - некая метрика в пространстве X, а α и m - настраиваемые
параметры алгоритма.
Определение начального числа кластеров r может быть в зависимости от
контекста и степени формализации конкретной прикладной проблемы выпол-
нено автоматически или с использованием процедур экспертно-классифика-
ционного анализа. Соответствующие процедуры могут включать в свой со-
став процедуры перекрестной экспертизы [9], рассчитанные на то, чтобы до-
биться согласования мнений задействованных в процедуру принятия оконча-
тельных решений экспертов. При этом среди экспертов почти всегда присут-
ствует лицо, принимающее решения (ЛПР), которого в рамках лексики, что
используется в экспертно-статистических процедурах принятия решений [5],
называют главным экспертом.
4. Этапы решения задачи
4.1. Процедура оценки начального приближения
к вероятностям перехода объектов
После того как в соответствии с рекомендациями подраздела 3.2 вы-
делена начальная кластерная структура {Ai}r(i=1), определяются “центры”1
кластеров начального разбиения ai(1) всех выделенных кластеров R(1)ji =
= R(xj(1),ai(1)), i = 1,... ,k; j = 1,... ,p. При этом, как отмечается в [12],
в некоторых случаях для повышения степени корректности решений задачи
выделения центра может понадобиться отказаться от классических евклидо-
вых метрик в пользу метрик более экзотических.
При этом значения интенсивностей входящего потока λi, которые соответ-
ствуют объектам ai(1), формируют результирующее множество возможных
состояний идентифицируемой конечной цепи Маркова Λ = {λi}, i ∈ 1, r.
Затем при движении объектов по их индивидуальным траекториям, т.е. в
динамике, начинаются переходы объектов из кластера в кластер. В рамках
идеологии структурного прогнозирования [4] можно рассчитать вероятности
перехода каждого из объектов в каждый из выделенных кластеров.
1 Центры кластеров иногда называют эталонами кластера.
71
Элементы матрицы вероятностей перехода объекта j в кластер i2, значе-
ния p(1)ji = pji(1), могут быть рассчитаны по формуле
(1)
α
j
(6)
p(1)ji =
,
R(1)
ji
где R(1)ji - расстояние по выбранной метрике от точки (объекта) j до центра
i-го кластера ai(1) в начальный момент времени, а нормирующий множи-
тель α(1)j определяется выражением
∏r
R(1)ji
i=1
(7)
α(1)j =
∑p
∏r
1
R(1)
i=1
ji
j=1 R(1)
ji
4.2. Процедура оценки последующих приближений
После выделения начальной структуры и оценки начального приближения
к вероятностям перехода объектов на следующих шагах элементы матрицы
вероятностей перехода объекта j в кластер i модифицируются при помощи
процедуры соотнесения между собой расстояний между точкой (объектом) j
и центром кластера i в два соседних момента времени, т.е. в начале и кон-
це каждого шага. Обозначим соответствующее изменение расстояний через
ΔR(n)ji = R(n)ji - R(n-1)ji.
Если окажется, что j-я точка (объект) в момент n совпадала с центром
какого-либо кластера (под номером i0), т.е., что R(n) = 0, то принимаетсяji
0
соглашение, что вероятность для данного объекта остаться в этом кластере
равна 1, а стало быть, вероятность перехода в другой кластер равна 0:
{
1, если i = i0,
p(n)ji =
0, если i = 1, . . . , k, i = i0.
Для случая, когда R(n) = 0, происходит модификация всех переходныхji
0
вероятностей по формуле, которая несколько отличается от ее аналога в [4]:
{
[
]
}
)
1 + sign(ΔR(n)
ji
(8)
p(n)ji = γ p(n-1)ji +
- p(n-1)jisign(ΔR(n)ji) R(n)
,
ji
2
{
1, если z ≥ 0,
где, как обычно, sign(z) =
, а γ - нормирующий множитель,
0, если z < 0,
∑k
определяемый условием нормировки
p(n)ji = 1:
i=1
1
(9)
γ=
[
]
(n)
1+sign(ΔRji )
1+
- p(n-1)jisign(ΔR(n)ji) ΔR(n)
2
ji
2 Заметим, что эти вероятности не совпадают с искомыми вероятностями из алгорит-
ма (2) (см. ниже подраздел 4.3).
72
4.3. Способы оценки искомых вероятностей перехода pij из формулы (2)
Поскольку в (2) используются вероятности перехода pij рассматриваемой
СМО из кластера i в кластер j, а в двух предыдущих пунктах приводятся
прогнозные оценки вероятностей перехода конкретного объекта в конкретный
кластер, то в зависимости от характера обучающей выборки можно поступать
следующими двумя способами.
Способ 1. Если рассматриваемая СМО - только один из объектов обу-
чающей выборки с номером s, тогда для оценки вероятностей pij разумно
использовать соотношение
(10)
pij = p(L)sj, объект с номером s принадлежит кластеру Ai,
где L - длина отрезка временного ряда в обучающей выборке, Ai - кластер
объектов с номером i, а оценки pLsj рассчитываются по формулам (8)-(9).
Способ 2. Если рассматриваемая СМО — единственный объект обучающей
выборки, иначе говоря обучающая выборка построена по предыстории дви-
жения этой СМО в различных ее отрезках, тогда для оценки вероятностей pij
можно использовать соотношение
∑
1
(11)
pij =
p(L)sj,
pi
s∈Ai
где L - длина отрезка временного ряда в обучающей выборке, Ai - кластер
объектов с номером i, оценки pLsj рассчитываются по формулам (8)-(9), а pi -
это число объектов в кластере Ai.
Можно предложить и другие способы оценки искомых вероятностей pij
из алгоритма (2) с возможным привлечением экспертов для осуществления
экспертно-статистической обработки результатов оценивания [5].
5. Применения
Предложенная методика была применена для расчета параметров мо-
дели многоканальной системы массового обслуживания, которой описыва-
лось функционирование операционного отделения Института нейрохирургии
им. Н.А. Бурденко.
6. Заключение
Для решения задачи оценки структуры и параметров модели выбора опти-
мальной стратегии переключения каналов в управляемой системе массового
обслуживания (СМО) предложены процедуры экспертно-классификационно-
го анализа, структурного прогнозирования и экспертно-статистической обра-
ботки данных.
Предстоит сравнить различные способы представления оценок вероят-
ностных параметров задачи управления СМО через оценки, полученные ме-
тодом структурного прогнозирования.
При дальнейшем развитии предложенной модели и методов обработки и
анализа данных придется, по-видимому, использовать новые возможности,
связанные с применениями теории нейронных сетей [13].
73
СПИСОК ЛИТЕРАТУРЫ
1.
Mandel А., Laptin V. Channel Switching Threshold Strategies for Multichannel
Controllable Queuing Systems // Communicat. Comput. Inform. Sci. 2020. V. 1337.
P. 259-270. link.springer.com/chapter.
2.
Бауман Е.В., Дорофеюк А.А. Классификационный анализ данных // Труды
Междунар. конф. по проблемам управления. Том 1. М.: СИНТЕГ, 1999. С. 62-77.
3.
Дорофеюк А.А. Методология экспертно-классификационного анализа в задачах
управления и обработки сложноорганизованных данных (история и перспекти-
вы развития) // Проблемы управления. 2009. № 3.1. С. 19-28.
4.
Дорофеюк Ю.А., Чернявский А.Л Интеллектуальные методы динамического
структурного анализа данных // Датчики и системы. 2019. № 10. С. 3-8.
5.
Мандель А.С., Дорофеюк Ю.А. Экспертно-классификационная и экспертно-ста-
тистическая обработка информации и принятие решений. М.: Макс Пресс, 2010.
С. 165-168.
6.
Воронцов К.В. Десять открытых проблем вероятностного тематического моде-
лирования // Интеллектуализация обработки информации: Пленарный доклад
на 13-й Междунар. конф. ИОИ-2020.
7.
Дорофеюк A.А., Покровская И.В., Чернявский А.Л. Структуризация объектов
нечисловой природы // Информационные технологии и вычислительные систе-
мы. 2018. № 1. С. 16-21.
8.
Дорофеюк A.А., Покровская И.В., Чернявский А.Л. Экспертные методы анализа
и совершенствования систем управления // АиТ. 2004. № 10. С. 172-188.
Dorofeyuk A.A., Pokrovskaya I.V., Chernyavsky A.L. Expert Methods to Analyze
and Perfect Management Systems // Autom. Remote Control. 2004. V. 65. No. 10.
Р. 1675-1688.
9.
Дорофеюк A.А., Гольдовская М.Д., Киселева Н.Е. и др. Процедуры коллек-
тивной многовариантной экспертизы в задачах анализа и совершенствования
социально-экономических систем // Информационные технологии и вычисли-
тельные системы. 2016. № 4. С. 53-68.
10.
Трояновский В.М. Программная инженерия информационно-управляющих си-
стем в свете прикладной теории случайных процессов. М.: Издательский дом
Форум. 2019.
11.
Айзерман М.А., Браверман Э.М., Розоноэр Л.И. Метод потенциальных функций
в теории обучения машин. М.: Наука, 1970.
12.
Шибзухов З.М. Об одном робастном подходе к поиску центров кластеров //
Интеллектуализация обработки информации: Тезисы докладов 13-й Междунар.
конф. ИОИ-2020. М.: РАН, 2020. С. 121-122.
13.
Хайкин С. Нейронные сети. Полный курс. М.-СПб.: Диалектика, 2020.
Статья представлена к публикации членом редколлегии А.А. Лазаревым.
Поступила в редакцию 20.01.2021
После доработки 16.05.2021
Принята к публикации 30.06.2021
74
