ریاضیات صف
در مقالهی قبل گفتیم که هرجا زمان درخواست یا تقاضای مشتریان نظمِِ زمانی ندارد، صف بهوجود میآید. و هرچه تراکم تقاضا و زمان خدمت رسانی بیشتر شود، تاخیرها بیشتر و صفها بسیار طولانی میشود. ریاضیدانها سالهاست که بهدنبال روشهایی برای بررسی صف، و طراحی الگوریتمهای کنترلِ شلوغی هستند. در ادامه با پارامترهای موثر در نظریهی صف و مقدمات این نظریه آشنا می شویم. توجه کنید که هر محیط یا فضای پُرترافیکی که با نظریهی صف قابل توضیح باشد را یک سیستم صف مینامیم.
تعداد مشتریها
تحلیل سیستمهای صف را با قضیه Little آغاز میکنیم. این قضیه میگوید که میانگین تعداد مشتریها در یک سیستم ($N$) می تواند به صورت زیر نوشته شود:
که $\lambda$ متوسط نرخ ورود مشتریان و $T$ متوسط زمانی است که یک مشتری در سیستم صرف می کند.
در این جا به یک درک شهودی از این قضیه اکتفا می کنیم. یک رستوران را در نظر بگیرید. می توانیم به این رستوران به عنوان یک نمونه برای نظریهی صف یا یک سیستم صف، نگاه کنیم: هر مشتری به محض ورود به رستوران، در صورتِ وجود میز خالی میتواند در رستوران بماند و غذا بخورد.
فرض کنید در یک روز متوسط نرخ ورود مشتریان به یک رستوران ($\lambda$) دو برابر شود در حالیکه زمان قرار گرفتن هر مشتری در آن ($T$) تغییر نکند (البته با فرض این که رستوران اشباع نشود). در این صورت تعداد مشتریانی که در هر لحظه در رستوران هستند دو برابر می شود. به همین ترتیب، اگر نرخ ورود مشتریان تغییر نکند ولی زمان قرار گرفتن هر کدام در صف دو برابر شود، باز هم در هر لحظه تعداد مشتریان حاضر در رستوران دو برابر می شود.
پارامترهای صف
برای بررسی دقیقتر هر سیستم صف، باید به پارامترهای خاص آن سیستم که بر نتیجهی عملکردش اثر میگذاراد توجه کنیم. برای مثال، عملکرد یک رستوران به عنوان یک سیستم صف به پاسخ سوالات زیر وابسته است:
آیا مانند یک رستوران معمولی، در زمان شام و نهار تعداد بیشتری مشتری می آید، و یا مثل یک قهوه خانه ورود مشتریها در طول زمان تقریباً یکنواخت است؟
مشتریان چقدر در رستوران می مانند؟ آیا هر مشتری بعد از گذشت یک زمان ثابت رستوران را ترک می کند، یا این زمان به نوع مشتری بستگی دارد؟
چند میز در رستوران برای استفاده مشتریان وجود دارد؟
این سه نکته بیانگر مهمترین مشخصههای یک سیستم صف هستند. میخواهیم این مشخصهها را به زبان ریاضی بیان کنیم:
فرآیند ورود: چون نمیدانیم هر مشتری دقیقا چهوقت از راه میرسد، می توانیم زمان ورود مشتریها را به عنوان یک فرآیندِ تصادفی در نظر بگیریم. همان طور که گفتیم، احتمال آمدن مشتری در زمانهای مختلف میتواند متفاوت باشد؛ این احتمال را میتوان بهعنوان تابعی از زمان در نظر گرفت که فرآیند ورود مشتری ها را توصیف می کند.
فرآیند خدمت: زمان خدمترسانی به یک مشتری نیز لزوماً ثابت نیست. اما با مشاهدات آماری میتوان نوع پراکندگی این مقدار را بهدست آورد. یعنی میتوان دید که بهطور میانگین هرنوع پذیرایی چقدر در یک روز تکرار میشود. میتوان زمان خدمترسانی به یک مشتری را هم بهعنوان یک متغیر تصادفی دیگر در نظر گرفت که به آن فرآیند خدمت رسانی می گویند.
تعداد سرویس دهندهها: در مثال رستوران تعداد میزها، مقدار این متغیر را مشخص میکند؛ و در یک سوپر مارکت تعداد صندوقهای پرداخت، تعداد سریسدهندههاست.
دسته بندی سیستمهای صف
هر کدام از پارامترهای صف که گفتیم، ویژگیهایی دارند که سبب میشود هر صف با صفهای دیگر فرق داشته باشد! یکی از ویژگیهای بسیار مهم که باید برای فرآیند ورود درنظر بگیریم، این است که فرض کنیم فرآیند ورود مشتریان مستقل از زمانهای گذشته است. برای مثال، این که بعدازظهر چه تعداد مشتری به یک رستوران بیایند، ارتباطی با تعداد مشتریان در قبلازظهر ندارد. یا تعداد مشتریان دیروز رستوران، اثری بر تعداد مشتریان امروز و فردا ندارد. فرآیند تصادفی پُواسون یک مدل ریاضی است که این انتظار را برآورده می کند. این فرآیند یکی از پُرکاربردترین فرآیندهای تصادفی است که تحلیلهای ریاضیِ دقیقی در مورد آن صورت گرفته است. فرآیند خدمات نیز میتواند تصادفی یا غیر تصادفی باشد. در حالت تصادفی، یکی از سادهترین مدلها توزیع نَمایی است به این معنی که احتمال اینکه فرآیند خدمات به اندازهی حداقل t طول بکشد برابر با α^t است که α عددی بین صفر و یک است. این توزیع ارتباط زیادی با فرآیند پواسون دارد و مشابه آن خواص ریاضی زیادی دارد. البته فرآیند خدمات در بسیاری از کاربردها دارای این توزیع نیست و به این وسیله تنها یک تقریب از مدل ارائه می شود.
با توجه به مشخصات فوق، سیستم های صف را می توان به دستههای مختلف تقسیم کرد:
$M/M/1$: این ساده ترین سیستم صف برای تحلیل است. در این مدل، فرآیند ورود یک فرآیند پواسون و فرآیند خدمات دارای توزیع نمایی است. هم چنین سیستم تنها یک سرویس دهنده دارد.
$M/D/n$: در این سیستم فرآیند ورود یک فرآیند پواسون است اما فرآیند خدمات غیر تصادفی است. به عنوان مثال می توان از سیستم فروش بلیط با $n$ باجه نام برد. در این مثال میتوان فرض کرد که زمان خدمات برای همهی مشتریها برابر است.
$G/G/n$: این سیستم کلیترین حالت یک سیستم صف است که در آن فرآیند ورود و فرآیند خدمات هر چیزی می توانند باشند. برای این سیستم تنها تحلیلهای کُلی مانند قضیهی Little موجود است.
