بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
رویکرد جدید برای تجزیه و تحلیل سیستم های صف با زمان سرویس قابل انعطاف پذیر با استفاده از درخت تصمیم گیری فازی
چکیده
کنترل درخت تصمیم گیری فازی صف یک روش جدید برای کنترل هزینه سیسـتم، تعـدادی از مشـتریان در حـال انتظـار در صف و بسیاری از جنبه های دیگر از صف است. در این مقاله یک روش جدید برای تجزیـه و تحلیـل سیسـتم هـای صـف بـا زمان سرویس قابل انعطاف پذیر با استفاده از درخت تصمیم گیری فازی ارائه شده که برای کنترل هزینه سیسـتم، تعـدادی از مشتریان در حال انتظار در صف و بسیاری از جنبه های دیگر از صف است. این روش برای کاهش هزینـه هـا سیسـتم پیشـنهاد می شود. تمام قوانین ریاضیات فازی دراین مقاله زاده اصل توسعه، مفهوم ممدانی، امکان ومفهوم احتمال است. در پایان ایـن مقاله مثال ساده عددی ارائه شده است.
واژگان کلیدی: سیستمهای صف، زمان سرویس قابل انعطاف پذیر، درخت تصمیم گیری فازی، سیستم فازی
1
مقدمه
موسسات تولیدی و خدماتی برای تصمیم گیری بهینه در جهت کاهش زمان انتظار مشتریان خو د میبایست از نظریههـای صف بهرهگیری نمایند، تا نه تنها سطح منابع لازم برای سرمایه گذاری را مشخص نمایند، بلکـه تـا آنجـا کـه امکـان دارد رضایت مشتری را تامین نمایند. این موضوع بویژه برای ادامه حیات اقتصادی شرکتهـا درشـرایط کـاملاً رقـابتی اهمیـت ویژهای دارد. لذا تحقیق در زمینه توصیف عملکرد سیستمهای صف در شرایط محیطی مختلف امـری ضـروری محسـوب میگردد.
تئوری صف یکی از قدیمی ترین و توسعه یافته ترین تکنیک های تجزیه و تحلیـل مـی باشـد کـه همـه روزه در خطـوط انتظار مورد استفاده قرار می گیرد [1]. تلاش عمده تمامی موسسات تولیدی و خدماتی کسب رضـایت مشـتری اسـت.[2] این رضایت در ویژگی های مورد نظر مشترک منعکس میشود. یکی از این ویژگی ها، دسترسی به کـالا یـا خـدمات در کمترین زمان ممکن است [3]. عرضه کنندگان کالا و خدمات ناچارند برای تصمیم گیری بهینه در جهت کـاهش زمـان انتظار مشتریان خود از نظریه های صف بهرهگیری نمایند تا نه تنها سطح منابع لازم برای سرمایهگذاری را مشخص نمایند، بلکه تا آنجا که امکان دارد رضایت مشتری را تامین نمایند.[4] این موضوع بهویژه برای ادامه حیات اقتصـادی شـرکتهـا در شرایطکاملاً رقابتی اهمیت ویژه ای دارد. لذا تحقیق در زمینه توصیف عملکرد سیستم های صـف در شـرایط محیطـی مختلف امری ضروری محسوب می گردد. در مجموع می توان گفت جانمایی فیزیکی سیستم های صف[5]، نوع چیدمان خدمت دهنده ها[6]، میزان فضای تخصیصی به مشتریان در استفاده بهینه از تمامی خدمت دهنده هـا [7]و در نهایـت نـوع ارائه خدمت [8] می تواند از جمله عوامل موثر در تحلیل سیستم های صف در شرایط واقعی با توجه به محـدودیت هـای موجود می باشد. عدم بهینه سازی طرح استقرار می تواند در بوجود آمدن صف های طولانی و به تبـع آن افـزایش مـدت زمان انتظار افراد جهت دریافت خدمت ، را به همراه داشته باشد.
نظریه صف، یک روش کلاسیک ریاضی است برای مطالعه صف از قبیل بدست آوردن میانگین زمان انتظار و متوسط تعـداد مشتریان در سیستم [9]، .[10] صف بندی درخت فازی و کنترل فازی صف یک رویکرد جدیـد بـرای بررسـی سیسـتم صـف خواهد بود
تئوری صف با کار تحقیقاتی آقای ای . کی .ارلنگ1 در سـال 1909 آغـاز گردیـد [11]. در آن سـالهـا او مطالعـات و انجام آزمایشات بر روی میزان افزایش و کاهش تقاضا در سیستم تلفن به بررسی عوامل و روابط موجـود در سیسـتم مـورد مطالعه پرداخت. هشت سال بعد او از جزیئات مطالعات صورت پذیر فته اتوماتیک کردن سیستم تلفـن و نتـایج حاصـل از روابط موجود، که پایه و اساس تئوری های صف قرار گرفت منتشر ساخت. در پایان جنگ جهانی دوم او کاربرد استفاده از مدل های صف را در حوزههای عمومی و تجاری به سرعت گسترش داد [12]. تئوری صف یکـی از قـدیمی تـرین و
2
توسعه یافته ترین تکنیک های تجزیه و تحلیل که در خطوط انتظار که همه روزه با آن روبرو هستیم مـورد اسـتفاده قـرار میگیرد.[11]
درخت تصمیم فازی با زمان سرویس انعطاف پذیر که در این مقاله مورد بررسی قرار گرفتـه اسـت هـدف بکـار گـرفتن یـک رویه فازی به منظور کاهش هزینه از سیستم و کنترل متوسط تعداد مشتریان در صف است. تمام قوانین ریاضیات فازی در ایـن مقاله در اصل گسترش زاده [13]، الگوریتم ایجاد درخت تصمیم فازیID3 ،مفهوم ممدانی، مفهـوم امکـان و احتمـال، نتـایج حاصل از این مقاله را می توان به دیگر سیستم های صف عمومیت یا توسعه داد. در سیستم ما تغییر بـین هزینـه هـای مشـخص شده توسط SC (هر زمان که ما به سرور وصل شده)، نرخ هزینه نگه داری هر مشتری (HC) بـه نـرخ هزینـه سـرور در حـال اجرا (RC) را با استفاده از درخت تصمیم پیش بینی می کنیم. ما باید سعی کنیم که یـک رویـه بـرای کنتـرل زمـان سـرویس پس از وصل شدن به سرور را به کار بگیریم . کنترل کننده فازی ما دارای دو خروجی می باشد .
-1 صف ها در درخت تصمیم فازی
در نظر بگیرید ما یک سیستم صف با صف پواسن، یک سرور و زمان خدمات فازی را داریم. نرخ ورود λ می باشد و ترتیب First in first (اولین ورودی، اولین خروجی) بکار رفته است. فرض کنید که زمان سرویس یک مجموعـه فـازی مشـخص شده توسطS̃ است. بنابراین است.
تصور کنید بعد از به اتمام رسیدن سرویس ما یک حالت جدید داریم. تعداد مشتریان که یـک شـخص کـه سـرویس او فقـط کامل شده در این سیستم به عنوان یک حالت سیستم در نظر گرفته شده است. بنابراین احتمال اینکه ما از حالت i به j حرکت کنیم یکسان است و به احتمال این است که تعداد j-i+1 از مشتریان به سیستم در طول زمان سرویس T وارد شوند.
پس ما صف ها را به شکلی که احتمال وارد شدن i در طول زمان سرویس در درخت تصمیم در درخت تصمیم فازی قرار می دهیم و هزینه تغییر بین صف ها SC و نرخ هزینه نگه داری هر مشتری (HC) را پیش بینی می کنیم و به سیستم فازی با توجه به SC,HC و L که به شرح زیر نشان می دهیم d2 (زمان سرویس) بدست می آوریم :[15]
)1(
3
کسری از زمان در دراز مدت است که حالت سیستم i را نشان میدهد. در حال حاضر ما می توانیم L را با استفاده از فرمول زیر محاسبه کنیم:
)2(
از فرمول بالا می فهمیم که L و W نیز مجموعه های فازی هستند، پس: L=?, W=?
)3(
.1-2 الگوریتم ایجاد درخت تصمیم فازیID3
-1 ریشه را ایجاد کن و تمامی داده ها را در آن قرار بده
-2 اگر گره t با مجموعه فازی داده D شرایط زیر را داشته باشد الگوریتم خاتمه می یابد :
-1-2 نسبت مجموعه داده در یک کلاس مثلاCk بیشتر یا مساوی یک مقدار آستانه شود.به صورت زیر:
-2-2 مجموع تعلقات یک مجموعه داده کمتر از یک حد آستانه شود. به صورت زیر :هیچ ویژگی
دیگری جهت دسته بندی وجود نداشته باشد
-3اگر شرایط فوق برقرار نباشد پس گره فوق برگ نیست و به صورت زیر برگهایی ایجاد می شود
-1-3 به ازای هر ویژگی Ai را به صورتی که در ادامه می آید ، محاسبه کن . آن ویژگی که مقدار آن از همه بیشتر است را انتخاب کن
D -2-3 را با توجه به Amaxبه D1, D2, . . ., Dmزیرمجموعه تقسیم کن به گونه ای که مقدار تعلق داده
درDj از ضرب مقدار تعلق آن در Dو مقدار Fmax,jمربوط به آن ویژگی درD به دست می آید
-3-3 گره های جدید tl, t2 , ..., tmرا برای زیر مجموعه های فازی D1, D2, . . ., Dm بساز و هر لبه از گره
tبه tjرا با مجموعه فازی را با Fmax,jبرچسب بزن 4-3)به جای D، Dj را در نظر بگیر و کار را از مرحله
2 از سر بگیربرای محاسبه مقدار G(Ai,D)) باید از فرمول زیر استفاده کرد :
)5(
4
که
)6(
ونحوه محاسبه متغیرهای فوق به صورت زیر می باشد :
)7(
)8(
.2-2 کنترل فازی
در این قسمت ما می خواهیم به یک رویه برای کنترل زمان سرویس از سیستم صف بندی در درخت فازی بدست آوریم، در رویه مطلوب برای هزینه، ما تا زمانی که حداقل یک مشتری در سیستم وارد می شود آنها را با توجـه بـه طـول هزینـه و صـف مربوط به آن در درخت تصمیم فازی طبقه بندی می کنیم .[14] هنگامی که سیستم خالی می شـود مـا سـرور را قطـع کـرده و تنها چیزی که ما نیاز داریم مشخص کردن زمان وصل شدن سرور می باشد.
در سیستم ما تغییر بین هزینه های مشخص شده توسط SC (هر زمان که ما به سرور وصـل شـده)، نـرخ هزینـه نگـه داری هـر مشتری (HC) به نرخ هزینه سرور در حال اجرا (RC) را با استفاده از درخت تصمیم پیش بینی می کنیم. ما بایـد سـعی کنـیم که یک رویه برای کنترل زمان سرویس پس از وصل شـدن بـه سـرور را بـه کـار بگیـریم . کنتـرل کننـده فـازی مـا دارای دو خروجی می باشد .
یکی d1 هست که نشان می دهد که سرور وصل است یا نه و دیگری d2 هست که زمان سرویس را تعیـین مـی کنـد در حـال حاضر ما به دانستن ورودی هایمان که قادر به تعریف منطق کنترل ما است نیاز داریم . در صورتی که اگر هـیچ هزینـه (تغییـر) سوئیچینگ نداشته باشد . (بدیهی است در آن به محض اینکه یک مشتری وارد سیستم شود سرور وصـل مـی شـود کـه بهینـه خواهد بود ) اما از آن جایی که ما هزینه سوئیچینگ بزرگی در بسیاری از موارد داریم ما در زمانی که جمع هزینـه نگهـداری (AHC) به اندازه کافی بزرگ و کامل با هزینه سوئیچینگ (SC) به دست آمده شود سرور وصل می شود .
5
ایجاد Si تعدادی از مشتریان در سیستم در واحد i ام از زمان است.
از آنجایی که ما نرخ ورود (رسیدن) بلور متوسط را داشته، بنابراین پس از اولین واحد زمان ما به طـور متوسـط λ مشـتریان در سیستم را داریم. مجموع میانگین هزینه نگهداری پس از اولین واحد از زمان AHC=HCλ/2 خواهد بود. پس از واحد n ام از زمان مجموع میانگین هزینه نگهداری خواهد بود.
AHC= HCλ/2 + 3HCλ/ 2 + 5HCλ/2 + … + (2n-1)HCλ/2=n2 λHC/2
از آنجا که AHC برابر به SC هزینه سوئیچینگ می شود، ما سرور را وصل می کنیم d1) وصل می شود)، بنابراین
جدول:1 قوانین فازی
بنابراین، هنگامی که مجموع هزینه نگهداری برابر می شود با )SCهزینه سوئیچینگ) می شود. طول صف حدود (تقریباً):
6
بنابراین زمانی که طول صف است ما سرور را وصل کنیم (d1=ON) همچنین مـا مـی دانـیم کـه بـالاترین ساعت h است، آسان تر از آن اتخاذ یک تصمیم با وصل کردن سرور است.
در حال حاضر ما باید تابع عضویت h، L و d2 (زمان سرویس) را تعریف کنیم. ما زمانی کـه طـول صـف محاسـبه مـی شـود بدست می آید. ما سرور خفته را وصل می کنیم. بنابراین در نظـر گرفتـه شـده کـه فاصـله نرمال ما 6]،[0 است، ما باید در مقیاس به 6 را انجام دهیم بنابراین فاکتور مقیاس بصورت زیـر خواهـد بـود:
بنابراین فاکتور مقیاس برای هزینه نگهداری HC برابر با 6/SC است. تـابع عضـویت بـرای L و HC مطـابق بـا شـکل 1 و 2 خواهد بود:
زمان سرویس (t)که با L بزرگ مشخص شده ) (L= که بزرگتر هستند. بنابراین معادله زیـر بایـد حـل شـود که بصورت:
ما بزرگترین t را مشخص و ما از معادله فوق که بوسیله A نشان می دهـیم و بزرگتـر از آن را بدسـت آورده. بنـابراین فـاکتور مقیاس گذاری برای d2 برابر 6/A می باشد (شکل .(3
