СМО с взаимопомощью

Математическая модель СМО с взаимопомощью

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

Описание модели

На вход n-канальной СМО с m-очередью поступает простейший поток заявок с интенсивностью λ. Интенсивность простейшего потока обслуживания каждого канала μ.

Интенсивность потока обслуживания с взаимопомощью между каналами всегда равна nμ.

Если заявка застаёт все каналы свободными, она принимается на обслуживание и обслуживается всеми n-каналами одновременно, при этом производительность увеличивается в n-раз.

После окончания обслуживания все каналы освобождаются одновременно.

Если вновь прибывшая заявка застаёт в системе одну заявку, то она принимается на обслуживание: часть каналов обслуживает первую заявку, часть приступает к обслуживанию второй заявки. Разделение каналов совершенно произвольное.

Если система обслуживает k-заявок (k=1,n-1), то вновь прибывшая заявка принимается на обслуживание и все (k+1)-заявок обслуживаются n-каналами, распределёнными произвольно между заявками, но так, что все каналы заняты обслуживанием.

Попавшая на обслуживание заявка обслуживается до конца (заявки терпеливые).

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

Если система обслуживает n-заявок (k=n), то каждая из них обслуживается одним каналом, а вновь прибывшая заявка встаёт в очередь и ожидает освобождения хотя бы одного из каналов.

Если в системе имеется (n+r)-заявок (r=1,m-1), то n-заявок из них обслуживаются и r-заявок ожидают в очереди, а вновь прибывшая заявка становится в очередь. Максимальное число мест в очереди m.

Если вновь прибывшая заявка застаёт в очереди m-заявок, то она получает отказ и исключается из обслуживания.

Состояние рассмотренной системы будем связывать с числом заявок, находящихся в системе.

Граф состояний

Рассмотрим множество состояний системы:

S₀ — в системе нет ни одной заявки, все каналы свободны;

S₁ — в системе имеется одна заявка, она обслуживается всеми n-каналами;

S₂ — в системе имеется две заявки, они обслуживается n-каналами;

…;

S_k — в системе имеется k-заявок, они обслуживаются n-каналами;

…;

S_n — в системе имеется n-заявок, они обслуживаются n-каналами, очереди нет;

S_n+1 — в системе имеется (n+1)-заявок, n из них обслуживаются n-каналами, а одна заявка ожидает в очереди;

…;

S_n+r — в системе имеется (n+r)-заявок, n из них обслуживаются n-каналами, а r-заявок ожидают в очереди;

…;

S_n+m — в системе имеется (n+m)-заявок, n из них обслуживаются n-каналами, а m-заявок ожидают в очереди;

Система дифференциальных уравнений

Система дифференциальных уравнений, описывающих поведение системы, имеет вид:

