%\input amsppt.sty
%\documentstyle{amsppt}
%\nopagenumbers
\magnification=\magstep2
%\pagewidth{17 true cm}
%\vcorrection{-.5 true cm}
%\hcorrection{-.5 true cm}
\TagsOnRight
\pretitle{ \centerline{\bf { Научные труды ИвГУ. Математика. Вып.~2}}
\centerline{\bf {Иваново, 1999}}

\noindent --------------------------------------------------------------------------------------------------
\vskip .1 cm
УДК 519.872
\vskip 0.2 cm
\centerline {\bf Е.~М.~Гинзбург}
\vskip 0.2 cm
%\leftheadtext{\it Е.~М.~Гинзбург  }
%\rightheadtext{\it Быстрое движение пpибоpов}
\topmatter
\title{\bf\noindent
 Быстрое движение приборов в поллинговой системе с управлением.
 Выбор оптимального значения.
%\footnote"*"{}
}\endtitle
\abstract \nofrills
\vskip 0.2 cm\noindent
 Рассмотрена поллинговая система с двумя типами приборов. Приборы первого типа
 обслуживают требования, приборы второго типа осуществляют управление,
 зависящее от состояния системы, не допуская больших скоплений приборов первого
 типа. Найдено значение управляющего параметра, позволяющее минимизировать
 вероятность потери требования при быстром движении приборов.

\endabstract
\endtopmatter
%\footnote""{* Работа выполнена пpи финансовой поддеpжке
%РФФИ (пpоект 96-01-01092). }
\document
\pageno=1
\vskip .5 cm
\centerline{\bf 1. Описание системы}
\vskip .1 cm
Эта статья продолжает цикл работ,  посвященных исследованию \break поллинговых
систем,  в которых обслуживание состоит в перевозке  требований  из  одного
узла в другой,  а приборы  передвигаются,    только  если  они  обслуживают
требования.

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

В работах [1, 2] было показано,  что системы  такого  типа  никогда  не
бывают эргодичными.    Это  можно  объяснить  тем,    что  ресурсы  системы
используются малоэффективно: в некоторых узлах скапливаются большие очереди
из приборов,  что ведет к их простою,   в  то  время  как  в  других  узлах
накапливаются большие очереди из требований.

В этой работе мы дополнительно вводим приборы второго типа, которые будем
называть  перевозчиками  (приборы  первого  типа  по-преж\-не\-му  будем
называть просто приборами).  Перевозчик забирает один прибор из очереди,  в
которой есть хотя бы $l$ приборов, и доставляет  его  в  другой  узел.   Он
оставляет прибор в узле, только если там находятся менее $l$ приборов,  иначе
он едет с ним в другой узел.  Так они реализуют управление,   зависящее  от
текущего  состояния  системы.    Далее  $l$  мы  будем  называть  управляющим
параметром.

Рассмотрим простейшую симметричную систему с потерями.  Поступившее в
узел требование покидает систему без обслуживания,  если в  очереди  уже
есть  $k$  требований. В сети  находятся  $rN$  приборов  и  $sN$ перевозчиков,
первоначально они распределены по узлам равномерно.  В каждый  из $N$  узлов
поступает пуассоновский  поток  требований  интенсивности $\lambda$. Требования
 и
перевозчики выбирают свои узлы назначения равновероятно,  времена  движения
приборов  и  перевозчиков   имеют    экспоненциальное    распределение    с
параметром $\mu$. Потоки требований, время движения и выбор узлов назначения
независимы в совокупности.

При произвольном конечном $N$ анализ  сети  практически  невозможен  из-за
возникающей зависимости между узлами  (поток  приходящих  в  узел  приборов
зависит от состояния всех узлов сети).  Мы будем  рассматривать  предельную
(при $N\to\infty$) систему. Можно доказать (это тема отдельной  статьи), что цепь
Маркова,  описывающая  поведение  такой  системы,    сходится  к  некоторой
динамической системе.

Марковскую цепь определим так.  Будем говорить,  что если в узле есть $j$
приборов, то он находится в состоянии $j$, если же в узле есть $j$  ожидающих
требований, то он находится в состоянии $-j$. Пусть $p_i^N$ -- доля узлов в
состоянии $i$, $u_j^N=\sum_{i\geq j}^m p_i^N$, а $x^N$ -- доля
перевозчиков, двигающихся с приборами.  Тогда однородная цепь
Маркова $\sum_N=(x^N,\ u_{-k}^N,\ u_{-k+1}^N,\,\dots)$ при $N\to\infty$ сходится
к  динамической  системе $(x,\ u_{-k},\ u_{-k+1},\,\dots)$, которая  описывается
системой уравнений:
%\pagebreak
$$
%\noindent
{{dx(t)}\over {dt}}=\mu u_l(t)-\mu x(t),
%\hskip 7 cm
\eqno(1)
$$
\noindent
$$
\multline
{{du_j(t)}\over {dt}}=-(\lambda+\mu rv(t)+\mu sx(t))u_j(t)
+(\mu rv(t)+
$$ $$
+\mu sx(t))u_{j-1}(t)+\lambda u_{j+1}(t),
\endmultline
\eqno(2)
$$
\hskip 7 cm $j= -k+1,\,\dots,\,l-1,$
\noindent
$$
\multline
{{du_l(t)}\over {dt}}=-(\lambda+\mu rv(t)+\mu s)u_l(t)+
$$ $$
+(\mu rv(t)+\mu sx(t))u_{l-1}(t)+(\lambda+\mu s(1-x(t)))u_{l+1}(t),
\endmultline
\eqno(3)
$$
\noindent
$$
\multline
{{du_j(t)}\over {dt}}=-(\lambda+\mu rv(t)+\mu s(1-x(t)))u_j(t)
+\mu rv(t)u_{j-1}(t)+
$$ $$
+(\lambda+\mu s(1-x(t)))u_{j+1}(t),
\endmultline
\eqno(4)
$$
\hskip 7 cm $j= l+1,\,\dots,\,m,$

\noindent
где
$$ v(t)=1- {{sx(t)}\over {r}}- {{1}\over {r}} \sum_{j=1}^m u_j(t)$$ (это аналог
доли приборов,  передвигающихся самостоятельно),  с краевым
условием  $u_{-k}(t)=1$ для всех $t \geq 0$.
\vskip .3 cm
\centerline{\bf 2. Оптимизация}
\vskip .1 cm
   Теперь найдем  такое  значение  управляющего  параметра  $l$,  чтобы
вероятность потери требования в стационарном режиме  была минимальной.
Перейдя к новым переменным $p_j= u_j-u_{j+1}$, найдем неподвижную точку
системы (1) -- (4)  (в этом разделе для удобства введено $q= \mu s/ \lambda$ ):


$$
&p_{-k}(\delta)={{(1+q- \delta )}\over {(1- \delta )}}{1+q-
\delta -q \delta ^{l+k}}, \eqno(5)
$$ $$
&p_{-k+j} (\delta)=\delta ^jp_{-k}
 \text{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ для } j=0,\,
\dots ,\,k+l-1, \eqno(6)
$$ $$
&p_{l+j} (\delta)=\delta ^{l+k}
{{(\delta -\beta (\delta))^j}\over {(1+q-\beta (\delta ))^{j+1}}}p_{-k}
\text{\ \ \ для } j=0,1,\,\dots , \eqno(7)\\
$$
где
$$\beta (\delta )={{q \delta ^{l+k}(1-\delta )}\over {1+q-\delta -
 q\delta ^{l+k}}},
$$
а значение $\delta $   определяется из условия
$$
 \sum_{j=1}^{\infty} jp_j=r-{{\lambda}\over {\mu}}\delta . \eqno(8)
$$
Используя формулы (5) -- (7), можно получить явный вид функции,  стоящей в
левой части уравнения (8).  Из-за сложности этого выражения  анализ  корней
уравнения (8) при произвольно выбранных параметрах практически  невозможен.
Однако, устремляя некоторые из них к нулю или бесконечности, можно получать
асимптотические разложения корней  уравнения  (8), а  затем  и  функций
$p_{-k}(\delta )$.
Нехватка места не позволяет подробно обсудить все результаты,  полученные в
этой области. Здесь мы остановимся на случае $\lambda / \mu \to 0$,
считая  значения  $r,s$  и  $k$
фиксированными,  что соответствует либо быстрому движению приборов,    либо
редкому приходу требований.  В этом случае вероятность потери требования  в
системе с управлением стремится к нулю,  в  то  время  как  в  системе  без
управления она стремится к ненулевому значению $P_0$.

    Обозначим через $P_0(l)$ вероятность потери требования в динамической
системе  с управляющим параметром $l,P_0(l)=p_{-k}(\delta )$, где $p_{-k}$
определено в (5), а $\delta$ - корень уравнения (8).
Под эффективностью управления с уровнем $l$ будем  понимать  величину
$\varepsilon (l)={{P_0-P_0(l)}\over {P_0}}$. Чем ближе $\varepsilon (l)$
к единице,
тем больший выигрыш дает введение приборов второго  типа.
Мы найдем значение $l_0 = arg min \left\{P_0(l)\right\}_{l=1}^{\infty}$  и
исследуем
$\varepsilon (l_0)$.

    Чтобы компактно сформулировать основной результат,  определим функции
$\langle x \rangle$ и $x_Z$ числа $x$ :
$$
\langle x \rangle = \cases{
 \{x\},& $x \notin {\bf Z}$,\cr
  1, &$x\in{\bf Z}$},
$$

$$
x_Z = \cases{
 [x], &$x \notin {\bf Z}$,\cr
 x-1, &$x \in \text{\bf Z}$
}.
$$

Здесь, как обычно, $\{x\}$  и $[x]$ обозначают
дробную и целую части
\break
числа $x$  .

{\bf Теоpема 1} При $\lambda / \mu \to 0$ $\varepsilon(l_0) \to 1$
 и выполняется:

     1. Если $r=1$ и $k=0$, то $l_0 =2$; если же $k>0$, то $l_0=1;$

     2. Если $s<\langle r \rangle$ и
$$
\left(
{{1+s}\over {\langle r \rangle}}
 \right)^{r_Z+k}
 >{{1+s}\over {(s+1-\langle r \rangle)
(\langle r \rangle-s)}},\ то \ l_0=r_Z.
$$
Иначе $l_0=r_Z+1$.


 \underbar {\bf Доказательство} опирается на две леммы.

 {\bf  Лемма 1} Для корня $\delta$ уравнения (8) при $\lambda /\mu \to 0$
   справедливо:

  1. При $l<r-s$ $\delta =q+1-{{1}\over {r-s-l}}+o(1)$;

  2. При $l=r-s$ $\delta =q-\sqrt{{q}\over {s+1}}+o({{1}\over {q^{1/2}}})$;

  3. При $r-s<l<r+1$ $\delta ={{r-l+1}\over {s+1}}q+o(q)$;

  4. При $l=r+1$ $\delta =\sqrt{{q}\over {s+1}}+o({{1}\over {q^{1/2}}})$;

  5. При $l>r+1$ $\delta =\xi _l+o(1)$,
  где $\xi _l$ -- корень уравнения
$$
1-l\delta ^{l-1}+(l-1)\delta ^l=r(\delta ^{l+k}-1)(\delta -1)/
     \delta ^{k+1} \text{.}
$$

 {\bf Лемма 2} Для величины $P_0(l)$ при $\lambda /\mu \to 0$ справедливо:

  1. При $l<r-s$ $P_0(l)={{1}\over {(r-s-l)q^{l+k}}}+o\left({{1}\over {q^{l+k}}}\right)$;

  2. При $l=r-s$ $P_0(l)={{1}\over {\sqrt{s+1}}}{{1}\over {q^{l+k-1/2}}}+o\left({{1}\over {q^{l+k-1/2}}}\right)$;

  3. При $r-s<l<r+1$ $P_0(l)={{l-r+s}\over {s+1}}\left({{s+1}\over {r-l+1}}\right)^
    {l+k-1}{{1}\over {q^{l+k-1}}}+o\left({{1}\over {q^{l+k-1}}}\right)$;


  4. При $l=r+1$ $P_0(l)=\sqrt{{s+1}\over {q}}^{r+k}+o\left({{1}\over
           {\sqrt{q^{r+k}}}}\right)$;

  5. При $l>r+1$ $P_0(l)={{1-\xi _l}\over {1-\xi _l^{l+k}}}+o(1)$,
где $\xi _l$ -- корень уравнения
$$
1-l\delta ^{l-1}+(l-1)\delta ^l=r(\delta ^{l+k}-1)(\delta -1)/
    \delta ^{k+1} \text{.}
$$

Исследовав асимптотики леммы 2, получим утверждение теоремы.

    Результаты леммы 2    позволяют    указать    две     особенности
последовательности $\left\{P_0(l)\right\}_{l=1}^{\infty}$. Во-первых,
 реальная величина $l_0$ совпадает с  указанной  в теореме только при очень
 маленьких  значениях $\lambda /\mu$ , в то время как  сами
асимптотические  формулы  дают  хорошие  приближения  для  гораздо  б\'ольших
значений $\lambda /\mu$. Во-вторых,  при некотором  наборе  параметров
$\lambda ,\mu ,r,s$ и $k$ последовательность $\left\{P_0(l)\right\}_{l=1}^{\infty}$
может иметь более одного локального минимума.  Эти две особенности отражены
в таблице. В ней жирным шрифтом выделены оптимальное значение
$l_0$, указанное в теореме, и минимальные значения вероятностей, полученные при
конечных  значениях $\lambda /\mu$. Нижняя строка соответствует системе  без
управления.

\vskip .2 cm
\centerline {\bf Зависимость вероятности потери требования от
уровня $l$}
\centerline {\bf для разных значений $\lambda/\mu (r=9.5, s=1, k=0)$.}

$$
\matrix{
 l\qquad & \lambda /\mu =0.2 & \lambda /\mu =2\cdot 10^{-3} & \lambda /\mu =10^{-5} \cr
 &&&\cr
 7\qquad & 3.63\cdot 10^{-6} & 8.47\cdot 10^{-20} & 6.67\cdot 10^{-36} \cr
  8\qquad & {\boldkey 2.\boldkey 2\boldkey 2\cdot \boldkey 1
     \boldkey 0^{-\boldkey 6}} &  {\boldkey 5
     . \boldkey 1\boldkey0 \cdot \boldkey 1\boldkey 0^{-
     \boldkey 2 \boldkey 2}} & 2.00\cdot 10^{-40} \cr
  9\qquad & 5.67\cdot 10^{-6} & 6.58\cdot 10^{-22} & 2.50\cdot 10^{-40} \cr
  10\qquad & 8.01\cdot 10^{-5} & 8.75\cdot 10^{-20} &
     {\boldkey 1.\boldkey 9\boldkey 6\cdot \boldkey 1\boldkey 0^{-\boldkey 4
     \boldkey 0}} \cr
  11\qquad & 1.11\cdot 10^{-3} & 1.30\cdot 10^{-5} & 1.13\cdot 10^{-5} \cr
   - & 0.097 & 0.095 & 0.095 \cr
}
$$

\vskip -.3 cm
Автор выражает глубокую благодарность научному руководителю профессору
Л. Г. Афанасьевой за постановку задачи и постоянное внимание к работе.

\vskip 0.5 cm
\centerline{\bf Список использованной литеpатуpы}
\vskip .3 cm
\noindent
1. {\it Afanassieva L.~G.,  Delcoigne F.,  Fayolle G.}  On polling systems  where
\break
\phantom{ны}
servers wait for customers: Rapport de recherche \No~3058// INRIA. Paris,
\break
\phantom{ны}1996. Dec.

\noindent
2. {\it Afanassieva L.~G.,  Fayolle G.,  Popov S.~Yu.} Models  for  transportation
\break
\phantom{ны}
networks// J. of Math. Science. 1997. Vol.~4, \No~3. P.~1092 - 1103.
\end
