نظریه صف (Queueing theory) چیست و چه کاربردی دارد؟

نظریه صف (Queueing theory) به مطالعه ریاضی یک ردیف در حال انتظار یا صف اشاره دارد.

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

نظریه صف چیست؟

نظریه صف از موضوعات مهم تحلیل سیستم‌هایی است که عملکردی مبتنی بر ورود، خروج و سرویس‌دهی دارند. این نظریه در سیستم‌های مهندسی نیز حائز اهمیت است. یکی از کاربردهای مهم آن تحلیل کارایی و ارزیابی سیستم‌های کامپیوتری است که کارها را برای انجام در سیستم صف با ورود و خروج‌های متفاوت قرار داده و سرویس‌دهی می‌کنند. با توجه به اهمیت سیستم‌های صف در تحلیل مسائل دنیای واقعی و سیستم‌های شبیه‌سازی در علوم مهندسی آشنایی با این مبحث اهمیت زیادی برای فارغ‌التحصیلان رشته‌ها کامپیوتر دارد. در نظریه صف، از مدل صف‌بندی برای تخمین وضعیت صف‌بندی واقعی سیستم استفاده می‌شود و بنابراین رفتار صف می‌تواند یک تحلیل ریاضی داشته باشد. مدل‌های صف بندی می‌توانند از نمادهایی مثل A/B/S/K/N/D استفاده کنند که در آن معانی زیر را دارند:

A: نشان‌دهنده توزیع فاصله زمانی ورود

B: نشان‌دهنده توزیع زمان سرویس

S: نشان‌دهنده تعداد سرویس دهنده‌ها

K: نشان‌دهنده ظرفیت سیستم

N: نشان‌دهنده فراخوانی جمعیت

D: نشان‌دهنده انضباط فرض شده برای سرویس

علاوه بر این، نمادهای استانداردی که برای توزیع در ارتباط با نظریه صف وجود دارند به شرح زیر هستند:

M: برای خاصیت مارکوف توزیع پواسون، توزیع نمایی (markovian)

Ek: برای توزیع ارلانگ (توزیع Erlang)

D: برای توزیع Degenerat (توزیع ثابت)

G: برای توزیع عمومی (Global)

Ph: برای توزیع نوع بار

تئوری صف از چه بخش‌هایی پدید آمده است؟

در تئوری صف، مدیریت صف از سه بخش زیر ساخته شده است:

نحوه مراجعه مشتریان.

نحوه خدمات‌رسانی به مشتریان.

شرایط خروج مشتری از سیستم.

در این زمینه مراجعات به دو زیرمجموعه زیر تقسیم می‌شوند:

ثابت: مراجعات رایجی که یک بازه زمانی ثابت میان آن‌ها وجود دارد.

متغیر: مراجعه‌ تصادفی که مرسوم‌تر است و شایع‌تری آن در صف نانوایی قابل مشاهده است.

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

مدل‌ها

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

مشخصات پارامترهایی مانند: نرخ ورود، زمان سرویس، ظرفیت صف و احتمالاً آرایش صف در سیستم.

مشخصات وضعیت سیستم: مشخص‌کننده وضعیت‌های عمومی مانند تعداد عناصر در صف و… هستند.

رسم دیاگرام انتقال حالت: این دیاگرام نشان‌دهنده زنجیره مارکوف است

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

توزیع پواسون

توزیع پواسون (Poisson distribution ‌) یک توزیع احتمالی گسسته است که احتمال اینکه یک حادثه به تعداد مشخصی در فاصله زمانی یا مکانی ثابتی رخ دهد را شرح می‌دهد؛ به شرط اینکه این حوادث با نرخ میانگین مشخصی و مستقل از زمان آخرین حادثه رخ دهند. علاوه بر این، توزیع پواسون برای تعدادی از حوادث در فاصله‌های مشخص دیگری مثل مسافت، مساحت یا حجم استفاده شود. این اثر بیشتر بر متغیرهای تصادفی خاصی تأکید می‌کند، مانند متغیر تصادفی N که تعداد ظهورها یا ورودهای گسسته را که در فاصله زمانی مشخصی اتفاق می‌افتند را می‌شمارد. توزیع پواسن در هر زمینه‌ای استفاده. به طور مثال، فرض کنید شخصی به طور متوسط چهار ایمیل در روز دریافت می‌کنید، تعداد ایمیل‌های دریافت شده در برخی از روزها می‌تواند کمتر یا بیشتر از چهار باشد، اما در بازه زمانی طولانی اگر بر دریافت ایمیل نظارت کنیم، می‌بینیم نرخ دریافت ثابت است. حال فرض کنید فرایند یا ترکیبی از چند فرایند یک جریان رویداد به صورت تصادفی تولید کنند، توزیع پواسن احتمال اینکه تعداد این رخدادها 2،3،4 و اعداد دیگر باشد را مشخص می‌کند. توزیع پواسن درجه پراکندگی اطراف نرخ متوسط وقوع رخداد را پیش‌بینی می‌کند.

زنجیره مارکوف

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

خدمات‌دهی در تئوری صف

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

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

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

برای اطلاعات بیشتر در خصوص نظریه صف به آدرس QUEUING THEORY AND PRACTICE: A SOURCE OF COMPETITIVE ADVANTAGE مراجعه کنید.