${\begin{cases}p_{0}'(t)=-\lambda p_{0}(t)+n\mu p_{1}(t)\\p_{1}'(t)=\lambda p_{0}(t)-(\lambda +n\mu )p_{1}(t)+n\mu p_{2}(t)\\p_{2}'(t)=\lambda p_{1}(t)-(\lambda +n\mu )p_{2}(t)+n\mu p_{3}(t)\\\ldots \\p_{k}'(t)=\lambda p_{k-1}(t)-(\lambda +n\mu )p_{k}(t)+n\mu p_{k+1}(t)\\p_{k+1}'(t)=\lambda p_{k}(t)-(\lambda +n\mu )p_{k+1}(t)+n\mu p_{k+2}(t)\\\ldots \\p_{n}'(t)=\lambda p_{n-1}(t)-(\lambda +n\mu )p_{n}(t)+n\mu p_{n+1}(t)\\p_{n+1}'(t)=\lambda p_{n}(t)-(\lambda +n\mu )p_{n+1}(t)+n\mu p_{n+2}(t)\\\ldots \\p_{n+m-1}'(t)=\lambda p_{n+m-2}(t)-(\lambda +n\mu )p_{n+m-1}(t)+n\mu p_{n+m}(t)\\p_{n+m}'(t)=\lambda p_{n+m-1}(t)-n\mu p_{n+m}(t)\\\sum \limits _{i=0}^{n+m}p_{i}(t)=1\\p_{0}(0)=1,\ p_{1}(0)=0,\ p_{2}(0)=0,\ldots ,\ p_{n+m}(0)=0\end{cases}}$

При стационарном режиме работы системы (при t→∞).

Система уравнений принимает вид:

${\begin{cases}-\lambda p_{0}+n\mu p_{1}=0\\\lambda p_{0}-(\lambda +n\mu )p_{1}+n\mu p_{2}=0\\\lambda p_{1}-(\lambda +n\mu )p_{2}+n\mu p_{3}=0\\\ldots \\\lambda p_{k-1}-(\lambda +n\mu )p_{k}+n\mu p_{k}=0\\\lambda p_{k}-(\lambda +n\mu )p_{k+1}+n\mu p_{k+1}=0\\\ldots \\\lambda p_{n-1}-(\lambda +n\mu )p_{n}+n\mu p_{n}=0\\\lambda p_{n}-(\lambda +n\mu )p_{n+1}+n\mu p_{n+1}=0\\\ldots \\\lambda p_{n+m-2}-(\lambda +n\mu )p_{n+m-1}+n\mu p_{n+m}=0\\\lambda p_{n+m-1}-n\mu p_{n+m}=0\\\sum \limits _{i=0}^{n+m}p_{i}=1\end{cases}}$ Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \Leftrightarrow} ${\begin{cases}-\lambda p_{0}+n\mu p_{1}=0\\-\lambda p_{1}+n\mu p_{2}=0\\-\lambda p_{2}+n\mu p_{3}=0\\\ldots \\-\lambda p_{k}+n\mu p_{k+1}=0\\-\lambda p_{k+1}+n\mu p_{k+2}=0\\\ldots \\-\lambda p_{n}+n\mu p_{n+1}=0\\-\lambda p_{n+1}+n\mu p_{n+2}=0\\\ldots \\-\lambda p_{n+m-1}+n\mu p_{n+m}=0\\\lambda p_{n+m-1}-n\mu p_{n+m}=0\\\sum \limits _{i=0}^{n+m}p_{i}=1\end{cases}}$

Суммируя в системе уравнения с первого до i-го (i=1,n+m), получаем упрощённый вид системы.

Решим систему относительно p₀,p₁,…,p_n+m.

${\begin{cases}p_{1}={\frac {\lambda }{n\mu }}p_{0}\\p_{2}={\frac {\lambda }{n\mu }}p_{1}\\p_{3}={\frac {\lambda }{n\mu }}p_{2}\\\ldots \\p_{k+1}={\frac {\lambda }{n\mu }}p_{k}\\p_{k+2}={\frac {\lambda }{n\mu }}p_{k+1}\\\ldots \\p_{n+1}={\frac {\lambda }{n\mu }}p_{n}\\p_{n+2}={\frac {\lambda }{n\mu }}p_{n+1}\\\ldots \\p_{n+m-1}={\frac {\lambda }{n\mu }}p_{n+m-2}\\p_{n+m}={\frac {\lambda }{n\mu }}p_{n+m-1}\\\sum \limits _{i=0}^{n+m}p_{i}=1\end{cases}}$$\Leftrightarrow$${\begin{cases}p_{1}={\frac {\lambda }{n\mu }}p_{0}\\p_{2}=\left({\frac {\lambda }{n\mu }}\right)^{2}p_{0}\\p_{3}=\left({\frac {\lambda }{n\mu }}\right)^{3}p_{0}\\\ldots \\p_{k+1}=\left({\frac {\lambda }{n\mu }}\right)^{k+1}p_{0}\\p_{k+2}=\left({\frac {\lambda }{n\mu }}\right)^{k+2}p_{0}\\\ldots \\p_{n+1}=\left({\frac {\lambda }{n\mu }}\right)^{n+1}p_{0}\\p_{n+2}=\left({\frac {\lambda }{n\mu }}\right)^{n+2}p_{0}\\\ldots \\p_{n+m-1}=\left({\frac {\lambda }{n\mu }}\right)^{n+m-1}p_{0}\\p_{n+m}=\left({\frac {\lambda }{n\mu }}\right)^{n+m}p_{0}\\\sum \limits _{i=0}^{n+m}\left({\frac {\lambda }{n\mu }}\right)^{i}p_{0}=1\end{cases}}$ Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \Leftrightarrow} ${\begin{cases}p_{0}=\left(\sum \limits _{i=0}^{n}{\frac {\lambda ^{i}}{n^{i}\mu ^{i}}}\right)^{-1}\\p_{1}={\frac {\lambda }{n\mu }}p_{0}\\\ldots \\p_{i}={\frac {\lambda ^{i}}{n^{i}\mu ^{i}}}p_{0}\\\ldots \\p_{n+m}={\frac {\lambda ^{n+m}}{n^{n+m}\mu ^{n+m}}}p_{0}\end{cases}}$

