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

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

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

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

На вход 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-заявок ожидают в очереди;

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

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

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \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}}$ $\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.

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \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}}$ $\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},$

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle 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^ip_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 }},$

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \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 получаем

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle p_0=\frac{1}{1+\chi+\chi^2+\ldots+\chi^{n+m}}=\frac{1-\chi}{1-\chi^{n+m+1}},p_i=\chi^ip_0,\forall i\in N_{n+m},}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \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}},}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle 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},}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \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.