مدل صف‌بندی

درنظریه صف، از مدل صف بندی برای تخمین وضعیت صف بندی واقعی سیستم استفاده می‌شود؛ بنابراین رفتار صف می‌تواند یک آنالیز ریاضی داشته باشد. در مدل‌های صف بندی به ما اجازه می‌دهد که تصمیم‌گیری کنیم بر تعداد مفید مقیاس‌های اندازه‌گیری کارایی وضعیت ثابت که شامل: میانگین تعداد (عناصر) در صف یا سیستم میانگین زمان صرف شده در صف یا سیستم توزیع آماری تعداد (مشتریان، بسته،...) یا زمان احتمال پر یا خالی بودن صف احتمال یافتن در صف/سیسنم در وضعیت خاص این مقیاس‌های اندازه‌گیری کارایی، برای مسائل و مشکلاتی که به وسیله وضعیت صف بندی ایجاد شده‌اند بسیار مهم هستند. این مسائل و مشکلات غالبآ مرتبط است به عدم رضایت مشتریان از سرویس ارائه شده یا می‌تواند از مسائل ریشه‌ای مانند زیان‌های اقتصادی در تجارت باشد. انالیزهای مربوط به مدل‌های صف بندی به ما اجازه می‌دهد موضوعات صف بندی مختلف را برای مشخص کردن و ادغام کردن اهداف برای تغییر ارزیابی‌ها ایجاد کنیم.

مدل‌های صف بندی می‌توانند از نمادهای کندال استفاده کنند:
A/B/S/K//N/D
که در آن:

• A: نشان دهنده توزیع فاصله زمانی ورود
• B: نشان دهنده توزیع زمان سرویس
• S: نشان دهنده تعداد سرویس دهنده‌ها
• K: نشان دهنده طرفیت سیستم
• N: نشان دهنده فراخوانی جمعیت
• D: نشان دهنده انضباط فرض شده برای سرویس

در بسیاری از مواقع اعضای (مشتریان) قدیمی حذف می‌شوند؛ بنابراین نمادها عبارتنداز A/B/S و هم چنین فرض می‌کنیم ظرفیت سیستم و تعداد فراخوانی جمعیت بی‌نهایت و انضباط فرض شده برای سرویس از نوع صف (رایانه) می‌باشد.

نمادهای استاندارد

نمادهای استاندارد که برای توزیع وجود دارد عبارتنداز:

• M: برای خاصیت مارکف (توزیع پواسون، توزیع نمایی (markovian)
• Ek: برای توزیع ارلانگ (توزیع Erlang)
• D: برای توزیع Degenerat (توزیع ثابت)
• G: برای توزیع عمومی(Global)
• Ph: برای توزیع نوع بار

مدل‌ها

مدل‌های صف بندی معمولآ در ساختار و نمایش صف بندی سیستم وضعیت ثابتی دارند. به این ترتیب مدل‌های تصادفی احتمال اینکه سیستم صف بندی بتواند یک وضعیت یت پیکربندی مخصوص پیدا کند را نشان می‌دهند.
روال‌های عمومی برای ساختاربندی و آنالیز مدل‌های صف بندی عبارتنداز:

1. مشخصات پارامترهایی مانند: نرخ ورود، زمان سرویس، ظرفیت صف و احتمالآ آرایش صف در سیستم
2. مشخصات وضعیت سیستم:(مشخص‌کننده وضعیت‌های عمومی مانند تعداد مشتری‌ها و...)
3. رسم دیاگرام انتقال حالت: این دیاگرام نشان دهنده زنجیره مارکوف است
4. به دلیل اینکه دیاگرام انتقال حالت نشان دهنده وضعیت ثابت، وضعیت فعلی و وضعیت توازن می‌باشد پس می‌توانیم احتمال رفتن از یک حالت مجاور به یک حالت دیگر را محاسبه کنیم.
5. صریح بودن احتمال تمامی حالات
6. تصمیم‌گیری در رابطه با احتمال خالی بودن وضعیت بر اساس این واقعیت که مجموع تمامی احتمال‌ها برابر ۱ است.

در حالیکه مشکلات خاصی را می‌توان به وسیله مدل‌های کوچک ثابت به صورت عدد آنالیز کرد. بیشتر مدل‌های عمومی از آنالیز محاسبات استفاده می‌کنند.}

صف با یک سرویس دهنده

شاید شایع‌ترین وضعیت صف بندی که در زندگی واقعی با آن مواجه می‌شویم صف‌هایی با یک سرویس دهنده می‌باشند. در بسیاری از شرایط با یک صف تک سرویس دهنده مواجه می‌شویم، از جمله کسب و کار، صنعت، انتقال و... در نتیجه توانایی مدل‌سازی و تجزیه تحلیل یک صف تک سرویس دهنده در زمینه خاص، می‌تواند باشد.

جریان ورود و سرویس با استفاده از فرایند پواسون