В результате получаем решение системы: $p_{0}={\frac {1}{\sum \limits _{i=0}^{n+m}{\frac {\lambda ^{i}}{n^{i}\mu ^{i}}}}},\ p_{i}={\frac {\lambda ^{i}}{n^{i}\mu ^{i}}}p_{0},\forall i\in N_{n+m}$

Основные характеристики системы

$t_{\lambda }={\frac {1}{\lambda }},t_{\mu }={\frac {1}{\mu }},\rho ={\frac {\lambda }{\mu }},\chi ={\frac {\lambda }{n\mu }},$

$p_{0}={\frac {1}{\sum \limits _{i=0}^{n+m}{\frac {\rho ^{i}}{n^{i}}}}}={\frac {1}{1+{\frac {\rho }{n}}+{\frac {\rho ^{2}}{n^{2}}}+\ldots +{\frac {\rho ^{n+m}}{n^{n+m}}}}}={\frac {1}{\sum \limits _{i=0}^{n+m}\chi ^{i}}}={\frac {1}{1+\chi +\chi ^{2}+\ldots +\chi ^{n+m}}}={\frac {1-\chi }{1-\chi ^{n+m+1}}},p_{i}={\frac {\rho ^{i}}{n^{i}}}p_{0}=\chi ^{i}p_{0},\forall i\in N_{n+m},$

${\bar {s}}=\sum \limits _{i=0}^{n}{ip_{i}}+\sum \limits _{i=1}^{m}{np_{n+i}}=\sum \limits _{i=0}^{n}{i\chi ^{i}p_{0}}+\sum \limits _{i=1}^{m}{n\chi ^{n+i}p_{0}},{\bar {r}}=\sum \limits _{i=0}^{m}{ip_{n+i}}=\sum \limits _{i=1}^{m}{i\chi ^{n+i}p_{0}},{\bar {l}}={\bar {s}}+{\bar {r}}=\sum \limits _{i=0}^{n+m}{i\chi ^{i}p_{0}},{\bar {k}}=\sum \limits _{i=1}^{n+m}{np_{i}}=\sum \limits _{i=1}^{n+m}{n\chi ^{i}p_{0}},$

$q=1-p_{n+m}=1-{\frac {\rho ^{n+m}}{n^{n+m}}}p_{0}=1-\chi ^{n+m}p_{0},A=\lambda (1-p_{n+m})=\lambda \left(1-{\frac {\rho ^{n+m}}{n^{n+m}}}p_{0}\right)=\lambda \left(1-\chi ^{n+m}p_{0}\right),$

$p_{\text{прост.}}=p_{0},p_{\text{отк.}}=p_{n+m}={\frac {\rho ^{n+m}}{n^{n+m}}}p_{0}=\chi ^{n+m}p_{0},p_{\text{обсл.}}=1-p_{n+m}=1-{\frac {\rho ^{n+m}}{n^{n+m}}}p_{0}=1-\chi ^{n+m}p_{0},$

