بخشی از مقاله
چکيده :
در اين تحقيق به تحليل يک مدل صف 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) اثبات قضيه را ادامه مي دهيم.
