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

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

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

سابقه

فرایندهای ورودی مارکوف دارای دو فرایند است . فرایند مارکوف در زمان پیوسته $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 _{k=0}^{\infty }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.