چکیده :
در این تحقیق به تحلیل یک مدل صف M/M/1 با سرویس دهی دروازه ای به ترتیب تصادفی خواهیم پرداخت. در این نوع سرویس دهی یک اتاق انتظار و یک صف سرویس برای مشتریان وجود دارد. هرگاه صف سرویس خالی شود تمامی مشتریان منتظر در اتاق، فوراً و بصورت تصادفی در صف سرویس قرار می گیرند.
خواهیم دید که تعداد مشتریان در اتاق انتظار و صف سرویس دارای توزیع پیوسته ثابت هستند.بنابراین می توان تبدیل دو متغیره Laplace –Stieltjes را از توزیع پیوسته زمانهای اقامت مشتریان در اتاق انتظار و صف سرویس بدست آورد.
1. مقدمه :
ما در این مقاله به بررسی مدل صف M/M/1 با سرویس دهی دروازه ای به ترتیب تصادفی می پردازیم. در این نوع سرویس دهی ، مشتریان در یک اتاق انتظار، بدون ترتیب، جمع می شوند تا به محض آنکه صف خالی شد بصورت تصادفی در صف قرار می گیرند.
این مدل موقعیت مخابره با دسترسی چندگانه در شبکه های کابلی را به یاد می آورد. شبکه های کابلی هم اکنون به منظور نقل وانتقال اطلاعات بصورت دوطرفه ارتقاء داده شده اند. سیستم با اضافه کردن یک کانال پیشرفته به کانال قدیمی که در حال حاضر وجود دارد، گسترش یافته است. بسیاری از ایستگاهها از این کانال پیشرفته بصورت مشترک استفاده می کنند به گونه ای که برای انتقال اطلاعات نیاز به جداسازی محتویات وجود دارد. یک راه مؤثر برای انتقال اطلاعات از طریق کانال پیشرفته استفاده از مکانیزم request–grant می باشد. هر ایستگاه باید از طریق انشعابات محتویات با سایر ایستگاهها هماهنگی اطلاعات داشته باشد. بعد از آنکه تقاضا بصورت موفقیت آمیز برآورده شد،جریا ن داده ها به شیارهای ذخیره شده می روند که این محتویات برای هر ایستگاه به صورت جداگانه می باشد.
دو نوع مکانیزم جداسازی محتوا در انشعابات محتویات وجود دارد : دسترسی بصورت آزاد و دسترسی بصورت بلاک شده . ویژگیهای اساسی نوع دسترسی بلاک شده عبارتند از :
• تقاضاهای در حال رقابت در یک انشعاب، بصورت تصادفی(بدون ترتیب) انشعاب را ترک می کنند.
• اگر تقاضاهای جدید به هنگامی برسندکه تقاضایی درحال ارسال می باشد باید صبر کند تا انشعاب حاضر آزاد گردد.
همین دو ویژگی منجر شده است که ما به مطالعه مدل صف با سرویس دهی دروازه ای که ترتیب سرویس دهی آن تصادفی است، بپردازیم. در اینجا مشتریان در صف بیان کننده تقاضاهایی هستند که در حال حاضر در یک انشعاب در حال رقابت هستند.
اخیراً کاربردی از این مدل بوسیله BOXMA در کتاب DENTENEER and RESING به منظور تسهیل تعمیرات در مدل تعمیر ماشین آلات که نحوه سرویس دهی آن بدون ترتیب می باشد، مورد مطالعه قرار گرفته است. در این کتاب تقریبی برای واریانس زمان اقامت در محل تعمیر با فرض اینکه منابع، محدود هستند ، بدست آمده است.
برای بدست آوردن توزیع زمانهای اقامت مشتری در اتاق انتظار و صف سرویس ابتدا به بررسی فرآیند مارکوف دو متغیره می پردازیم.سپس با بکارگیری یک روش تصحیح برای مسئله صفی که توسط ADAN ارئه شده است درمی یابیم که این فرآیند مارکوف دوبعدی دارای توزیع ثابت می باشد.
پیش از این ALI و NEUTS (1984) یک مدل صف با دو مرحله انتظار را مورد مطالعه قرار داده بودند. تفاوت اساسی بین مدلهای ALI و NEUTS ، BOXMA و COHENو مدل ذکر شده در اینجا آنست که مدت زمان انتقال مشتری از اتاق انتظار به صف سرویس(T) در مدلهای فوق الذکر بزرگتر از صفر می باشد در حالیکه در مدل ما این مدت زمان صفر می باشد. بنابراین این ویژگی که مشتریان بعد از انتقال بصورت تصادفی در صف سرویس قرار می گیرند در مدلهای ALI و NEUTS ، BOXMA وCOHEN وجود ندارد.
در ادامه مقاله روش تشریح شده در بالا دنبال شده است. در بخش 2 جزئیات مدل تحت بررسی مورد تشریح خواهد شد. بعد از آن در بخش 3 اثبات خواهیم کرد که تعداد مشتریان در اتاق انتظار و صف سرویس دارای توزیع پیوسته ثابت می باشد. در بخش 4 یک نتیجه جانبی از اینکه تعداد مشتریان در اتاق انتظار توزیع ثابت دارند (با فرض اینکه تعدادکل مشتریان در اتاق انتظار و صف سرویس برابر N باشد) را خواهیم دید. نهایتاً در بخش 5 به ارائه نتایج حاصل از توزیع پیوسته ثابت زمانهای اقامت مشتریان در اتاق انتظار و صف سرویس، می پردازیم.
2. شرح مدل :
مشتریان بصورت فرآیند پواسون با نرخ λ وارد سیستمی می شوندکه یک سرور دارد. مدت زمان سرویس مشتریان از توزیع نمایی با پارامتر µ پیروی می کند. فرض می کنیم که 1 > µ/λ = ρ . مکان انتظار قبل از سرویس دهی شامل دو بخش می باشد : یک اتاق که مشتریان بدون ترتیب در آن منتظر می باشند و یک صف سرویس که مشتریان بترتیب در آن قرار دارند.مشتری در بدو ورود وارد اتاق انتظار می شود. هر زمان صف سرویس خالی شود، همه مشتریان حاضر در اتاق انتظار فوراً از اتاق انتظار به صف سرویس منتقل می شوند. آنها بترتیب تصادفی در این صف قرار می گیرند و براساس ترتیب قرار گیری آنها در صف، سرویس دهی به آنها صورت می گیرد. اگر در لحظه ای که صف سرویس خالی می شود هیچ مشتری در اتاق انتظار وجود نداشته باشد، سرور صبر می کند تا مشتری بعدی برسد. پس از آن فوراً این مشتری به صف سرویس منتقل شده و سرویس دهی به آن آغاز می گردد.
به عبارت دیگر صف سرویس نمی تواند خالی باشد مگر آنکه اتاق انتظار خالی باشد.در حقیقت نحوه سرویس دهی در این روش به این صورت است که ابتدا مشتریان در پشت یک در و در اتاق انتظار صبر می کنند و بعد از آن بصورت تصادفی در یک صف بترتیب قرار می گیرند.این روش به نام « سرویس دهی دروازه ای با ترتیب تصادفی » خوانده می شود.
تعداد مشتریان در اتاق انتظار در زمان t بوسیله X1(t) و تعداد مشتریان در صف سرویس ( که شامل مشتری در حال سرویس می باشد) در زمان t بوسیله X2(t)نمایش داده می شود. واضح است که فرآیند تصادفی
{(X1(t), X2(t)) : t ≥ 0} یک فرآیند مارکوف دوبعدی می باشد. بخش بعدی به محاسبه احتمالات حالت ثابت این فرآیند مارکوف اختصاص داده شده است.
خاطر نشان می شود که زوج دوتایی (X1, X2) متغیرهای تصادفی هستند که دارای توزیع پیوسته بوده و بوسیله احتمالات(k,n) π معین می شوند. همچنین X1+ X2دارای همان توزیع در یک صف معمولی M/M/1 با تعداد مشتری ثابت و نحوه سرویس دهی FCFS می باشد. به عبارت دیگر :
3. احتمالات حالت ثابت ((k,n) π ) :
معادلات مربوط به احتمالات حالت ثابت در زیر آورده شده اند :
قضیه بعدی بیان می کند که احتمالات (k,n) π بوسیله مجموع نامتناهی از ترکیبات حاصلضرب بدست می آید.
قضیه 1 : توزیع احتمال منحصربفردی که معادلات بالا را توسط آن می توان حل کرد عبارت است از :
که در آن :
و همچنین داریم :
اثبات قضیه 1 : با توجه به رابطه (1 ) واضح است که : ρ0,0)=1 – ) π . علاوه براین با جایگذاری رابطه (2) در رابطه (3) داریم :
از آنجائیکه ما به دنبال محاسبه احتمالات (k,n) π , k≥0 , n≥1 و برآورده ساختن روابط (4) و (5) و(8) هستیم باید داشته باشیم :
به منظور بدست آوردن این احتمالات از یک روش تصحیح برای مسئله صف طرح شده توسط ADAN در سال 1991 استفاده می کنیم. در این روش سعی می شود که معادلات بوسیله یک ترکیب خطی از عباراتی که در هم ضرب شده اند، حل شوند. به منظور تحقق این امر ابتدا باید ترکیباتی(راه حلی) که رابطه (5) را برآورده می سازند، تعیین گردند . سپس از این راه حل برای ساخت یک ترکیب خطی که رابطه (4) را برآورده می سازد استفاده کرد.
این ترکیبات شامل عوامل غیر قابل شمارش بسیاری هستند. بنابراین برای انتخاب عوامل مناسب نیاز به یک دستورالعمل داریم. این دستورالعمل بر پایه منطق تصحیح می باشد : بعد از مشخص شدن اولین مورد ، عوامل دیگری به منظور تصحیح خطاهای ایجاد شده در معادلات اضافه می شوند. در نهایت ملاحظه می کنید که روابط (4) و (5) برآورده می شوند و در نتیجه معادله (8) هم به صورت اتوماتیک برقرار خواهد شد زیرا که این معادلات به هم وابسته اند.
با توجه به مطالب فوق الذکر ما ابتدا در به دنبال حلی بشکل n-1β kα برای برآورده سازی رابطه (5) به ازای تمامی مقادیرk و n هستیم. با جایگزینی این عبارت در (5) و مخرج مشترک گرفتن :
از آنجائیکه مجبور هستیم جواب معادله را به نرمال تبدیل کنیم باید 1 > |α| و 1 > |β| باشند. نقاط در کنار منحنی شکل (10) که به صورت یک ناحیه پیوسته می باشند در حقیقت عبارات جواب معادله (5) هستند.
سپس یک ترکیب خطی از این عبارات حاصلضربی که در رابطه (4) صدق می کنند ، می سازیم. ما با عبارت ابتداییc1α1kβ1n-1 که در آن 0 = 1β و 0 = α1 و )= ρ/(ρ+1)1β g( = α1 و c1یک مقدار ثابت است .
رابطه (4) را می توان بصورت زیر نوشت :
اگر عبارت c1α1kβ1n-1 را در معادله (4) قرار دهیم داریم : c1α1n = 0
بنابراین عبارت c1α1kβ1n-1 نمی تواند معادله(4) را برآورده سازد و برای تصحیح این خطا باید عبارت دومی را به معادله اضافه کنیم به طوری که در سمت چپ مقدار c1α1n بدست آید. این بدان معناست که ما باید عبارت
c2α2kβ2n-1 متناظر با زوج(β , α ) بر منحنی (10) اضافه کنیم به طوری که به ازای همه مقادیر n≥2 داشته باشیم :
که از آن می توان نتیجه گرفت :
البته بوسیله اضافه کردن عبارت c2α2kβ2n-1 عبارت اضافی c2α2n را در سمت راست معادله (11) خواهیم داشت. بنابراین عبارت سوم c3α3kβ3k را برای تصحیح این خطا اضافه می کنیم. به صورت مشابه نتایج زیر حاصل می شود :
با ادامه دادن این روش عبارت اضافی cmαmkβmk را که در آن αm و βm و cm همانند روابط پیشین بصورت زیر تعیین می گردند، اضافه می گردد :
حال اگر ما بتوانیم ثابت کنیم که :
الف) هنگامی که →m عبارت خطای cmαmn به سمت صفر میل می کند.
ب)سری همگراست و
هردو معادله (4) و (5) برآورده خواهند شد.(الف) و (ب) بصورت مستقیم با توجه به عبارات زیر حاصل می شوند :
نهایتاً مقدار ثابت c1 از معادله (9) بدست می آید :
در اثبات قضیه ذکر شده باید نکات زیر را مدنظر قرار داد.
نکته اول : انتخاب مقدار اولیه= 0 1β بسیار مهم است.برای مثال اگر عبارت اولیه c1α1kβ1n-1 به شرطρ > 1β> 0
ما تمایل نداریم که فقط عبارت c1α1n را در سمت راست و همچنین عبارت1β1k d را سمت چپ بدست آوریم.
ا ز طرفی دیگر نمی خواهیم که مجبور باشیم یک عبارت را برای تصحیح خطای c1α1n و یک عبارت دیگر را برای تصحیح خطای 1β1k d به معادله اضافه کنیم. با ادامه دادن این روش به یک جمع ناهمگرا (واگرا) دست
خواهیم یافت، مگر آنکه به بازای مقادیری از m داشته باشیم : (g○…○g) = β1
نکته دوم : در قضیه 1 برای j > 0 داریم :
نکته سوم : با توجه به قضیه 1 توزیع حاشیه ای X1 و X2 بصورت زیر می باشد :
و
نکته چهارم : قضیه 1 را می توان بوسیله استفاده از توابع مولد نیز اثبات کرد. اگر قرار دهیم :
از رابطه (4) ، (5) و (8) داریم :
اگر قرار دهیم :
و با جایگزینی y = f(x) در رابطه (12) ، سمت چپ آن برابر صفر می شود. با استفاده از Q(x,y) به شرط اینکه |x|≤1 , |y|≤1 می توانیم نتیجه بگیریم که به ازای y=f(x) سمت راست (12) نیز برابر صفر می باشد و بنابراین :
با تکرار این تساوی می توان یک عبارت که بصورت مجموع نامتناهی می باشد را برای Q(x,y) بدست آورد. بعد از جایگزینی این عبارت در (12) و استفاده از نتایج قضیه 1 می توان یک عبارت مشخص را برای Q(x,y) تعیین کرد.
4. تفکیک بین مشتریان اتاق انتظار و صف سرویس :
در قضیه 1 بخش قبلی احتمالات حالت ثابت (k,n) π را بصورت مجموع نامتناهی از عبارات ضربی بدست آوردیم. با وجود اینکه اگر ρ به یک نزدیک نباشد این عبارات همگرا هستند اما اگر کسی بخواهد به طور مثال مقادیر(0,100) π ،(50,50) π و(99,1) π را بررسی کند این مجموع نامتناهی سودمند نخواهند بود. در این بخش از نتایج بخش قبلی برای آگاهی بیشتر از نحوه تفکیک بین مشتریان اتاق انتظار و صف سرویس هنگامی که تعداد کل مشتریان زیاد باشد، استفاده می کنیم . فرمولهایی را بدست می آوریم که به ازای مقادیر نزدیک به یک ρ همگراست.
این فرمولها دارای رفتار نوسانی جالب توجهی هستند که به ازای مقادیر کوچک ρ نمایانگر می باشد. فرض کنید PN(k) احتمال وجود k مشتری در اتاق انتظار و تعداد کل مشتریان N باشد. در این صورت :
از آنجائیکه ، PN(k) از رتبه 1/N خواهد بود. اگر N PN(k) به شرط آنکه k/N=ξ
هنگامی که N→ ∞ دارای حد معین باشد دیگر نیازی به تمامی نتایج بخش قبلی برای بدست آوردن این حد
نداریم . به عبارت دیگر اگر فرض کنیم :
با نرمال سازی :
و سپس به کارگیری رابطه (5) برای Nهای بزرگ
(ρ+1)f(ξ) = (1- 1/N)-1f( ( 1- 1/N )-1(ξ-1/N) ) + ρ( 1+ 1/N )-1f(ξ(1+ 1/N)-1)
با بکارگیری بسط تیلور برای مراتب 1/N معادلات دیفرانسیل زیر بدست می آید:
که جواب نرمال شده زیر را در بر دارد:
از سوی دیگر برای برقراری معادله (4) باید :
بسط سری تیلور برای 1/N دارای کمترین مرتبه f(0) = ρf(1) می باشد که بوسیله تابع f رابطه (13) حاصل
می شود. اما اولین مرتبه f(1) + f΄(1) = -f(0) بوسیله این تابع برقرار نمی شود و آنچه بدست خواهد آمد
f(1) + f΄(1) = f(0)/ρ2 می باشد. بنابراین تابع f در تمامی معادلات مربوطه صدق کند. این بدان معناست که NPN([Nξ]) وقتی N→ ∞ دارای حد نیست . این موضوع بصورت قضیه زیر بیان شده است.
قضیه 2 : توزیعNPN([Nξ]) به ازای مقادیر بزرگ N هنگامی که k/N مقدار ثابت ξ را داشته باشد به صورت زیر است:
که در آن fN ~gN و یا limN→∞(fN/gN) = 1
اثبات قضیه 2 : با بکارگیری فرمولهای موجود برای (k,N-k) π داریم :
به ازای k = 0,…,N-2 و ξ = k/N (بنابراین0 ≤ ξ < 1 ) .به ازای k<N-1 داریم s0N-k-1=0 . همچنین :
نحوه عملکرد N را با استفاده از روشهای به کار گرفته شده در ضمیمه کتاب JANSSEN و DE JONG (2000) می توان بدست آورد.هنگامی که هر دو عدد N وk بزرگ باشند، با فرضξ = k/N (ξ عدد ثابت) ، عباراتی که در روابط (15) و (16) بین براکتهای مجذور هستند به یک میل می کنند. بنابراین به ازای مقادیر بزرگ m ، m ρ نقش کمی را در مقدار کلی زیگما دارد. با لگاریتم گیری و بسط تیلور برای m ρ حول 0 =m ρ و به توان نمایی رساندن، نتایج زیر حاصل می گردند :
با تعریف K = N(1-ρ)(1-ξ(1-ρ)) و ضرب و تقسیم عبارت فوق بر K داریم :
این عبارت برای PN(N-1) نیز (علاوه بر مقادیر بزرگN ) معتبر است.( با قرار دادن = 1 ξ و K=Nρ(1-ρ) )
از آنجائیکه :
بنابراین خطای ایجاد شده بصورت نمایی کاهش می یابد. در حقیقت محدوده زیگما بستن برروی m می تواند به
کل اعداد صحیح با خطای قابل اغماض گسترش یابد. با توجه به اینکه برای m ≤ 0 و 0 < ρ < 1 ، ρm ≥ 1
می باشد بنابراین حاصل زیگما با افزایش K به سرعت کاهش می یابد.فقط مقادیر بزرگ m ( m→∞ ) در محاسبه مجموعی که برروی K بسته می شود نقش دارد. با تعریف t = -ln(ρ) > 0 و s = ln(K) خواهیم داشت :
همانطور که مشاهده می کنید عبارت سمت راست تابعی متناوب از s با دوره تناوب t می باشد بنابراین آن را
می توان به صورت یک سری فوریه نوشت :
که در آن :
با جایگزینی این عبارت aq(t) در رابطه (19) و استفاده از روابط (17) و (18) اثبات قضیه را ادامه می دهیم.
با توجه به خاصیت بازتابی معروف تابع گاما
دامنه نوسانات ||aq(t) در ضرایب فوریه به صورت نمایی توسط عامل نمایی exp(-π|q|/t) کاهش می یابد. بنابراین به منظور بدست آوردن جواب عددی دقیق برای مقادیر کوچک ρ یا به عبارت دیگر مقادیر بزرگ t، عبارات بیشتری مورد نیاز می باشد. برای مقادیر نزدیک به یک ρ یا مقادیر کوچک t تعداد کمی عبارت مورد نیاز است. دامنه تغییر عبارات نوسانی در سمت رابطه (14) بستگی به |q| ، ρ و ξ دارد و این مقادیر نیز به مقدار N وابسته هستند.
5. توزیع زمان اقامت :
فرض کنید S1 و S2 بترتیب زمان اقامت مشتری (به صورت ثابت) در اتاق انتظار و صف سرویس باشد. می خواهیم تبدیل دو متغیره Laplace –Stieltjes را برای این زمانهای اقامت ثابت بدست آوریم:
قضیه 3 : تبدیل دومتغیره Laplace –Stieltjes { } از رابطه زیر حاصل
می شود :
اثبات قضیه 3 : براساس خاصیت PASTA یک مشتری به هنگام ورود با احتمال (k,n) π در وضعیت (k,n) سیستم قرار می گیرد. اگر (k,n) = (0,0) مشتری فوراً سرویس در یافت می کند. اگر (k,n) ≠ (0,0) ابتدا مشتری مجبور است در اتاق انتظار صبر کند در حالیکه n مشتری در صف سرویس هستند. اگر در طول این زمان، r مشتری دیگر وارد شوند، مشتری مورد نظر ما با احتمال ( k+1+r )-1 ، نفر ℓ ام صف سرویس خواهد بود.
بنابراین می توان نوشت :
حال با استفاده از فرمولهای :
و همچنین :
با جایگذاری در فرمول بالا خواهیم داشت :
که در آن :
با جمع بستن بر روی k و r و استفاده از فرمول زیر :
می توان نتیجه گرفت :
بنابراین قضیه به اثبات رسید.
با جایگزینی u = 0 و = 0υ در رابطه (20) و استفاده از :
داریم :
و همچنین :
نکته پنجم : زمان اقامت در اتاق انتظار (که بزرگتر از صفر می باشد) و زمان اقامت در صف سرویس برابر ترکیب هندسی بدست آمده می باشد.
دو لحظه ابتداییS1 (زمان اقامت در اتاق انتظار) و S2 (زمان اقامت در صف سرویس ) را در نظر بگیرید. قرار
می دهیم : S = S1 + S2 .با توجه به رابطه (24) برای لحظه S2 داریم :
فرمت این مقاله به صورت Word و با قابلیت ویرایش میباشد
تعداد صفحات این مقاله 15 صفحه
پس از پرداخت ، میتوانید مقاله را به صورت انلاین دانلود کنید
دانلود مقاله مدل صف M/M/1 با سرویس دهی دروازه ای به ترتیب تصادفی -صنایع