$p_{\text{н.загр.}}=\sum \limits _{i=0}^{n-1}p_{i}=\sum \limits _{i=0}^{n-1}{\frac {\rho ^{i}}{n^{i}}}p_{0}=\sum \limits _{i=0}^{n-1}\chi ^{i}p_{0},p_{\text{п.загр.}}=\sum \limits _{i=0}^{m}{p_{n+i}}=\sum \limits _{i=0}^{m}{\frac {\rho ^{n+i}}{n^{n+i}}}p_{0}=\sum \limits _{i=0}^{m}\chi ^{n+i}p_{0},p_{\text{н.очер.}}=\sum \limits _{i=1}^{m}{p_{n+i}}=\sum \limits _{i=1}^{m}{\frac {\rho ^{n+i}}{n^{n+i}}}p_{0}=\sum \limits _{i=1}^{m}\chi ^{n+i}p_{0},$

${\bar {t}}_{\text{н.очер.}}={\bar {t}}_{\lambda }\cdot {\frac {\sum \limits _{i=1}^{m}{p_{n+i}}}{p_{n}}}={\frac {\sum \limits _{i=1}^{m}\chi ^{i}}{\lambda }},{\bar {t}}_{\text{н.загр.}}={\bar {t}}_{n\mu }\cdot {\frac {\sum \limits _{i=0}^{n-1}{p_{i}}}{p_{n}}}={\frac {\sum \limits _{i=0}^{n-1}\chi ^{i}}{n\mu \chi ^{n}}},{\bar {t}}_{\text{п.загр.}}={\bar {t}}_{\text{н.загр.}}\cdot {\frac {p_{\text{п.загр.}}}{p_{\text{н.загр.}}}}={\frac {\sum \limits _{i=1}^{m}\chi ^{i}}{n\mu }},$

${\bar {t}}_{\text{прост.}}={\bar {t}}_{\lambda }={\frac {1}{\lambda }},{\bar {t}}_{\text{обсл.}}={\bar {t}}_{\lambda }\cdot {\bar {s}}={\frac {\bar {s}}{\lambda }},{\bar {t}}_{\text{очер.}}={\bar {t}}_{\lambda }\cdot {\bar {r}}={\frac {\bar {r}}{\lambda }},{\bar {t}}_{\text{сист.}}={\bar {t}}_{\lambda }\cdot {\bar {l}}={\frac {\bar {l}}{\lambda }}.$

При χ≠1 получаем

$p_{0}={\frac {1}{1+\chi +\chi ^{2}+\ldots +\chi ^{n+m}}}={\frac {1-\chi }{1-\chi ^{n+m+1}}},p_{i}=\chi ^{i}p_{0},\forall i\in N_{n+m},$

${\bar {s}}={\frac {1-(n+1)\chi ^{n}+n\chi ^{n+1}}{\left(1-\chi \right)\left(1-\chi ^{n+m+1}\right)}}\chi +{\frac {1-\chi ^{m}}{\left(1-\chi ^{n+m+1}\right)}}n\chi ^{n+1},{\bar {r}}={\frac {1-(m+1)\chi ^{m}+m\chi ^{m+1}}{\left(1-\chi \right)\left(1-\chi ^{n+m+1}\right)}}\chi ,{\bar {l}}={\frac {1-(n+m+1)\chi ^{n+m}+(n+m)\chi ^{n+m+1}}{\left(1-\chi \right)\left(1-\chi ^{n+m+1}\right)}}\chi ,{\bar {k}}=\rho {\frac {1-\chi ^{n+m}}{1-\chi ^{n+m+1}}},q={\frac {1-\chi ^{n+m}}{1-\chi ^{n+m+1}}},A=\lambda {\frac {1-\chi ^{n+m}}{1-\chi ^{n+m+1}}},$

