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

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

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

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

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

Интенсивность простейшего потока обслуживания каждого канала μ.

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

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

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

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

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

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

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

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

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

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

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

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

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

…;

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

…;

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

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

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

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

Невозможно разобрать выражение (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-1}'(t)=\lambda p_{n-2}(t)-(\lambda+n\mu)p_{n-1}(t)+n\mu p_{n}(t) \\ p_{n}'(t)=\lambda p_{n-1}(t)-n\mu p_{n}(t) \\ \sum\limits_{i=0}^{n}p_i(t)=1 \\ p_0(0)=1, \ p_1(0)=0, \ p_2(0)=0,\ldots, \ p_{n}(0)=0 \end{cases}}

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

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

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \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-2}-(\lambda+n\mu)p_{n-1}+n\mu p_{n}=0 \\ \lambda p_{n-1}-n\mu p_{n}=0 \\ \sum\limits_{i=0}^{n}p_i=1 \end{cases}} Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \Leftrightarrow} Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \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-1}+n\mu p_n=0 \\ \lambda p_{n-1}-n\mu p_{n}=0 \\ \sum\limits_{i=0}^{n}p_i=1 \end{cases}}

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

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

Невозможно разобрать выражение (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-2} \\ p_n=\frac{\lambda}{n\mu}p_{n-1} \\ \sum\limits_{i=0}^{n}p_i=1 \end{cases}} Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \Leftrightarrow} Невозможно разобрать выражение (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=\left(\frac{\lambda}{n\mu}\right)^2p_0 \\ p_3=\left(\frac{\lambda}{n\mu}\right)^3p_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=\left(\frac{\lambda}{n\mu}\right)^n p_0 \\ \sum\limits_{i=0}^{n}\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} Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \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=\frac{\lambda^n}{n^n\mu^n}p_0 \end{cases}}

В результате получаем решение системы: Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle p_0=\frac{1}{\sum\limits_{i=0}^{n}\frac{\lambda^i}{n^i\mu^i}}, \ p_i=\frac{\lambda^i}{n^i\mu^i} p_0 , \forall i\in N_n}

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

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

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

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \bar s={\sum\limits_{i=0}^{n}{ip_i}}={\sum\limits_{i=0}^{n}{i\chi^ip_0}}, \bar r=0, \bar l=\bar s, \bar k={\sum\limits_{i=1}^{n}{np_i}}={\sum\limits_{i=1}^{n}{n\chi^ip_0}},}

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

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

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

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle p_\text{н.очер.}=0, p_\text{1зан.}=\frac{\bar k}{n}=\sum\limits_{i=1}^np_i=1-p_0,p_\text{1прост.}=1-\frac{\bar k}{n}=p_0, }

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

Невозможно разобрать выражение (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{очер.}=0, \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}=\frac{1-\chi}{1-\chi^{n+1}},p_i=\chi^ip_0,\forall i\in N_n,}

Невозможно разобрать выражение (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+1}\right)}\chi,\bar r=0,\bar l=\frac{1-(n+1)\chi^n+n\chi^{n+1}}{\left(1-\chi\right)\left(1-\chi^{n+1}\right)}\chi,}

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

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

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

Невозможно разобрать выражение (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{обсл.}= \frac{1-(n+1)\chi^n+n\chi^{n+1}}{n\mu\left(1-\chi\right)\left(1-\chi^{n+1}\right)},\bar t_\text{очер.}=0,\bar t_\text{сист.}=\bar t_\text{обсл.}+\bar t_\text{очер.}= \frac{1-(n+1)\chi^n+n\chi^{n+1}}{n\mu\left(1-\chi\right)\left(1-\chi^{n+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,}

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

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \bar s=\frac{n}{2},\bar r=0,\bar l=\frac{n}{2},\bar k=\frac{n^2}{n+1}, q=1-p_n=\frac{n}{n+1}, A=\lambda\frac{n}{n+1},}

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

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

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

Другие СМО

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

Литература

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