فرایند ورود مارکوف

از ویکی‌پدیا، دانشنامهٔ آزاد
(تغییرمسیر از فرآیند ورود مارکوف)
پرش به: ناوبری، جستجو

در نظریه صف ، برای مدل کردن ورود مشتریان به صف از فرایند ورود مارکوف استفاده می شود.

فرایند پواسون، فرایند ورود مارکوف و فرایند ورود دسته ای مارکوف برخی از رایج ترین ها محسوب می شوند.

سابقه[ویرایش]

فرایندهای ورودی مارکوف دارای دو فرایند است . فرایند مارکوف در زمان پیوسته j(t) ، فرایند های مارکوف که توسط یک مولد یا ماتریس تغییرات Q تولید می شود. فرایند دیگر یک فرایند شمارنده است N(t) ، که دارای فضای حالت \mathbb{N}_{0}:=\mathbb{N}\cup\{0\} (که در آن \mathbb{N} مجموعه ای از تمام اعداد طبیعی)

که هر زمان N(t) افزایش می بابد و یک گذار j(t)  وجود داشته و علامتگذاری شده است .

فرایند پواسون[ویرایش]

فرایند ورود پواسون یا فرایند پواسون تعداد ورودی ها را می شمارد به طوری که هریک از آنها دارای توزیع نمایی بین ورود می باشد . در حالت کلی این مورد با ماتریس تغییرات نشان داده است ،


Q=\left[\begin{matrix}
-\lambda_{0}&\lambda_{0}&0&0&\dots\\
0&-\lambda_{1}&\lambda_{1}&0&\dots\\
0&0&-\lambda_{2}&\lambda_{2}&\dots\\
\vdots & \vdots & \ddots & \ddots & \ddots
\end{matrix}\right]\; .

در حالت همگن ساده تر هم می شود.


Q=\left[\begin{matrix}
-\lambda&\lambda&0&0&\dots\\
0&-\lambda&\lambda&0&\dots\\
0&0&-\lambda&\lambda&\dots\\
\vdots & \vdots & \ddots & \ddots & \ddots
\end{matrix}\right]\; .

در اینجا هر حالت گذار مشخص شده است .

فرایندهای ورود مارکوف[ویرایش]

فرایند ورود مارکوف (MAP) یک تعمیم از فرایند پواسون با توزیع غیر نمایی موقت بین ورودی ها است. در وضعیت همگن ، ماتریس تغییرات بصورت زیر است ،


Q=\left[\begin{matrix}
D_{0}&D_{1}&0&0&\dots\\
0&D_{0}&D_{1}&0&\dots\\
0&0&D_{0}&D_{1}&\dots\\
\vdots & \vdots & \ddots & \ddots & \ddots
\end{matrix}\right]\; .

ورود در زمان گذار رخ می هد و باعث افزایش سطح (گذار مشخص شده ) می شود بعنوان مثال در تغییر حالت درزیر ماتریس D_{1} . در زیر ماتریس های D_{0} و D_{1} با عناصر \lambda_{i,j} و تغییرات فرایند پواسون ،


0\leq [D_{1}]_{i,j}<\infty

0\leq [D_{0}]_{i,j}<\infty\;\;\;\; i\neq j

[D_{0}]_{i,i}<0\;

و


(D_{0}+D_{1})\boldsymbol{1}=\boldsymbol{0}

چندین مورد خاص در فرایند ورود مارکوف وجود دارد.

فرایندهای پوآسون با مدوله مارکوف[ویرایش]

فرایندهای پوآسون با مدوله مارکوف و یا MMPP که m بوسیله فرایندهای پواسون تغییر می کند . در صورتی که هر یک از فرایندهای پواسون m دارای تغییرات \lambda_{i} و فرایند اساسی تولید شده بوسیله یک ماتریس مولد m\times m باشد.، سپس در MAP نمایش داده می شود،

D_{1} = \operatorname{diag}\{\lambda_{1},\dots,\lambda_{m}\}

ماتریس قطری در تغییرات پواسون است و

D_{0}=R-D_{1}

فرایندهای نوسازی از نوع فاز[ویرایش]

فرایندهای نوسازی از نوع فاز یک فرایند ورود مارکوف با توزیع موقتی از نوع فاز بین ورودی است . بطور مثال اگر یک فرایند ورودی بین دو ورود که زمان توزیع PH (\boldsymbol{\alpha},S) با یک بردار خروجی نشان داده شد \boldsymbol{S}^{0}=-S\boldsymbol{1} ، فرایند ورودی یک ماتریس مولد دارد ،


Q=\left[\begin{matrix}
S&\boldsymbol{S}^{0}\boldsymbol{\alpha}&0&0&\dots\\
0&S&\boldsymbol{S}^{0}\boldsymbol{\alpha}&0&\dots\\
0&0&S&\boldsymbol{S}^{0}\boldsymbol{\alpha}&\dots\\
\vdots&\vdots&\ddots&\ddots&\ddots\\
\end{matrix}\right]

فرایند ورود دسته ای مارکوف[ویرایش]

فرایند ورود دسته ای مارکوف (BMAP) یک فرایند ورود مارکوف دارای ورودی ها بزرگتر از یک است . در وضعیت همگن ، ماتریس تغییرات بصورت زیر است ،


Q=\left[\begin{matrix}
D_{0}&D_{1}&D_{2}&D_{3}&\dots\\
0&D_{0}&D_{1}&D_{2}&\dots\\
0&0&D_{0}&D_{1}&\dots\\
\vdots & \vdots & \ddots & \ddots & \ddots
\end{matrix}\right]\; .

یک ورودی با اندازه k هر زمان رخ می دهد که گذار اتفاق می افتد . زیر ماتریس D_{k} دارای عناصر \lambda_{i,j} است و تغییرات فرایند پواسون :


0\leq [D_{k}]_{i,j}<\infty\;\;\;\; 1\leq k

0\leq [D_{0}]_{i,j}<\infty\;\;\;\; i\neq j

[D_{0}]_{i,i}<0\;

و


\sum^{\infty}_{k=0}D_{k}\boldsymbol{1}=\boldsymbol{0}

منابع[ویرایش]

  • Søren Asmussen (2000). Matrix-analytic Models and their Analysis، Scandinavian Journal of Statistics 27(2)، 193–226.
  • David M. Lucantoni (1993). The BMAP/G/1 Queue: A Tutorial، Lecture Notes in Computer Science: Performance Evaluation of Computer and Communication Systems (Editors: Lorenzo Donatiello and Randolph Nelson)، volume 729.
  • Srinivas R. Chakravarthy (2001). The batch Markovian arrival process: A review and future work. In Advances in Probability and Stochastic Processes، Ed. A. Krishnamoorthy، N.Raju and V. Ramaswami، Notable Publications، Inc.، New Jersey، USA، 21-49.
  • Srinivas R. Chakravarthy (2010). Markovian Arrival Processes. Wiley Encyclopedia of Operations Research and Management Science. Published Online: 15 JUN 2010.
  • Marcel F. Neuts (1992). Models based on the Markovian arrival process. IEICE Transactions on Communications، E75B، 1255-1265.