Система массового обслуживания M/E₂/c с повторными вызовами

Розглянуто систему масового обслуговування типу M/E₂/c з повторними викликами, тобто багатоканальну систему з пуасонівським вхідним потоком викликів, двофазним розподілом Ерланга часу обслуговування, нескінченною експоненціальною орбітою та без втрат. Побудовано аналітичну модель системи обслуговув...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2011
Hauptverfasser:	Коба, Е.В., Пустовая, С.В.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2011
Schriftenreihe:	Проблемы управления и информатики
Schlagworte:	Методы обработки информации
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/207382
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Система массового обслуживания M/E₂/c с повторными вызовами / Е.В. Коба, С.В. Пустовая // Проблемы управления и информатики. — 2011. — № 6. — С. 103–109. — Бібліогр.: 7 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-207382
record_format	dspace
spelling	irk-123456789-2073822025-10-07T00:20:53Z Система массового обслуживания M/E₂/c с повторными вызовами Система масового обслуговування M/E₂/c з повторними викликами Retrial Queueing System M/E₂/c Коба, Е.В. Пустовая, С.В. Методы обработки информации Розглянуто систему масового обслуговування типу M/E₂/c з повторними викликами, тобто багатоканальну систему з пуасонівським вхідним потоком викликів, двофазним розподілом Ерланга часу обслуговування, нескінченною експоненціальною орбітою та без втрат. Побудовано аналітичну модель системи обслуговування типу M/E₂/c з поверненнями. Отримано чисельний розв’язок з використанням методу розріджених матриць. Показано деякі чисельні та графічні результати якісних характеристик системи. Retrial queueing system M/E₂/c has been considered, that is a multichannel system with Poisson input flow of calls, with Erlang two-phase distribution of service times, infinite exponential orbit and without losses. Analytical model of retrial queueing system M/E₂/c has been built. Numerical solution with the help of sparse matrix method has been received. Some numerical and graphical results of quality characteristics of the system are shown. 2011 Article Система массового обслуживания M/E₂/c с повторными вызовами / Е.В. Коба, С.В. Пустовая // Проблемы управления и информатики. — 2011. — № 6. — С. 103–109. — Бібліогр.: 7 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207382 519.872 10.1615/JAutomatInfScien.v43.i12.50 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Методы обработки информации Методы обработки информации
spellingShingle	Методы обработки информации Методы обработки информации Коба, Е.В. Пустовая, С.В. Система массового обслуживания M/E₂/c с повторными вызовами Проблемы управления и информатики
description	Розглянуто систему масового обслуговування типу M/E₂/c з повторними викликами, тобто багатоканальну систему з пуасонівським вхідним потоком викликів, двофазним розподілом Ерланга часу обслуговування, нескінченною експоненціальною орбітою та без втрат. Побудовано аналітичну модель системи обслуговування типу M/E₂/c з поверненнями. Отримано чисельний розв’язок з використанням методу розріджених матриць. Показано деякі чисельні та графічні результати якісних характеристик системи.
format	Article
author	Коба, Е.В. Пустовая, С.В.
author_facet	Коба, Е.В. Пустовая, С.В.
author_sort	Коба, Е.В.
title	Система массового обслуживания M/E₂/c с повторными вызовами
title_short	Система массового обслуживания M/E₂/c с повторными вызовами
title_full	Система массового обслуживания M/E₂/c с повторными вызовами
title_fullStr	Система массового обслуживания M/E₂/c с повторными вызовами
title_full_unstemmed	Система массового обслуживания M/E₂/c с повторными вызовами
title_sort	система массового обслуживания m/e₂/c с повторными вызовами
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2011
topic_facet	Методы обработки информации
url	https://nasplib.isofts.kiev.ua/handle/123456789/207382
citation_txt	Система массового обслуживания M/E₂/c с повторными вызовами / Е.В. Коба, С.В. Пустовая // Проблемы управления и информатики. — 2011. — № 6. — С. 103–109. — Бібліогр.: 7 назв. — рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT kobaev sistemamassovogoobsluživaniâme2cspovtornymivyzovami AT pustovaâsv sistemamassovogoobsluživaniâme2cspovtornymivyzovami AT kobaev sistemamasovogoobslugovuvannâme2czpovtornimiviklikami AT pustovaâsv sistemamasovogoobslugovuvannâme2czpovtornimiviklikami AT kobaev retrialqueueingsystemme2c AT pustovaâsv retrialqueueingsystemme2c
first_indexed	2025-10-07T01:12:40Z
last_indexed	2025-10-08T01:07:18Z
_version_	1845373843546308608
fulltext	© Е.В. КОБА, С.В. ПУСТОВАЯ, 2011 Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 6 103 УДК 519.872 Е.В. Коба, С.В. Пустовая СИСТЕМА МАССОВОГО ОБСЛУЖИВАНИЯ cEM // 2 C ПОВТОРНЫМИ ВЫЗОВАМИ Введение Теория массового обслуживания получила широкое распространение и раз- витие за последние 20 лет [1, 2], позволяя использовать новые математические инструменты для исследования сложных реальных систем, функционирование которых можно описать следующим образом. Если на вход системы, в которой все каналы обслуживания и места ожидания (если таковые имеются) заняты, по- ступает заявка, она покидает систему на некоторый случайный промежуток вре- мени (другими словами, идет на орбиту) и повторяет попытку получить обслужи- вание. Орбита — это виртуальная среда накопления заявок, которые не смогли получить обслуживание сразу и пытаются повторить его. Заявки, которые нахо- дятся на орбите, называют возвращениями, повторными вызовами, повторениями, или повторами. Библиографический анализ по тематике систем массового обслуживания (СМО) с возвращениями показывает, что практически все важные результаты как аналитические, так и численные, получены для экспоненциально распределенных повторных вызовов. Хотя некоторые работы, в частности [3, 4], рассматривают неэкспоненциальную орбиту. СМО с возвращениями широко применяются в проектировании и разработке телекоммуникационных и сетевых систем [3–5]. Игнорирование потока повтор- ных вызовов при исследовании реальных систем может привести к значительным ошибкам в решении инженерных задач. 1. Классификация СМО с возвращениями по Кендаллу Согласно классификации Кендалла СМО с возвращениями могут быть опи- саны как [5, 6] ,////// KHOmsBA где A и B — распределения интервалов между временами поступления вызовов в систему и временами их обслуживания соответственно, s — количество кана- лов обслуживания, m — количество мест ожидания или количество мест ожида- ния плюс количество каналов обслуживания (размер системы), O — емкость ор- биты (максимально возможное количество вызовов, которые могут находиться на орбите), H — модель с потерями (если ,NLH  то СМО без потерь), K — рас- пределение вызовов на орбите. Если четвертая позиция в нотации Кендалла для СМО с возвращениями про- пущена, предполагается, что .0m Если пропущена пятая позиция, предполага- ется, что ,O если пропущена шестая позиция, предполагается, что ,MK  т.е. времена между повторными вызовами распределены экспоненциально. Рассмотрим СМО типа cEM // 2 с повторными вызовами, т.е. многоканаль- ную систему обслуживания с входящим пуассоновским потоком входящих вызо- вов, двухфазным эрланговским распределением времен обслуживания, бесконеч- ной экспоненциально распределенной орбитой и без потерь, чтобы найти некото- рые вероятностные характеристики системы. 104 ISSN 0572-2691 2. Описание функционирования системы Рассмотрим систему функционирования СМО типа cEM // 2 с возвращени- ями (рис. 1) с c каналами обслуживания, в которую поступает пуассоновский по- ток вызовов с интенсивностью  . Если при поступлении вызова в системе есть свободный канал обслуживания, то вызов получает обслуживание немедленно и оставляет систему после его завершения. Иначе, если все каналы обслуживания заняты в момент поступления вызова, то вызов становится источником возвраще- ний (повторов). Говорят, что такие вызовы находятся на орбите. Каждый такой источник возвращений производит повторные попытки получить обслуживание через некоторые случайные промежутки времени до тех пор, пока один из кана- лов не освободится, иначе источник исчезает, а вызов получает обслуживание и затем уходит из системы. ...  Каналы 1 2 2 1 2 1 C  2 2 2 Орбита Рис. 1 Предполагается, что интервалы между успешными повторными вызовами распределены экспоненциально с параметром ν, а времена обслуживания — по двухфазному эрланговскому закону распределения с параметром  (с плотно- стью распределения вероятностей ).)2()( )2(2 xxexb  Также предполагается, что интервалы между поступлениями вызовов, времена повторов и времена об- служиваний взаимно независимы. 3. Аналитическая модель Функционирование рассматриваемой системы можно описать с помощью тривариантного процесса )),(),(),(( tYtXtZ где ),(tX )(tY — количество занятых каналов обслуживания, находящихся на первой и второй фазах в момент t соответ- ственно, ctYtX  )()( — количество занятых каналов обслуживания, )(tZ — ко- личество повторных вызовов в момент t. Согласно приведенным выше предположе- ни- ям процесс ))(),(),(( tYtXtZ марковский с множеством состояний  ...},1,0{S }....,,1,0{}...,,1,0{ cc  Определим переходные интенсивности процесса ))(),(),(( tYtXtZ за время ).,( dttt  Из состояния ),,,( jik ,0k ,,0 ci  ,,0 cj  ,cji  за время dt система может с вероятностью (рис. 2)  dt перейти в состояние ),,1,( jik  ,cji  ci  (новый первичный вы- зов поступил в систему и занял свободный канал обслуживания);  dt перейти в состояние ),,1( jik  (новый первичный вызов поступил в систему, когда все каналы обслуживания заняты, и ушел на орбиту);  k перейти в состояние ),,1,1( jik  ,cji  ,ci  0k (один из по- вторных вызовов сделал успешную попытку получить обслуживание);  i2 перейти в состояние ),1,1,(  jik ,0i cj  (один из вызовов за- кончил обслуживание на первой фазе); Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 6 105  i2 перейти в состояние ),1,,( jik 0j (один из вызовов закончил об- служивание и ушел из системы). Тогда инфинитезимальные переходные интенсивности ,),,)(,,( lnmjikq ...},,1,0{, mk ,,0,,, clnji  ,cji  cln  процесса ))(),(),(( tYtXtZ из сос- тояния ),,( jik в состояние ),,( lnm могут быть определены так (согласно рис. 2 и рис. 3): 1) cjicjcik  ,0,0,0                   иначе;0 ),,,(),,(),)(22( ),,1,1(),,(, ),1,,(),,(,2 ),1,1,(),,(,2 ),,,1(),,(, ),,1,(),,(, ))(( jiklnmkji jiklnmk jiklnmj jiklnmi jiklnm jiklnm q mnlkij (1) 2) cjicjcik  ,0,0,0                ;иначе0 ),,,(),,(),)(2( ),,1,1(),,(, ),1,,(),,(,2 ),1,1,(),,(,2 ),,,1(),,(, ))(( jiklnmkji jiklnmk jiklnmj jiklnmi jiklnm q mnlkij (2) 3) cjik  ,0,0            ;иначе0 ),,,(),,(),2( ),1,,(),,(,2 ),,,1(),,(, ))(( jiklnmj jiklnmj jiklnm q mnlkij (3) 4) 0,,0  jcik            .иначе0 ),,,(),,(),2( ),1,1,(),,(,2 ),,,1(),,(, ))(( jiklnmi jiklnmi jiklnm q mnlkij (4)   jik ,1,1  jik ,, jik ,1,  1,1,  jik 1,, jik jik ,,1 0i 0i  )1(k 0,  jci )1(2  j 0k cj  )1(2  j Рис. 3 4. Система уравнений Колмогорова для стационарных вероятностей Пусть })(,)(,)({)( jtYitXktZPtpkij  — вероятность того, что в мо- мент t система находится в состоянии ),,,( jik kijp — соответствующие стацио-   jik ,1,1  jik ,, jik ,1,  1,1,  jik 1,, jik jik ,,1 ci k cji    0 k cji  ,0 j2 0j j2 ci cji   Рис. 2 106 ISSN 0572-2691 нарные вероятности (если какой-либо индекс у kijp отрицательный, то соответ- ствующий компонент уравнения равен нулю). Эти вероятности удовлетворяют следующей системе уравнений Колмогорова: ,,0,0,)1(2)1(2 )1())(22( 1,,1,1, ,1,1,,1,1, cjicjcipjpi pkppkjip jikjik jikjikjikkij     (5) ,,0,0,)1(2 )1())(2( 1,1, ,1,1,,1,1, cjicjcipi pkppkjip jik jikjikjikkij     (6) ,2)2( 1,0,0,0,100 kkk ppkp   ,0k (7) ,2)2( 1,1,,0,10   ckckck ppcp ,0k (8) ,001000 pp  (9) ,2)2( 1,1,000  cc pcp (10) .)2( 0,1,10,1,000   ccc ppcp (11) Условие нормирования ,0 0 0 0       k c i kij c j p .cji  (12) Довольно трудно получить аналитическое решение для такой системы урав- нений. Один из методов численного решения системы уравнений (5)–(12) состоит в том, чтобы ограничить емкость орбиты довольно большой константой L [7]. То- гда система уравнений (5)–(11) будет иметь конечное количество переменных, ко- торые нужно найти. Пусть L — максимальное количество повторных вызовов на орбите (емкость орбиты). Тогда дополнительно к (5)–(11) получим ,,0,0,)1(2 )1(2))(2( 1,, 1,1,,,1,1, cjicjcipj pippLjip jiL jiLjiLjiLLij     (13) ,)2( ,,1,1, jiLjiLLij ppcp   ,0 ci  ,0 cj  ,cji  (14) ,)1(2 1,0,0,0,100 LLL pipp   ,)2( ,0,10 cLcL pcp  (15) .)2( 0,,10,1,0 cLcLLc ppcp   (16) Условие нормировки (12) станет следующим: ,0 0 0 0       L k c i kij c j p .cji  (17) Система (5)–(11), (13)–(17) имеет ограниченное количество неизвестных, по- скольку ,L таким образом СМО с возвращениями LcEM /0/// 2 будет все- гда эргодична. 5. Численное решение Система (5)–(11), (13)–(17) может быть решена стандартными вычислитель- ными процедурами на компьютере. Однако количество памяти компьютера, необ- ходимое для выделения под матрицу системы уравнений, довольно значительно Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 6 107 для некоторого большого L и c, хотя большинство элементов таких матриц нуле- вые. Поэтому предложено решить систему (13)–(17) с помощью разреженных матриц. Разреженная матрица — это матрица, у которой большинство элементов ну- левые. Методы разреженных матриц позволяют значительно уменьшить как ис- пользование памяти компьютера, так и время вычисления. Доказано, что время обработки элементов разреженной матрицы пропорционально количеству нену- левых элементов. Систему (5)–(11), (13)–(17) можно представить в матричной форме как .BPA  На рис. 4 показано визуальное отображение основной матрицы A си- стемы. Можно увидеть, что даже при малых значениях 10L и 10c количе- ство неизвестных переменных достаточно большое. На рис. 4 также показана раз- реженность основной матрицы: точки представляют собой ненулевые элементы главной матрицы системы. 0 2 4 6 7 6 5 4 3 2 1 0 Количество ненулевых элементов — 19 1,1  cL 0 200 400 600 700 600 500 400 300 200 100 0 Количество ненулевых элементов — 4375 10,10  cL Рис. 4 Таблица L B 1 0,947783573 5 0,980924289 10 0,989509608 50 0,997672271 100 0,998818438 300 0,999602074 500 0,999760748 1000 0,999880187 2000 0,999880187 108 ISSN 0572-2691 Пусть })()({lim ctYtXPB t   — вероятность того, что все каналы обслу- живания заняты (так называемая вероятность блокировки). В табл. 1 показана за- висимость вероятности блокировки B от емкости орбиты L ,10( c ,5,10  ).1 При L можно видеть, что B стремится к некоторому численному значению, т.е. вероятность блокировки урезанной системы согласовывается с ве- роятностью блокировки начальной системы (5)–(12). Также получена зависимость вероятности блокировки B от интенсивности возвращений  ,5c 1,2  (рис. 5): вероятность блокировки возрастает с увеличением интенсивности по- вторных вызовов. На рис. 6 показана зависимость вероятности блокировки вызо- вов B от интенсивности возвращений и интенсивности первичных вызовов  :)1,5( c вероятность блокировки возрастает с увеличением интенсивности первичных вызовов. 0 5 10 15 20  B 0,9993 0,9994 3 0,9995 0,9996 3 0,9997 0,9998 3 0,9999 Рис. 5 0 2 10  B 0,9992 0,9993 3 0,9994 0,9995 3 0,9996 0,9997 3 0,9998 0,9999 4 6 8 12 14 16 18 4  4 Рис. 6 Заключение Построена аналитическая модель системы массового обслуживания типа cEM // 2 с повторными вызовами. Предложено численное решение для системы уравнений, которым описывается функционирование рассматриваемой системы. Получены некоторые численные результаты. Показано, что вероятность блокиро- вания вызовов зависит от интенсивности первичных и повторных вызовов, таким образом, повторные вызовы влияют на качественные характеристики системы. С помощью таких моделей адекватно описываются телекоммуникационные системы, например call-центры, где вторичный, третичный и т.д. входящие пото- ки влияют на характеристики функционирования таких систем. Другие области использования рассмотренной системы обслуживания включают моделирование компьютерных сетей и систем, авиационные задачи и различные задачи инженер- ных систем. О.В. Коба, С.В. Пустова СИСТЕМА МАСОВОГО ОБСЛУГОВУВАННЯ cEM // 2 З ПОВТОРНИМИ ВИКЛИКАМИ Розглянуто систему масового обслуговування типу M /E2 /c з повторними ви- кликами, тобто багатоканальну систему з пуасонівським вхідним потоком ви- кликів, двофазним розподілом Ерланга часу обслуговування, нескінченною експоненціальною орбітою та без втрат. Побудовано аналітичну модель систе- ми обслуговування типу M /E2 /c з поверненнями. Отримано чисельний розв’язок з використанням методу розріджених матриць. Показано деякі чисе- льні та графічні результати якісних характеристик системи. Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 6 109 Е.V. Koba, S.V. Pustova RETRIAL QUEUEING SYSTEM cEM // 2 Retrial queueing system M /E2 /c has been considered, that is a multichannel sys- tem with Poisson input flow of calls, with Erlang two-phase distribution of service times, infinite exponential orbit and without losses. Analytical model of retrial queueing system M /E2 /c has been built. Numerical solution with the help of sparse matrix method has been received. Some numerical and graphical results of quality characteristics of the system are shown. 1. Falin G.I., Templeton J.G.C. Retrial queues. — London : Chapman and Hall, 1997. — 328 p. 2. Artalejo J.R., Gómez-Corral A. Retrial queueing systems: a computational approach. — Berlin : Springer-Verlag, 2008. — 318 p. 3. Koba E.V., Pustovaya S.V. Call center as retrial queueing system // J. of Automation and Inform. Sci. — 2007. — 39, N 5. — P. 37–47. 4. Pustova S.V. Investigation of call centers as retrial queuing systems // Cybernetics and Systems Analysis. — 2010. — 46, N 3. — P. 494–499. 5. Pustova S.V. Dependence of performance indices of a call center on the distribution of calls’ so- journ time in the orbit // Ibid. — 2009. — 45, N 2. — P. 314–325. 6. Kovalenko I.N., Koba E.V. On the classification of retrial queuing systems // Ibid. — 2010. — 46, N 3. — P. 420–425. 7. Wilkinson R.I. Theories for toll traffic engineering in the U.S.A. // The Bell System Tech. J. — 1956. — N 35. — P. 421–514. Получено 26.05.2011

Система массового обслуживания M/E₂/c с повторными вызовами

Institution

Ähnliche Einträge