О системе обслуживания множественных заявок с учетом времени подготовки обслуживающего канала
Найдены условия устойчивости и эргодичности вложенной цепи Маркова, которая описывает поведение системы массового обслуживания GI/Ğ/1, где символ Ğ означает множественную заявку, с учетом предварительной подготовки обслуживания операций заявки на протяжении случайного времени. Приведен алгоритм стат...
Saved in:
| Published in: | Доповіді НАН України |
|---|---|
| Date: | 2012 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Видавничий дім "Академперіодика" НАН України
2012
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/49346 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | О системе обслуживания множественных заявок с учетом времени подготовки обслуживающего канала / О.Н. Дышлюк // Доп. НАН України. — 2012. — № 3. — С. 34-37. — Бібліогр.: 4 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860223171101196288 |
|---|---|
| author | Дышлюк, О.Н. |
| author_facet | Дышлюк, О.Н. |
| citation_txt | О системе обслуживания множественных заявок с учетом времени подготовки обслуживающего канала / О.Н. Дышлюк // Доп. НАН України. — 2012. — № 3. — С. 34-37. — Бібліогр.: 4 назв. — рос. |
| collection | DSpace DC |
| container_title | Доповіді НАН України |
| description | Найдены условия устойчивости и эргодичности вложенной цепи Маркова, которая описывает поведение системы массового обслуживания GI/Ğ/1, где символ Ğ означает множественную заявку, с учетом предварительной подготовки обслуживания операций заявки на протяжении случайного времени. Приведен алгоритм статистического моделирования системы.
Знайдено умови стійкості та ергодичності вкладеного ланцюга Маркова, який описує поведінку системи масового обслуговування GI/Ğ/1, де символ Ğ означає множинну заявку, з урахуванням попередньої підготовки обслуговування операцій заявки протягом випадкового часу. Наведено алгоритм статистичного моделювання системи.
The conditions of stability and ergodicity of the embedded Markov chain, which describes the operation of a queuing system GI/Ğ/1, where the symbol Ğ is a multiple application, with the pre-service training operations of the application for a random time being taken into account are obtained. An algorithm for the statistical modeling of the system is given.
|
| first_indexed | 2025-12-07T18:18:50Z |
| format | Article |
| fulltext |
оповiдi
НАЦIОНАЛЬНОЇ
АКАДЕМIЇ НАУК
УКРАЇНИ
3 • 2012
IНФОРМАТИКА ТА КIБЕРНЕТИКА
УДК 519.872
© 2012
О.Н. Дышлюк
О системе обслуживания множественных заявок
с учетом времени подготовки обслуживающего канала
(Представлено академиком НАН Украины И. Н. Коваленко)
Найдены условия устойчивости и эргодичности вложенной цепи Маркова, которая опи-
сывает поведение системы массового обслуживания GI/
−→
G/1, где символ
−→
G означает
множественную заявку, с учетом предварительной подготовки обслуживания опера-
ций заявки на протяжении случайного времени. Приведен алгоритм статистического
моделирования системы.
В классической теории массового обслуживания обычно заявка нуждается в обслуживании
в течение некоторого интервала времени. Между тем в ряде технических систем каждая
заявка предполагает выполнение некоторой конечной последовательности операций, разне-
сенных во времени. Такая ситуация характерна для систем обработки информации о дви-
жущихся объектах. В работах [1, 2] исследованы системы с заявками сложной структуры
(множественными заявками), которые требуют выполнения n-го числа операций; в рабо-
те [3] рассмотрена система, в которой n = 2. Такие системы мы назвали системами со
сдвоенными заявками. Можно условно считать, что обслуживание заявки состоит из вре-
мени приема сигнала от некоторого объекта и времени передачи ответного сигнала. Оба
этих времени могут сдвигаться диспетчером в некоторых пределах.
Ниже рассматривается система обслуживания с множественными заявками, где каждая
заявка состоит из случайного числа операций, имеющих случайную длительность. Интер-
валы времени, выделяемые диспетчером для различных операций, выполняются одним об-
служивающим каналом.
Автор включает в модель также такую особенность, как наличие времени подготовки
каждой операции той или иной заявки. Если tn — момент поступления n-й заявки в систему
обслуживания, то k-я операция данной заявки может начаться не ранее момента tn+Unk, где
Unk — случайные величины с конечным математическим ожиданием. Предполагается, что
случайные векторы (Un1, Un2, . . . , UnNn
) независимы и одинаково распределены, а также
что Un1 6 Un2 6 · · · 6 UnNn
.
Алгоритм работы диспетчера описывается следующим образом.
34 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2012, №3
Первая операция заявки, поступившей в начальный момент времени (t0 = 0), разме-
щается в интервале времени (U01, U01 + Y01), где через Ynk обозначим длительность k-й
операции n-й заявки.
Операции n-й заявки размещаются на оси времени после окончания операций (n− 1)-й
заявки. При этом k-я операция n-й заявки размещается после окончания (k−1)-й операции
данной заявки и в то же время после времени подготовки данной операции, т. е. момен-
та tn + Unk. Подразумевается, что диспетчеру известны величины Unk и Ynk в момент tn
поступления n-й множественной заявки.
Описание системы и основные соотношения. Рассмотрим систему массового об-
служивания, в которой входящий поток заявок — рекуррентный. Моменты поступления
заявок: tn, n > 0, где t0 = 0, tn+1 = tn +Xn, где Xn — независимые случайные величины
с функцией распределения A(x); EXn = a ∈ (0,∞). Заявка с номером n требует выпол-
нения Nn операций Onk длительностью Ynk, 1 6 k 6 Nn, соответственно. Расположение
величин Ynk на оси времени планируется диспетчером в момент tn по следующему прото-
колу. Операция Onk занимает интервал времени Γnk = (tn + Znk, tn + Znk + Ynk), где Znk
выбирается из условия:
Znk = min
(
z > Unk : Γnk
⋂
Γml = ∅, m < n либо m = n, l < k
)
,
где Unk > 0 — заданные величины.
Величину Unk можно интерпретировать как время ориентации для операции Onk: эта
операция может начаться не раньше, чем произойдет соответствующая ориентация в те-
чение времени Unk, отсчитываемого с момента tn поступления заявки. Возможны и иные
интерпретации. В любом случае Un1 6 Un2 6 · · · 6 UnNn
.
Обозначим такую систему GI/
−→
G/1, т. е. это одноканальная система массового обслу-
живания с рекуррентным входящим потоком самого общего вида, символ
−→
G означает, что
заявка множественная. Каждая операция множественной заявки требует предварительной
подготовки канала обслуживания.
Примем следующие вероятностные условия.
1. Случайные векторы (Yn1, Yn2, . . . , YnNn
;Un1, Un2, . . . , UnNn
) не зависят от входящего
потока заявок, взаимно независимы и одинаково распределены.
2. Случайные векторы Yn = Yn1 + Yn2 + · · · + YnNn
и UnNn
независимы и
b = E(Yn1 + Yn2 + · · ·+ YnNn
) 6 ∞, c = E(UnNn
) < ∞.
Введем случайную величину Wn = ZnN + Yn. Эта величина равна времени от момента tn
до того момента, когда закончится последняя операция n-й заявки.
Предельные теоремы.
Теорема 1. В принятых условиях, если, к тому же,
b
a
< 1,
последовательность (Wn) стохастически ограничена.
Теорема 2. Если, в дополнение к условиям теоремы 1, распределение
A(x) обладает плотностью и
A(x) < 1, x > 0,
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2012, №3 35
то последовательность случайных векторов (Wn) имеет предельное распределение
при n → ∞.
Доказательство теорем. Фиксируем некоторое n > 1 и допустим, что Wn−1 = w > 0.
Возможны два случая: Xn−1 + ZnN 6 w (событие A) и Xn−1 + ZnN > w (событие B). При
событии A обслуживание операций n-го требования начнется ранее момента tn−1+w, и все
они произойдут подряд, без зазора. Следовательно,
Wn = w + Yn1 + Yn2 + · · ·+ YnNn
−Xn−1. (1)
При событии B имеем
Wn 6 w + UnN + Yn1 + Yn2 + · · ·+ YnNn
. (2)
Из (1) и (2)
E(Wn −w) 6 b+ E(UnN ;B)− E(Xn−1;A).
Имеем a = E(Xn−1) = E(Xn−1;A) + E(Xn−1;B). При w → ∞ последнее слагаемое пред-
ставляет собой остаток сходящегося интеграла, откуда
−E(Xn−1;A) = −a+ o(1), при w → ∞. (3)
Аналогично
E(UnN ;B) 6 E(Xn−1 + UnN ;B) = o(1), w → ∞. (4)
Как остаток сходящегося ряда из (3) и (4)
E(Wn −Wn−1|Wn−1 = w) = b− a+ o(1), w → ∞, (5)
т. е., в силу b/a 6 1, в пределе получаем отрицательное число.
Из (1) и (2) получаем
E(Wn −Wn−1) 6 E(UnN ) + E(Yn1 + Yn2 + · · · + YnN ) 6 c+ b. (6)
На основании соотношений (5) и (6), теоремы 1 и 2 легко доказать с помощью теоремы 1
§ 20 из работы [4].
Алгоритм статистического моделирования. Обозначим через Wnk время от момен-
та tn до момента окончания k-й операции n-й заявки, если Nn > k; положим Wnk = 0 —
в противном случае. Легко доказать, что в условиях теоремы 1 существует эргодическое
среднее
Wk = lim
n→∞
1
n
(W1k +W2k + · · · +Wnk), (7)
где имеется в виду сходимость по вероятности. Следовательно, Wnk можно сколь угодно
точно аппроксимировать допредельным значением правой части (7). Так как случайные
векторы (Wn1,Wn2, . . .) образуют однородную цепь Маркова, то их можно вычислить ме-
тодом статистического моделирования. Для этого достаточно реализовать рекуррентные
соотношения, которым эти величины удовлетворяют.
36 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2012, №3
Для начальных значений (n = 0) получаем формулы:
W01 =
{
U01 + Y01, если N0 > 0,
0, если N0 = 0.
(8)
При k > 1 имеем
W0k =
{
max(W0,k−1, U0k) + Y0k, если N0 > k,
0, если N0 < k.
(9)
При n > 0 получаем следующие формулы:
Wn1 =
{
max(Wn−1,N−1 − tn + tn+1, Un1) + Yn1, если Nn > 0,
0, если Nn = 0.
(10)
Если к тому же k > 1, имеем:
Wnk =
{
max(Wn,k−1, Unk) + Ynk, если Nn > k,
0, если Nn < k.
(11)
Таким образом, формулы (8)–(11) дают возможность методом статистического модели-
рования реализовать вложенную цепь Маркова, что значительно облегчает исследование
системы GI/
−→
G/1.
1. Коба Е. В., Дышлюк О.Н. Оценка вероятности пересечения заявок сложной структуры в системах
обслуживания // Кибернетика и систем. анализ. – 2010. – № 3. – С. 175–180.
2. Коба Е. В., Дышлюк О.Н. Системы обслуживания с ограниченным последействием и потоками заявок
сложной структуры // Пробл. управления и информатики. – 2010. – № 4. – С. 123–130.
3. Дышлюк О.Н., Коба Е.В., Пустовая С. В. Исследование распределения времени ожидания в системе
обслуживания со сдвоенными заявками // Там же. – 2011. – № 4. – С. 98–107.
4. Боровков А.А. Эргодичность и устойчивость случайных процессов. – Москва: Эдиториал УРСС,
1999. – 440 с.
Поступило в редакцию 05.07.2011Национальный авиационный университет, Киев
О.М. Дишлюк
Про систему обслуговування множинних заявок з урахуванням часу
пiдготовки обслуговуючого каналу
Знайдено умови стiйкостi та ергодичностi вкладеного ланцюга Маркова, який описує пове-
дiнку системи масового обслуговування GI/
−→
G/1, де символ
−→
G означає множинну заявку,
з урахуванням попередньої пiдготовки обслуговування операцiй заявки протягом випадково-
го часу. Наведено алгоритм статистичного моделювання системи.
O.N. Dyshliuk
A system of multiple service applications with regard for the
preparation time of a service channel
The conditions of stability and ergodicity of the embedded Markov chain, which describes the opera-
tion of a queuing system GI/
−→
G/1, where the symbol
−→
G is a multiple application, with the pre-service
training operations of the application for a random time being taken into account are obtained. An
algorithm for the statistical modeling of the system is given.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2012, №3 37
|
| id | nasplib_isofts_kiev_ua-123456789-49346 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1025-6415 |
| language | Russian |
| last_indexed | 2025-12-07T18:18:50Z |
| publishDate | 2012 |
| publisher | Видавничий дім "Академперіодика" НАН України |
| record_format | dspace |
| spelling | Дышлюк, О.Н. 2013-09-16T19:42:16Z 2013-09-16T19:42:16Z 2012 О системе обслуживания множественных заявок с учетом времени подготовки обслуживающего канала / О.Н. Дышлюк // Доп. НАН України. — 2012. — № 3. — С. 34-37. — Бібліогр.: 4 назв. — рос. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/49346 519.872 Найдены условия устойчивости и эргодичности вложенной цепи Маркова, которая описывает поведение системы массового обслуживания GI/Ğ/1, где символ Ğ означает множественную заявку, с учетом предварительной подготовки обслуживания операций заявки на протяжении случайного времени. Приведен алгоритм статистического моделирования системы. Знайдено умови стійкості та ергодичності вкладеного ланцюга Маркова, який описує поведінку системи масового обслуговування GI/Ğ/1, де символ Ğ означає множинну заявку, з урахуванням попередньої підготовки обслуговування операцій заявки протягом випадкового часу. Наведено алгоритм статистичного моделювання системи. The conditions of stability and ergodicity of the embedded Markov chain, which describes the operation of a queuing system GI/Ğ/1, where the symbol Ğ is a multiple application, with the pre-service training operations of the application for a random time being taken into account are obtained. An algorithm for the statistical modeling of the system is given. ru Видавничий дім "Академперіодика" НАН України Доповіді НАН України Інформатика та кібернетика О системе обслуживания множественных заявок с учетом времени подготовки обслуживающего канала Про систему обслуговування множинних заявок з урахуванням часу підготовки обслуговуючого каналу A system of multiple service applications with regard for the preparation time of a service channel Article published earlier |
| spellingShingle | О системе обслуживания множественных заявок с учетом времени подготовки обслуживающего канала Дышлюк, О.Н. Інформатика та кібернетика |
| title | О системе обслуживания множественных заявок с учетом времени подготовки обслуживающего канала |
| title_alt | Про систему обслуговування множинних заявок з урахуванням часу підготовки обслуговуючого каналу A system of multiple service applications with regard for the preparation time of a service channel |
| title_full | О системе обслуживания множественных заявок с учетом времени подготовки обслуживающего канала |
| title_fullStr | О системе обслуживания множественных заявок с учетом времени подготовки обслуживающего канала |
| title_full_unstemmed | О системе обслуживания множественных заявок с учетом времени подготовки обслуживающего канала |
| title_short | О системе обслуживания множественных заявок с учетом времени подготовки обслуживающего канала |
| title_sort | о системе обслуживания множественных заявок с учетом времени подготовки обслуживающего канала |
| topic | Інформатика та кібернетика |
| topic_facet | Інформатика та кібернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/49346 |
| work_keys_str_mv | AT dyšlûkon osistemeobsluživaniâmnožestvennyhzaâvoksučetomvremenipodgotovkiobsluživaûŝegokanala AT dyšlûkon prosistemuobslugovuvannâmnožinnihzaâvokzurahuvannâmčasupídgotovkiobslugovuûčogokanalu AT dyšlûkon asystemofmultipleserviceapplicationswithregardforthepreparationtimeofaservicechannel |