$p_{\text{прост.}}={\frac {1-\chi }{1-\chi ^{n+m+1}}},p_{\text{отк.}}={\frac {1-\chi }{1-\chi ^{n+m+1}}}\chi ^{n+m},p_{\text{обсл.}}={\frac {1-\chi ^{n+m}}{1-\chi ^{n+m+1}}},p_{\text{п.загр.}}={\frac {1-\chi ^{m+1}}{1-\chi ^{n+m+1}}}\chi ^{n},p_{\text{н.загр.}}={\frac {1-\chi ^{n}}{1-\chi ^{n+m+1}}},p_{\text{н.очер.}}={\frac {1-\chi ^{m}}{1-\chi ^{n+m+1}}}\chi ^{n+1},$

${\bar {t}}_{\text{п.загр.}}={\frac {1-\chi ^{m+1}}{n\mu \left(1-\chi \right)}},{\bar {t}}_{\text{н.загр.}}={\frac {1-\chi ^{n}}{n\mu \chi ^{n}\left(1-\chi \right)}},{\bar {t}}_{\text{н.очер.}}={\frac {1-\chi ^{m}}{n\mu \left(1-\chi \right)}},$

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \bar t_\text{прост.}=\frac{1}{\lambda},\bar t_\text{обсл.}=\frac{1-(n+1)\chi^n+n\chi^{n+1}}{n\mu\left(1-\chi\right)\left(1-\chi^{n+m+1}\right)}+\frac{\chi^n\left(1-\chi^m\right)}{\mu\left(1-\chi^{n+m+1}\right)},\bar t_\text{очер.}=\frac{1-(m+1)\chi^m+m\chi^{m+1}}{n\mu\left(1-\chi\right)\left(1-\chi^{n+m+1}\right)},\bar t_\text{сист.}=\frac{1-(n+m+1)\chi^{n+m}+(n+m)\chi^{n+m+1}}{n\mu\left(1-\chi\right)\left(1-\chi^{n+m+1}\right)}.}

При χ=1 получаем

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \chi=1\Leftrightarrow \lambda=n\mu\Leftrightarrow\rho=n,}

$p_{0}=p_{1}=p_{2}=\ldots =p_{n+m}={\frac {1}{n+m+1}},$

${\bar {s}}={\frac {n(n+1)+2nm}{2(n+m+1)}},{\bar {r}}={\frac {m(m+1)}{2(n+m+1)}},{\bar {l}}={\frac {n+m}{2}},{\bar {k}}={\frac {n(n+m)}{n+m+1}},q={\frac {n+m}{n+m+1}},A=\lambda {\frac {n+m}{n+m+1}},$

$p_{\text{прост.}}={\frac {1}{n+m+1}},p_{\text{отк.}}={\frac {1}{n+m+1}},p_{\text{обсл.}}={\frac {n+m}{n+m+1}},p_{\text{н.загр.}}={\frac {n}{n+m+1}},p_{\text{п.загр.}}={\frac {m+1}{n+m+1}},p_{\text{н.очер.}}={\frac {m}{n+m+1}},$

${\bar {t}}_{\text{н.загр.}}={\frac {1}{\mu }},{\bar {t}}_{\text{п.загр.}}={\frac {m+1}{n\mu }},{\bar {t}}_{\text{н.очер.}}={\frac {m}{\lambda }},{\bar {t}}_{\text{прост.}}={\frac {1}{\lambda }},{\bar {t}}_{\text{обсл.}}={\frac {n(n+1)+2nm}{2\lambda (n+m+1)}},{\bar {t}}_{\text{очер.}}={\frac {m(m+1)}{2\lambda (n+m+1)}},{\bar {t}}_{\text{сист.}}={\frac {n+m}{2\lambda }}.$

Другие СМО

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

Литература

• Овчаров Л. А. Прикладные задачи теории массового обслуживания, «Машиностроение», М.,1969.