موضوع مقاله: نظریه صف | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # نظریه صف | مقدمه: زمانی که او مدل‌هایی را برای توصیف سیستم در شرکت تبادلات تلفنی کپنهاگ که یک شرکت دانمارکی است، انجام می‌داد این نظریه شکل گرفت. | ## بخش 1: نظریه صف | مشاغل یا «مشتریان» به صف می‌رسند، احتمالاً مدتی صبر می‌کنند، مدتی پردازش می‌کنند و سپس از صف خارج می‌شوند (شکل ۱ را ببینید). از آنجا که اطلاعاتی در مورد داخل گره دارای صف وجود دارد که باید مشخص کنیم، گره دارای صف کاملاً یک جعبه سیاه خالص نیست. این صف دارای یک یا چند «سرور» است که هر کدام را می‌توان با یک کار ورودی تا زمان ترک آن جفت کرد، و پس از آن آن سرور آزاد خواهد بود که با یک کار ورودی دیگر جفت شود (شکل ۲ را ببینید). سرور c سرویس یک کار را به تازگی به پایان رسانده‌است و بنابراین منتظر برای دریافت کار ورودی بعدی خواهد بود. مدل‌های دیگری نیز وجود دارد، اما این نمونه ای است که در نوشته‌ها معمولاً دیده می‌شود. هر صندوقدار همزمان کاریک مشتری را انجام می‌دهد و از این رو مشابه یک گره دارای صف است که فقط یک سرور دارد. تنظیماتی که در صورت مشغول بودن صندوقدار هنگام ورود مشتری، مشتری فوراً آنجا را ترک خواهد کرد، به عنوان صف بدون بافر (یا بدون «منطقه انتظار» یا شرایط مشابه) شناخته می‌شود. و به یک تنظیم با منطقه انتظار برای حداکثر n مشتری، صف با بافر اندازه n گفته می‌شود. شناخت یک سیستم صف برای شناختِ یک سیستم صف، باید شش بخش را بشناسیم: الگوی ورود مشتریان (کلایِنت) الگوی روشِ خدمت‌دهندگان (سِروِرها) نظمِ صف ظرفیتِ سیستم تعدادِ کانالهای سرویس مشتری و خدمت‌دهنده در تئوری صف، مشتری واژه‌ای عام است که برای موجودیتی به‌کار می‌رود که برای دریافتِ خدمت، به سیستمی که این خدمت را فراهم می‌کند وارد می‌شود. مکانیزم یا ابزاری که این‌چنین خدمت یا خدماتی را در اختیارِ مشتری قرار می‌دهد، سِروِر یا خدمت‌دهنده نام دارد. فرایند تولد و مرگ رفتار / وضعیت یک صف واحد (که " گره صف " نیز نامیده می‌شود) را می‌توان با یک فرایند تولد-مرگ توصیف کرد، که ورود و خروج از صف را در طول تعدادی کار (که متناسب با زمینه استفاده،"مشتری"، "درخواست" یا هر تعداد چیز دیگر، گفته می‌شود) موجود در سیستم، توصیف می‌کند. ورود هر کار، تعداد k را ۱ واحد افزایش می‌دهد و خروج هر کار (کاری در حال تکمیل خدمات خود باشد) k را ۱ واحد کاهش می‌دهد (شکل ۱ را ببینید). انتقال سیستم بین k فرایندها توسط «تولد» و «مرگ» است که به ترتیب با نرخ داده‌شده توسط مقادیر مختلف λi و μi رخ می‌دهد. برای یک سیستم صف‌بندی، k تعداد کارهای موجود در سیستم (در حال سرویس‌دهی یا در حال انتظار درصورتی‌که صف دارای بافر برای کارهای در حال انتظار باشد) است. بعلاوه، برای یک صف، نرخ ورود و نرخ خروج معمولاً با توجه به تعداد کارهای موجود در صف در نظر گرفته نمی‌شود، بنابراین ما یک نرخ متوسط ورود و خروج در واحد زمان به صف را در نظر می‌گیریم. ازاین‌رو، برای یک صف، این نمودار دارای نرخ ورود λ = λ۱ , λ۲ , … , λk، و نرخ خروج µ = µ ۱ , µ ۲ , … , µ k است (شکل ۴ را ببینید).|وسط|شکل ۳. انتقال سیستم بین k فرایندها توسط «تولد» و «مرگ» است که به ترتیب با نرخ داده‌شده توسط مقادیر مختلف λi و μi رخ می‌دهد. برای یک سیستم صف‌بندی، k تعداد کارهای موجود در سیستم (در حال سرویس‌دهی یا در حال انتظار درصورتی‌که صف دارای بافر برای کارهای در حال انتظار باشد) است. بعلاوه، برای یک صف، نرخ ورود و نرخ خروج معمولاً با توجه به تعداد کارهای موجود در صف در نظر گرفته نمی‌شود، بنابراین ما یک نرخ متوسط ورود و خروج در واحد زمان به صف را در نظر می‌گیریم. ازاین‌رو، برای یک صف، این نمودار دارای نرخ ورود λ = λ1 , λ2 , … , λk، و نرخ خروج µ = µ 1 , µ 2 , … , µ k است (شکل ۴ را ببینید). انتقال سیستم بین k فرایندها توسط «تولد» و «مرگ» است که به ترتیب با نرخ داده‌شده توسط مقادیر مختلف λi و μi رخ می‌دهد. | ## بخش 2: نظریه صف | برای یک سیستم صف‌بندی، k تعداد کارهای موجود در سیستم (در حال سرویس‌دهی یا در حال انتظار درصورتی‌که صف دارای بافر برای کارهای در حال انتظار باشد) است. بعلاوه، برای یک صف، نرخ ورود و نرخ خروج معمولاً با توجه به تعداد کارهای موجود در صف در نظر گرفته نمی‌شود، بنابراین ما یک نرخ متوسط ورود و خروج در واحد زمان به صف را در نظر می‌گیریم. ازاین‌رو، برای یک صف، این نمودار دارای نرخ ورود λ = λ1 , λ2 , … , λk، و نرخ خروج µ = µ 1 , µ 2 , … , µ k است (شکل ۲ را ببینید). (در اینجا p نشان‌دهنده احتمال حالت پایدار در وضعیت n است) معادلات تعادل معادله حالت ۱ (از طریق حالت ۰): µ1P1 = λ0P0 معادله حالت ۲ (از طریق حالت ۱ و ۰): λ0P0 + µ2P2 = (λ1+ µ1)P1 معادله عمومی (بیان حالت n + 1 از طریق حالت‌های n - 1، n): از دو معادله اول داریم: با استنتاج ریاضی به فرمول زیر خواهیم رسید: از شرط: خواهیم داشت: که برای nهای بزرگتر و مساوی با ۱، به‌طور کامل احتمالات حالت پایدار موردنیاز را توصیف می‌کند. از طرفی سازمان مجبور است فضایی برای انتظار مشتریان قرار دهد (مانند اتاق انتظار). بنابراین تعداد مشتریانی که در صف منتظر دریافت خدمت هستند یا تعداد مشتریان داخل سیستم، معیاری برای ارزیابی سیستم صف محسوب می‌شوند. زمان انتظار هر مشتری در صف یا سیستم: رضایت حضور مشتری با میزان حضورش در سیستم رابطه عکس دارد به این معنی که حضور مشتری در صف، هزینه از دست دادن مشتری را به سازمان تحمیل می‌کند؛ بنابراین هزینه زمان انتظار در صف و مدت زمان دریافت سرویس، یکی از معیارهای مهم ارزیابی صف است. درصدی از زمان که سیستم به علت نبودن مشتری بیکار است: سازمان برای حضور هر خدمت دهنده در سیستم هزینه‌ای به صورت ثابت یا متغیر تخصیص می‌دهد که جزء هزینه‌های سازمان است؛ بنابراین سازمان علاقه دارد تا درصد بیکاری سرورها را به حداقل ممکن برساند. دقت کنید که اکثر سیستم‌های مورد بررسی، سیستم‌هایی تصادفی هستند و بنابراین مقادیر عددی معیارهای نام برده نیز رفتاری تصادفی دارند؛ بنابراین از ارزش انتظاری یا میانگین این معیارها، به عنوان معیار ارزیابی استفاده می‌شود. برای نشان دادن یک نمونه از علامت گذاری می‌توان صف M/M/1 را که یک مدل ساده است را استفاده کرد، که در اینجا یک سرور به مشتری‌هایی که براساس فرایند پواسون (به صورتی که مدت زمان بین ورود به صورت توزیع نمایی می‌شود) می‌رسند، خدمات دهی می‌کند و دارای مدت زمان‌های انجام سرویس به صورت توزیع نمایی شده‌اند (که M فرایند مارکوف را نشان می‌دهد). صف درجه دو ساده یک سیستم پایه و متداول صف، سیستم صف ارلانگ است که ناشی از تغییر در برخی از قوانین لیتل است. چنانچه در یک صف، نرخ ورود به آن را λ، نرخ خروج از آن را σ و نرخ سرویس دهی μ در نظر بگیریم، طول صف برابر است با: با فرض توزیع نمایی برای نرخ‌های مذکور، زمان انتظار w را می‌توان نسبت ورودی‌ها به مواردی که سرویس داده می‌شوند، دانست؛ بنابراین، نرخ بقای نمایی آن‌هایی که در طول مدت انتظار، خارج نمی‌شوند به‌صورت زیر است: معادله دوم معمولاً به‌صورت زیر بازنویسی می‌شود: این مدل دومرحله‌ای یک جعبه‌ای در اپیدمیولوژی رایج است. او شماره تلفن‌هایی که جهت تماس به مرکز تبادل (تلفن) می‌رسیدند را بوسیله فرایند پواسون مدل کرد و در سال ۱۹۱۷ صف M/D/1 و در سال ۱۹۲۰ مدل صف M/D/k را حل کرد.Kingman, J. در علامت گذاری کندال: M مخفف مارکوف(Markov) یا بدون حافظه است و به این معنی است که ورودها بر اساس فرایند پواسون انجام می‌شود. اگر تعداد مشتری‌هایی که داریم بیشتر از تعداد سرورهای ما باشد، آن وقت مشتری‌ها به صف خواهند رفت و برای سرویس‌گیری منتظر می‌شوند. 1930 این راه حل بعداً توسط الکساندر خینچین با اصطلاحات احتمالی اصلاح شد و اکنون به عنوان فرمول پولاچیک - خینچین شناخته می‌شود.Whittle, P. 1953 و علامت گذاری مدرن را برای صف‌ها معرفی کرد که اکنون به نام علامت گذاری کندال شناخته می‌شود. لئونارد کلین راک بر روی کاربرد تئوری صف روی سوئیچینگ پیام (در اوایل دهه ۱۹۶۰) و سوئیچینگ بسته (در اوایل دهه ۱۹۷۰) کار می‌کرد. سهم اولیه وی در این زمینه، پایان‌نامه دکتری وی در انستیتوی فناوری ماساچوست در سال ۱۹۶۲ بود. کارهای نظری او در اوایل دهه ۱۹۷۰ که زیربنای استفاده از سوئیچینگ بسته در ARPANET بود منتشر کرد. ترافیک سنگین / تقریب انتشار در یک سیستم با نرخ بالای اشغال (میزان استفاده نزدیک به ۱) از تقریب ترافیک سنگین می‌توان برای تقریب فرایند طول صف با حرکت براونی معکوس،فرایند Ornstein Uhlenbeck یا روند انتشار عمومی‌تر استفاده کرد. | ## بخش 3: نظریه صف | محدودیت‌های سیال مدل‌های سیال، آنالوگ‌های قطعی پیوسته شبکه‌های صف هستند که به اشیا ناهمگن اجازه می‌دهند فرایند با در نظر گرفتن محدودیت زمانی، در زمان و مکان مقیاس بندی شود. این خط مقیاس به یک معادله قطعی همگرا می‌شود که اجازه می‌دهد ثبات سیستم اثبات شود. مشخص‌شده‌است که یک شبکه صف می‌تواند پایدار باشد، اما دارای محدودیت‌های سیال ناپایدار باشد. آخرین ورودی / اولین خروجی (LIFO) این اصل همچنین بیان می‌کند که مشتریان به‌طور هم‌زمان سرویس دهی می‌شوند اما برای مشتری با کمترین زمان انتظار ابتدا خدمات ارائه می‌شود. صف‌های اولویت دار می‌توانند دو نوع باشند، غیر پیشگیرانه (کار در زمان انجام خدمت نمی‌تواند قطع شود) و پیشگیرانه (در صورتی که یک کار در حال خدمت‌گیری است می‌تواند توسط یک کار با اولویت بالاتر قطع شود). اول کوتاهترین کار پیشگیرانه کار بعدی که باید خدمت گیرد کاری با کوچک‌ترین اندازه اصلی است کوتاهترین زمان پردازش باقی مانده کار بعدی که باید خدمت گیرد کاری با کمترین نیاز پردازش باقی مانده‌است. ۱)امکانات خدماتی سرور منفرد: مشتریان در صف قرار می‌گیرند و فقط یک سرور وجود دارد چندین سرور موازی - یک صف: مشتریان در صف قرار می‌گیرند و چندین سرور نیز وجود دارد چندین سرور - چند صف: تعداد زیادی شمارنده وجود دارد و مشتریان می‌توانند تصمیم بگیرند که به کجا صف بروند ۲)رفتار مشتری در انتظار طفره رفتن: مشتریان تصمیم می‌گیرند اگر صف طولانی باشد به صف ملحق نشوند. فریب دادن: اگر مشتریان فکر کنند با این کار سریعتر به آنها سرویس داده می‌شود، بین صف‌ها جابجا می‌شوند. ورود مشتریانی که به آنها سرویس داده نشده‌است (یا به دلیل صف نداشتن حافظه، یا به دلیل امتناع مشتری) نیز به عنوان از قلم افتادگی شناخته می‌شوند و میانگین نرخ از قلم افتادگی پارامتر قابل توجهی برای توصیف یک صف است. شبکه‌های صف بندی شبکه‌های صف به سیستم‌هایی گفته می‌شود که در آن تعدادی از صف‌ها توسط آنچه که به عنوان مسیریابی مشتری شناخته می‌شود متصل می‌شوند. وقتی مشتری در یک گره سرویس دهی می‌شود، می‌تواند به یک‌گره و صف دیگری برای سرویس‌گیری ملحق شود، یا شبکه را ترک کند. برای شبکه‌هایی متشکل از m گره وضعیت سیستم را می‌توان با یک بردار m بعدی (x1, x2, … , xm) توصیف کرد که در آن xi تعداد مشتریان در هر گره را نشان می‌دهد. اولین نتایج قابل توجه در این حوزه شبکه‌های جکسون بود، که یک توزیع ثابت از فرم محصول کارآمد وجود دارد. تجزیه و تحلیل مقدار میانگین به معیارهای میانگین مانند زمان تولید و زمان اقامت اجازه می‌دهد تا محاسبه شود. اگر تعداد کل مشتریان در شبکه ثابت بماند، شبکه یک شبکه بسته نامیده می‌شود و همچنین که یک توزیع ثابت از محصول در قضیه گوردون-نیول نشان داده شده‌است. این نتیجه به شبکه BCMPتعمیم داده شد که در آن یک شبکه با زمان سرویس دهی عمومی، رژیم‌ها و مسیر یابی مشتریان یک توزیع ثابت محصول را نشان می‌دهند. ثابت نرمال سازی را می‌توان با الگوریتم بوزن Buzen، پیشنهاد شده در سال ۱۹۷۳، محاسبه کرد. شبکه‌های کلی (Kelly) که در آن مشتریان طبقات مختلف سطوح اولویت متفاوتی را در گره‌های خدماتی مختلف تجربه می‌کنند بعنوان شبکه‌های مشتریان مورد بررسی قرار گرفته‌است. نوع دیگری از شبکه‌ها، شبکه‌های G هستند که برای نخستین بار توسط ارول گلنبه Erol Gelenbe در سال ۱۹۹۳ پیشنهاد شد: این شبکه‌ها توزیع زمان نمایی شبیه شبکه کلاسیک جکسون ندارند. الگوریتم‌های مسیریابی در شبکه‌های زمانی گسسته که در آن محدودیت وجود دارد که گره‌های سرویس می‌توانند در هر زمان فعال باشند، الگوریتم زمان‌بندی حداکثر وزن، یک سیاست خدماتی را انتخاب می‌کند تا بتواند توان عملیاتی مطلوب در شرایطی که برای هر کار فقط از یک گره خدمات شخصی ارائه دهد. | ## جمع‌بندی | یک برنامه‌ریز شبکه باید یک الگوریتم صف بندی را انتخاب کند، که بر ویژگی‌های شبکه‌های بزرگتر تأثیر بگذارد محدودیت‌های میدانی میانگین مدلهای میدانی میانگین، محدودیت رفتار اندازه‌گیری تجربی (نسبت صف در حالت‌های مختلف) را در نظر می‌گیرند زیرا تعداد صفها (بیشتر از m) به سمت بی‌نهایت می‌رود.