مدل M/M/1 نشان دهنده این است که یک صف با یک سرویس دهنده، ظرفیت نامحدود و فراخوانی جمعیت نامحدود داریم. در حالیکه ورود هنوز بر اساس پواسون است. به این معنا که هر دو جریان بین ورود و زمان سرویس به صورت توزیع نمایی است. از آنجا که ماهیت ریاضی، توزیع آماری، تعدادی از روابط ساده است، می‌تواندبرای چندین اندازه‌گیری عملکرد بر اساس دانستن نرخ ورود و نرخ سرویس مشتق شده باشد. با توجه به مطالب بالا مدل صف بندی M/M/1 تقریبآ برای بسیاری از شرایط مناسب است

جریان ورودی پواسون و جریان سرویس عمومی

مدل M/G/1 نشان دهنده یک صف با یک سرویس دهنده، ظرفیت صف نامحدود و فداخوانی جمعیت نامحدود است. این در حالی است که فرایند ورود بر حسب پواسون است به این معنا که از نظر توزیع آماری جریان ورود بر اساس توزیع نمایی است و توزیع زمان سرویس دیگر نمایی نیست. بلکه توزیع زمان سرویس، ممکن است هر توزیع اماری عمومی را دنبال کند و نه فقط نمایی. روابط هنوز هم می‌تواند برای تعدادی از اندازه‌گیری عملکرد مشتق شده باشد اگر نرخ ورود، میانگین و واریانس نرخ سرویس مشخص باشد. با این حال این مشتقات به‌طور کلی پیچیده‌تر و دشوار است. یکی از موارد خاص M/G/1 ارئه راه حل‌های خاص با بینش بسیار گسترده برای انتخاب بهترین مدل برای موقعیت‌های خاص صف است. به همین دلیل شما اجازع مقایسه ـن راه حل‌ها با عملکرد یک مدل M/M/1 را دارید.

صف با چند سرویس دهنده

صف‌هایی با چند سرویس دهنده غالبآ برای ارتباط راه دور یا خدمات مشتری استفاده می‌شوند. هنگامیکه این مدل صف مدل‌سازی می‌شود لازم است تا اطمینان حاصل شود که صف‌های چند سرویس دهنده، شبکه‌ای از صف‌های تک سرویس دهنده نیستند. چراکه نتایج ممکن است متفاوت باشد با توجه به چگونگی رفتار مدل صف. یک بینش مشاهده با مقایسه مدل‌های صف بندی اینست که یک صف با چند سرویس دهنده از نظر کارایی از چندین صف با هر کدام با یک سرویس دهنده بهتر است. ویک استخر بزرگ از سرویس دهنده از نظر کارایی از ۲ یا چند استخر کوچک بهتر است. حتی اگر به همان تعداد در کل سیستم سرزیس دهنده وجود داشته باشد.

مثال

یک مثال ساده برای اثبات واقعیت فوق به شرح زیر است:

یک سیستم را در نظر بگیرید با ۸ خط ورودی، یک صف واحد و ۸ سرویس دهنده. خط خروجی دارای ظرفیت ۶۴KB/s است. با توجه به اینکه سرعت ورود به هر خط با نرخ ۲ بسته بر ثانیه است؛ بنابراین کل نرخ ورود ۱۶ بسته بر ثانیه است. با میانگین ۲۰۰۰ بیت در هر بسته نرخ خدمات برابر ۶۴kb/s/2000b = 32packet/sec از این رو میانگین زمان پاسخ برای این سیستم بربر ۰٫۰۶۲۵ = ۱۶–۱/۳۲

حال سیستم دوم را با ۸ صف در نظر بگیرید و با یک سرویس دهنده برای هر کدام. هر خط خروجی ظرفیتی معادل ۸kbit/s دارد. محاسبه بازده زمان پاسخ برابر ۰٫۵ = ۲–۱/۴ میانگین زمان انتظار برای صف حالت اول برابر ۰٫۰۶۲۵ در حالیکه این زمان برای صف حالت دوم برابر ۰٫۲۵ می‌باشد.
مدل M/M

این مدل نشان دهنده بی‌نهایت سرویس دهنده می‌باشد که در واقعیت عملآ با این مدل هرگز مواجه نمی‌شویم. مدل با سرزیس دهنده نامحدود یک مدل نظری مناسب برای شرایطی که شامل دخیرع‌سازی یا تآخیر از قبیل پارکینگ، انبارها و حتی انتقال است. در این مدل‌ها صف وجود ندارد. به عنوان مثال بعد از رسین هر مشتری بلافاصله سرویس دریافت می‌کند. وقتی از بعد بیرون نگاه شود به نظر می‌رسد این مدل برای به تآخیر انداختن یا ذخیره هر مشتری برای برخی از زمان هاست.

منابع

• مدل صف
• مدل صف و بعضی ارتباط‌های بنیادی، سیستم صف بندی