نشریه تخصصی مهندسی صنایع، دوره 46، شماره 1، فروردین ماه 1391، از صفحه 39 تا 51 بهبود زمان انتظار با استفاده از الگوریتم اولویتدهی بر اساس
بالاترین امتیاز در صفوف انسانی

عباس دیدبان*1 و محسن کیانی2
استادیار- دانشکده برق و کامپیوتر- دانشگاه سمنان
دانش آموخته کارشناسی ارشد مکاترونیک- دانشکده برق و کامپیوتر – دانشگاه سمنان
(تاریخ دریافت 21/9/90، تاریخ دریافت روایت اصلاح شده 10/10/90، تاریخ تصویب 14/1/91 )

چکیده
در این مقاله به بیان یک الگوریتم جدید در اولویتدهی صفوف انسانی پرداخته شده است. این شیوه اولویتدهی در صفوفی قابل استفاده است که حجم تقاضا در آنها متفاوت باشد. در این الگوریتم زمان انتظار هر مشتري متناسب با حجم مورد تقاضا است. یک مثال بارز چنین صفی، صف نانوایی است. در روش پیشنهادي در این مقاله، زمان ورود مشتري ذخیرهسازي شده و هنگام فراخوانی یک مشتري براي سرویس -دهی، امتیاز همه مشتریان (طبق رابطه تعریف شده) محاسبه شده و مشتري با بیشترین امتیاز فراخوانی میشود. با اجراي این الگوریتم زمان انتظار به طور قابل ملاحظهاي بهبود مییابد. با ارایه یک مدل ریاضی براي شبیهسازي الگوریتم مذکور اثبات شده است که زمان انتظار از نظر تئوري تا حداکثر 25 درصد قابل بهبود است. همچنین در اجراي عملی براي یک صف نمونه، زمان انتظار حدود 20 درصد بهبود یافته است.
نکته قابل توجه دیگر پیش بینی زمان انتظار به صورت کاملا شهودي با توجه به تعداد افراد حاضر در صف است. از دیگر مزایاي این روش می-توان به تنظیم خودکار ازدحام، عادلانه تر بودن صف و افزایش رضایتمندي مشتریان اشاره کرد. این روش در یک دستگاه نوبتدهی براي استفاده در نانوایی پیادهسازي شده و نتایج آن ارایه شده است. این نتایج تأییدي بر اثرات مثبت برشمرده شده است. نتیجه نظرسنجی نیز حاکی از افزایش رضایتمندي مشتریان است.

واژه هاي کلیدي: صف، زمان انتظار، بهینهسازي، نوبتدهی

مقدمه
هماهنگ نبودن تولید و مصرف یا سرویسدهنده و سرویس گیرنده با توجه به نوع تابع تقاضا که اغلب احتمالی است، سبب ایجاد صف میشود. در بسیاري از مکان ها به دلیل محدودبودن منبع، با این پدیده اجتماعی روبه رو هستیم. شهروندان در هر سال زمان قابل ملاحظه-اي را در صف میگذرانند که براي کشورهاي مختلف این میانگین متفاوت است.
Email: [email protected] ، 0231 – 3354123 :نویسنده مسئول: تلفن: 3366997- 0231 ، فاکس *

صف ممکن است در طرف مصرف کننده یا متقاضی و یا در طرف تولیدکننده یا سرویسدهنده باشد. با توجه به نوع سیستم و شرایط و اهداف، مکانیزمهاي متنوعی از صف براي هماهنگی بین دو قست سیستم استفاده می شود. میزان زمان انتظار مشتري با رضایت مشتري رابطه منفی دارد[1] به طوري که از زمان انتظار به عنوان منبع مهمی در نارضایتی مشتري یاد میشود[2]. در سیستمهاي تولید، امکان ایجاد صف در هر دو طرف تولید و تقاضا وجود دارد که با توجه به شرایط بازار اغلب توسط تولیدکننده انتخاب می شود. در سیستمهاي صنعتی، سیاستگذاري تولیدکننده نحوه سرویسدهی به مشتریان را مشخص میکند و به صورت معمول سیستم “اول ورود اول سرویس دهی”(آواس)1 استفاده می شود. در سرویس-دهی به مشتریان با حجم تقاضاي زیاد نیز با توجه به شرایط رفتار می شود و چه بسا خارج از صف به او سرویس داده شود و یا هم براي مدت بیشتري منتظر بماند، چون هدف اصلی در این گونه سیستمها سود بیشتر و داشتن مشتري با حجم تقاضاي بیشتر است.
در سیستمهاي انبارداري اغلب از روش “آخر ورود اول سرویس دهی”(آخ اس) 2 استفاده می شود. این نوع صف در سیستم هاي صف انسانی کاربرد خاصی ندارد و در سیستمهاي انبار یا پشته استفاده میشود.
سیستم آواس از پرکاربرد ترین نوع صف در سیستم-هاي صف انسانی است و مردم نیز به آن عادت کرده اند، اما سیستم عادلانهاي نیست. این مدل سرویس دهی باعث ایجاد احساس بی عدالتی اجتماعی در مشتري میشود[3] که باعث بالا رفتن زمان انتظار ادراکی مشتري که شایستگی سرویس دهی زودتر را دارند می شود[4]. به طورمثال صف یک بانک را در نظر بگیرید که به طور معمول هر نفر یک یا دو قبض را پرداخت کرده و یا چکی را وصول میکند. چنانچه در این میان ناگهان شخصی از یک شرکت مراجعه کرده و قصد پرداخت 30 قبض را داشته باشد، این کار به طور قطع با اعتراض سایر مشتریان منتظر در صف روبه رو خواهد شد. راه حلهایی که اغلب براي این حالتها به کار گرفته میشود، سلیقهاي بوده و توسط مدیر آن قسمت ارائه میشود. در بسیاري از مکانها مانند خرده فروشیها راه حلهایی را مانند ایجاد صف سریع براي مشتريها با نیاز به سرویس کم مدت ترتیب می دهند. چرا که با کم کردن زمان انتظار براي مشتريها با تعداد اقلام کمتر می توان میانگین زمان انتظار کل سیستم را کاهش داد([4] و [5]). اگر چه مثال ذکرشده ممکن است نادر باشد، اما تفاوت در نوع تقاضا و در نتیجه زمان سرویسدهی متفاوت کاري طبیعی است.
در حوزه مدیریت صف، در ابتدا لازم است براي تجزیه و تحلیل و نیز کنترل یک صف بتوان آن را مدل سازي کرد. در تئوري صف کلاسیک از آنجا که ورود مشتريها یک فرایند احتمالی و نه کاملا مشخص است و همچنین زمان سرویسدهی به مشتریان نیز ثابت نیست، تئوري احتمالات ابزاري مناسب براي تجزیه و کنترل صف هستند. در این بین کارهاي زیادي انجام شده است. در مرجع[7] چگونگی مدل سازي صف با قوانین احتمال ارایه شده است. در مرجع[8] نیز خلاصهاي از کارهاي مهم انجام شده در تئوري صف ارایه شده است. در کارهاي انجام شده، هدف، تخمین تعداد مشتريها در صف و نیز زمان انتظار و زمان اقامت هر مشتري در صف است. یکی از صفها که به دلیل اهمیت آن توجه زیادي به آن شده است، صف اولویت دار است. در این نوع از صف، مشتريها کلاسهاي مختلفی داشته و هر کلاس نرخ ورودي منحصر به فرد خود را دارد. همچنین هر کلاس یک میانگین زمان سرویسدهی دارد. در چنین صفی به یک مکانیسم اولویتدهی نیاز است تا ترتیب مشتريها را براي ارایه سرویس تعیین کند[9]، [10] و [11]. در این مقاله نتایج عملی حاصل از اجراي چند مکانیسم اولویتدهی در صف نانوایی ارایه و با نتایج نمونه برداري شده از صف سنتی مقایسه و در هر حالت زمان انتظار کل مشتريها براي مشاهده تأثیرات آن بررسی شده است.
در مطالعاتی که در کنترل یک صف انجام شده است، اغلب هدف، بیشینه کردن سود یا رفاه اجتماعی و انصاف است. یک روش معمول در اولویتدهی، اولویت دهی مطلق است که مشتریان موجود در صف طبق این اولویت ثابت فراخوانی می شوند[12]. در این زمینه مطالعات زیادي انجام شده است که در مراجع[13] و [14] خلاصه اي از کارهاي انجام شده در این زمینه ارایه شده است.
نوع دیگر اولویتدهی، اولویت دهی نسبی است که در آن اولویت داده شده به یک کلاس به متغیرهاي حالت در دیگر کلاسها نیز بستگی دارد. در مرجع [15] میانگین زمان انتظار در یک صف تک سرور با توزیع ورودي و زمان سرویسدهی پواسون مورد بحث قرار گرفته است. در مراجع[12]و[16] نیز اختصاص اولویت نسبی مورد بحث قرار گرفته و نشان داده شده است که با اختصاص اولویت نسبی، هزینه در سیستم(تابع هزینه، تابعی از زمان انتظار مشتریان در صف است) نسبت به حالت معمول آواس کاهش مییابد.
در [17]روشی براي اولویتدهی به بیماران در صف جراحی ارایه شده است که نتیجه آن حاکی از کاهش زمان انتظار وزنی مورد انتظار بیماران است. در تحقیقی که در [18] انجام شده است، به بررسی نوعی از صفهاي اولویت دار در شهر بازي پرداخته شده است که حجم مورد تقاضا در آن یکسان است، اما میتوان با پرداخت هزینه بیشتر داراي اولویت شد. طبق نتایج به دست آمده، وجود چنین اولویتی، باعث ایجاد نارضایتی و احساس بی عدالتی در مشتریان حاضر در صف اصلی می شود و نیز بر مراجعه مجدد اثر منفی دارد. توجه به تفاوت چنین اولویتی با اولویت پیشنهادشده در این مقاله بااهمیت است؛ چرا که اولویت داده شده در صف پیشنهادي، بر پایه حجم سرویس درخواستی توسط مشتري است.
نوع دیگري از سیستمهاي صف داراي اولویت، سیستم سرکشی است که یک سرور و چند کلاس دارد که در چنین سیستمی از یک کلاس براي برههاي از زمان به اصطلاح “سرکشی” و به مشتریان آن سرویس داده می-شود. پس از گذشت مدت زمانی مشخص، به کلاس دیگر سوئیچ شده و به آن سرویس داده میشود. این فرایند تکرار میشود تا به همه سیستمها سرکشی شود. یک مدل معمول سرکشی چرخهاي است که سرور به m کلاس با ترتیب ثابتی سرکشی میکند. چندین قانون براي تعیینزمان سرویسدهی سرور به هر کلاس وجود دارد. دو تا ازمعروف ترین روشها، روش جامع و روش دروازهاي است.
روش جامع، سرویسدهی به یک کلاس را ادامه میدهد تا دیگر مشترياي در این کلاس نباشد و سپس به کلاس دیگر سوئیچ میکند. روش دروازهاي فقط به مشتریانی که در لحظه سوئیچ سرور به کلاس مربوطه باشند، سرویس دهی میکند[8]. اگر چه در این مقاله نیز دسته بندي روي مشتریان انجام شده است، اما روش انتخاب مشتري با این روشها متفاوت است.
در این مقاله یک صف چند کلاس مدنظر داشته و الگوریتمی براي کاهش زمان انتظار مشتریان در چنین صفی ارایه شده است. این الگوریتم که آن را اولویتدهی بر اساس بالاترین امتیاز3 می نامیم، با توجه به زمان انتظار مشتریان و حجم تقاضاي آنها اولویت را تعیین میکند.
براي اثبات اثرات مثبت این نوع اولویت دهی، مدلی ریاضی براي شبیه سازي آن ارایه شده است. این اولویت علاوه بر کاهش زمان انتظار، اثرات مثبت دیگري نیز دارد؛ به ویژه در درازمدت که مشتریان به آن عادت کردهاند. صف نانوایی که در آن مشتریان با درخواستهاي متفاوت وجود دارند(کلاسهاي متفاوت) و سرور براي سرویسدهی به هر کلاس با توجه به حجم تقاضاي آن زمان بیشتري صرف می کند، صفی مناسب براي اجراي الگوریتم مورد نظر است. بنابراین براي بررسی اثرات الگوریتم پیشنهادي، روش اولویتدهی مذکور روي یک صف نانوایی اجرا و تأثیرات آن بررسی شده است. چند مزیت عمده را میتوان براي این سیستم بر شمرد:
کاهش زمان انتظار
رعایت انصاف بیشتر و افزایش رضایتمندي مشتریان
جلوگیري از تقاضاهاي بی مورد
تنظیم نوع تقاضا متناسب با شرایط
ترتیب و نظم در سیستم
اگر چه ایده استفاده از امتیاز در تعیین اولویت در صف ها جدید نیست، اما این ایده تا کنون در صفوف انسانی مورد استفاده قرار نگرفته است. علاوه بر این، روش استفاده شده در این مقاله، یک روش امتیاز دهی خطی و متناسب نیست، چون با اجراي این روش، رضایتمندي مشتریان کاهش یافت که با اصلاح نحوه امتیازدهی توانستیم رضایتمندي قابل قبول و بهبود زمان انتظار مناسب داشته باشیم. الگوریتم ارائه شده را می توان یک الگوریتم اولویت دهی فازي دانست که به دلیل زیادبودن قواعد از جدول استفاده شده است.
در این مقاله، در قسمت بعد به بررسی مختصر سیستمهاي صف پرداخته شده است. در ادامه در قسمت سوم، روش هاي اولویتدهی در صف انسانی مورد بررسی قرار گرفته است. در قسمت چهارم، نحوه کاهش زمان انتظار به اثبات رسیده و روشی براي محاسبه زمان انتظار ارائه شده است. قسمت پنجم، مربوط به ارائه نتایج عملی حاصل از اجراي الگوریتم پیشنهادشده و مقایسه با حالت رایج است. در انتها، نتایج حاصله مورد بررسی قرار گرفته و نتیجهگیري به عمل آمده است.

سیستمهاي صف
قوانین اولویت خط انتظار تعیین می کند که کدام مشتري به عنوان نفر بعدي سرویس دهی شود. قانون معمول استفاده از مکانیزم اولویتدهی اول ورود اول سرویسدهی(آواس) است. این قانون با توجه به اینکه چه کسی بیشترین زمان را در صف ایستاده، اولویت را محاسبه می کند. اغلب از نظر مشتريها منصفانه ترین روش تعیین اولویت در بیشتر صفها قانون آواس است. این روش زمانی مناسب خواهد بود که شرایط همه افراد در صف از هر جهت مشابه باشد که این شرط در همه جا برآورده نمی-شود. قوانین دیگر مانند ابتدا مشتري با کمترین نیاز سرویس دهی4 ( آ ك ن م)، ابتدا مشتري با سریع ترین نیاز سرویس دهی5 ( آ س ن م)، ابتدا مشتري با بزرگ ترین نیاز سرویس دهی6 ( آ ب ن م) ابتدا پر سود ترین مشتري7 ( آ پ م) و … نیز براي تعیین اولویت استفاده می شود. باید توجه شود که لازم است از قانون اولویت دهی که بهترین و مناسب ترین پشتیبانی از استراتژي کاربرد مربوطه را دارد، استفاده شود.
همان طور که اشاره شد، قانون اولویتدهی آواس منصافه ترین قانون به نظر می رسد و مردم نیز به آن عادت کردهاند، اما این ادعا زمانی درست است که تقاضاي همه مشتریان حاضر در صف یکسان باشد. در بسیاري از انواع صف هاي انسانی این شرط صادق نیست. به طور مثال در صف نانوایی یک نفر متقاضی 4 عدد نان و دیگري متقاضی 10 عدد نان است. در این حالت هیچ یک از دو نوع قانون آواس و اكنم عادلانه به نظر نمیرسد. در این حالتمیتوان از قانونی ترکیبی از این دو با عنوان، ابتدا مشتريبا بالاترین امتیاز ( آمبا ) استفاده کرد. این امتیاز از تقسیم زمان انتظار بر زمان سرویس دهی به دست میآید. براي استفاده از این قانون لازم است تا زمان مورد نظر براي سرویسدهی در ابتداي ورود مشخص باشد. این پارامتر در بعضی از صفها مانند صف نانوایی تقریبا مشخص بوده و متناسب با تعداد مورد نیاز خواهد بود.
براي انتخاب قانون مناسب، لازم است برخی از پارامترهاي سیستم معین شوند. در ادامه به بررسی پارامترهاي مهم در یک صف پرداخته میشود.

پارامترهاي مهم در یک خط انتظار
هر مدل صف با پارامترهایی مشخص میشود. این پارامترها در سنجش کارآیی و تجزیه و تحلیل یک سیستم اهمیت دارند. این پارامترها عبارتند از:

میانگین تعداد مشتريهایی که در خط می ایستند (n)
میانگین زمانی که مشتري صرف انتظار می کندTwave
زمانی که مشتري متقاضی سرویس k ام منتظر
میماند Twk
تعداد سرویسهاي مورد تقاضا(m)
میانگین زمانی که براي مشتري متقاضی سرویس
kام در سیستم صرف میشودTS k
میانگین زمانی که براي مشتري در سیستم صرف میشودTSave ز. میانگین و حداکثر حجم تقاضاي مشتریان (vave و vm) ح. ترتیب سرویسدهی ط. میزان بهره برداري و استفاده از سیستم ي. تعداد خطوط انتظار ك. تعداد سرورها و آرایش سرورها

روش فعلی مورد استفاده در سیتمهاي نانوایی از نوع یک سرور چند خط انتظار و یک فاز است که پس از اصلاح به صورت یک سرور، یک خط انتظار و یک فاز خواهد شد.

روش اولویتدهی بر اساس بالاترین امتیاز
در پژوهش انجام شده با ارایه الگوریتمی با عنوان نوبتدهی بر اساس بالاترین امتیاز به دنبال کاهش زمان انتظار و همچنین بالا بردن سطح عدالت بین مشتریان هستیم. به طور منطقی، هر مشتري براي دریافت سرویس باید مدت زمانی را در صف سپري کرده و این مدت زمان باید متناسب با حجم سرویس مورد تقاضاي وي باشد. چنانچه در یک صف، همه مشتريها نیاز به حجم سرویسدهی برابر داشته باشند، استفاده از مکانیسم آواس براي این صف کفایت میکند. اما در اکثر صفهاي انسانی، از جمله صف نانوایی و صف بانک، چنین شرایطی حاکم نبوده و هر مشتري نیاز به صرف مدت زمانی متناسب با سرویس درخواستی دارد که در نانوایی حجم مورد تقاضا، تعداد نان است و از مشتري به مشتري دیگر متفاوت است. براي روشن شدن این موضوع، از دیدگاه دیگر به موضوع مینگریم: هر مشتري براي دریافت یک سرویس، دو نوع هزینه میپردازد؛ یکی زمانی که منتظر دریافت سرویس است و دیگري هزینهاي که براي دریافت سرویس به سرویس دهنده می پردازد. ما به دنبال این هستیم که هزینه کل یا به عبارت دیگر زمان انتظار با حجم مورد تقاضا متناسب باشد تا عدالت به شکل بهتري بین مشتریان رعایت شود. اگر ضریب هزینه را براي مشتري i به صورت (C(i، زمان اقامت(جمع زمان انتظارTwi و زمان دریافت سرویسTSi) را به صورت(T(i و حجم مورد تقاضا را به صورت (V(i و هزینه دریافتی از مشتري به ازاي هر واحد سرویسدهی را cv و هزینه تحمیل شده به مشتري به ازاي هر واحد زمانی (دست مزد هر ساعت انتظار) را ct در نظر بگیریم، میتوان نوشت:
(1) C i V(i)*cv T(i)*ctبا توجه به معادله (1) و اینکه هزینه همه مشتريها باید به نسبت زمان انتظار و حجم تقاضاي آنها باشد، می-توان نتیجه گرفت که هر مشتري با حجم تقاضاي مشخص، باید زمان مشخصی که متناسب با همان حجم تقاضا است، منتظر بماند تا هزینهاي که متحمل دریافت یک سرویس میشود، متناسب با حجم سرویس درخواستی باشد. در این حالت طبیعی است که مشتریان به ترتیب ورودي سرویس داده نشوند و براي تعیین ترتیب سرویسدهی میتوان با استفاده از معادله (2) زمانی کهسرویسدهنده آماده سرویسدهی به مشتري بعدي است، امتیاز هر مشتري را محاسبه کرده و با استفاده از این امتیازها به مشتري داراي بالاترین امتیاز به عنوان مشتري واجد شرایط سرویسدهی کرد. بنابراین ترتیب سرویس دهی به مشتريها در صف، نه بر اساس ترتیب ورود، بلکه بر اساس زمان انتظار و حجم مورد تقاضا است:
(2)
Bi

T(i)
(k *V(iکه در این معادله (B(i امتیاز مشتري i ام و k ضریبی ثابتی است که در ابتدا میتوان آنرا برابر یک فرض کرد، اما در ادامه براي افزایش رضایتمندي آن را براي حجمهاي تقاضاي متفاوت، متغیر در نظر گرفته ایم. از بین همه مشتریان حاضر در صف، به مشتري داراي بالاترین امتیاز سرویس داده می شود. استفاده از این مکانیسم براي اولویتدهی به مشتریان در صف، دو اثر اصلی دارد که اولین آنها رعایت انصاف بیشتر بین آنها است و دومین اثر آن کاهش زمان انتظار مشتریان نسبت به مکانیسم آواس است. رعایت انصاف را از آن نظر می توان گفت که کسی که متقاضی سرویس طولانیتري است، باید هزینه زمانی بیشتري را هم بپردازد. کاهش زمان انتظار موضوعی است که ما در پی اثبات ریاضی آن هستیم.

مثالی از یک صف نانوایی
در ادامه با ارایه یک مثال ساده از یک صف نانوایی، اثرات مثبت الگوریتم ذکرشده، یعنی سرویسدهی بر اساس حجم تقاضا، ارایه میشود. از اثرات جانبی این روش میتوان به تنظیم خودکار ازدحام و همچنین تشویق به دریافت نان متناسب با نیاز و کاهش دورریز نان اشاره کرد.
در ابتدا فرض شده است که حجم تقاضا تعداد نان باشد و زمان انتظار بر حسب دقیقه در نظر گرفته شود.
براي مثال فرض کنید مشتري 1s متقاضی سرویسدهی با حجم 7 عدد نان و مشتري 2s داراي حجم تقاضاي 3 عدد نان است. زمان انتظار براي مشتري اول برابر با 15 دقیقه و مشتري دوم برابر با 10 دقیقه است. در این صورت امتیاز این مشتريها با استفاده از رابطه (2) و در نظر گرفتن 1=k به صورت زیر حاصل میشود:
B1=15/(1*7)=2/14
B2=10/(1*3)=3/33
بنابراین در ابتدا به مشتري 2B و سپس 1B سرویس داده میشود. براي نشان دادن اینکه استفاده از این مکانیسم منصفانه تر است، فرض کنید داریم: 500=Tu و بدین معنی که هزینه انتظار 60 دقیقه براي هر شخص برابر با 30000 ریال باشد. فرض میشود حجم تقاضاي کل مشتریان را بتوان بین 1 تا 10 تقسیم بندي کرد.
همچنین زمان سرویسدهی به ازاي هر واحد برابر با 2 دقیقه(دو واحد زمانی) است. همچنین قیمت هر نان 500 ریال در نظر گرفته شده است. در ابتدا فرض شود به این دو مشتري با مکانیسم آواس سرویس داده شود. بنابراین می توان نوشت:
زمان صرف شده توسط مشتري 1B:
S1= 15+14=29
15 زمان انتظار مشتري و 14 زمانی است که طول میکشد تا مشتري سرویس داده شود. با استفاده از رابطه
(1) میتوان نوشت:
18000=(500* 7)+(500*29) =1Cبا تقسیم این عدد براي یافتن هزینه به ازاي هر واحد سرویسدهی داریم:
2571=7/18000=1cmبنابراین مشتري اول به ازاي دریافت هر عدد نان، 2571ریال هزینه متحمل شده است. حال براي مشتري دوم:
S2=10+14+6=30 C2= (30*500)+(3 *500)= 16500 cm2= 16500/3=5500
بنابراین مشتري دوم به ازاي دریافت هر واحد سرویسدهی، 5500 ریال هزینه متحمل شده است. به وضوح دیده می شود که این حالت اصلا عادلانه نیست، یعنی یک مشتري بیش از 2 برابر دیگري براي دریافت سرویس یکسان هزینه متحمل شود. حال از مکانیسم پیشنهاد شده استفاده میشود که در آن به علت بالاتر بودن امتیاز مشتري دوم، در ابتدا به این مشتري سرویس داده میشود. براي مشتري دوم یا 2B داریم:
16=6+10=2S 9500 =(500* 3)+(500*16) =2C 3166=3/9500 =2cmو همچنین براي مشتري 1B داریم:
S1= 15+6+14=35
C1= (35*500)+(7*500)= 21000
3000=7/21000 =1cmهمان طور که ملاحظه میشود در این حالت هر دومشتري هزینهاي تقریبا یکسان براي هر عدد نان متحملمیشوند.
با استفاده از این روش، از آنجا که در مقایسه با مکانیسم رایج کنونی مشتري با حجم سرویسدهی بالاتر همه مشتريها با حجم کمتر را معطل نمی کند، زمان انتظار کل مشتريها کاهش مییابد. همچنین با عادت کردن مشتري به اجراي چنین مکانیسمی به ویژه در صف نانوایی، مشتري به درخواست تعداد نان متناسب با نیاز ترغیب میشود. بنابراین به طور حتم دورریز نان نیز کاهش خواهد یافت.
در ادامه در ابتدا اثبات خواهد شد که الگوریتم ارایه شده داراي اثر کاهش زمان انتظار بوده و سپس چگونگی محاسبه زمان انتظار براي مشتریان ارایه شده است. در ادامه آن به بررسی پیادهسازي الگوریتم پیشنهادي به صورت عملی در یک نانوایی پرداخته شده و نتایج آن مورد بحث قرار گرفته است.

اثبات کاهش زمان انتظار و چگونگی محاسبه آن با الگوریتم نوبتدهی بر اساس بالاترین امتیاز
ما از اولویتدهی “اول ورود-اول سرویسدهی” که شناخته شده ترین و پرکاربردترین الگوریتم مورد استفاده است، به عنوان یک شاخص براي اثبات کاهش 25% زمان انتظار مشتریان حاضر در صف استفاده کردهایم.
براي اثبات این مدل نیاز به فرض چند نکته است. اولین نکتهاي که در اثبات این مدل فرض شده است، نسبت یکسان حجم کالاهاي مورد تقاضا است؛ بدین معنی که فرض شده است در یک دوره سرویسدهی هر کالا یا خدمات به یک نسبت مشخص تقاضا شده است. همچنین در ادامه وضعیت صف به وجود آمده در سیستم نیز به صورت یکنواخت فرض شده است؛ بدین ترتیب که میانگین نرخ ورود به سیستم در هر دوره زمانی از یک رفتار یا تابع خاصی پیروي می کند و نرخ ورود به سیستم با نرخ خروج از آن پس از ایجاد یک صف مشخص برابر است. این فرض در صفهایی مانند صف نانوائی در بازه-هاي مشخص زمانی معقول خواهد بود.
بدیهی است که مجموع زمان هاي انتظار مشتریان دریک سیستم برابر با زمان صرف شده توسط افراد حاضر در صف در کل دوره سرویسدهی است؛ مثلا اگر به طورمتوسط ده نفر در طول دوره سرویسدهی منتظر باشند، میتوان گفت مجموع زمان انتظار برابر با طول دوره سرویسدهی ضربدر 10 است. حال اگر بتوان تعداد مشتریان منتظر در هر نوبت سرویسدهی را کاهش داد، پس به طور قطع میتوان مدت زمان انتظار کل مشتریان را نیز کاهش داد که این موضوع به عنوان هدف اصلی از الگوریتم ارائه شده است. متوسط حجم تقاضا و مجموع تقاضاها در صف با اولویت دهی اوآس را می توان به ترتیب به صورت معادلات (3) و (4) نوشت:
(3)
m1
vave 

2
(4)
nm1
S 

2
که n تعداد افراد حاضر در صف در اجراي الگوریتم آوآس، m حداکثر حجم تقاضا هستند. چنانچه الگوریتم تغییر داده شود و پارامترهاي سیستم مانند نرخ ورود و سرعت سرویسدهی تغییر نکند، حجم کالایی که افراد وارد شده در صف متقاضی آن هستند تغییر نمیکند، اما تعداد افراد منتظر تغییر می کند. در ادامه اثبات شده است که زمان در بهترین حالت 25 درصد کاهش پیدا میکند.
واضح است که در الگوریتم جدید معرفی شده زمان انتظار متقاضی حجم i ، i برابر زمان انتظار متقاضی حجم واحد است. با این توضیح میتوان زمان انتظار بزرگ ترین حجم تقاضا تا کنون را به m قسمت تقسیم کرد که در نزدیک ترین بازه زمانی آن، همه متقاضیان حاضر هستند. در بازه زمانی دوم متقاضیان کمترین حجم تقاضا، سرویس داده شده و بقیه حاضر هستند. به همین ترتیب در آخرین گروه فقط متقاضیان بالاترین حجم تقاضا حاضر هستند. اگر افراد واردشده در این بازه زمانی را mx در نظر بگیریم، مجموع تقاضاهاي افراد حاضر در صف عبارت است از (با x نفر یکی x2 نفر دوتایی و …mx. نفر m تایی):

Sx (2x*2)  (3x*3) … (mx*m)
xmm12m1

6
با فرض برابر بودن مجموع تقاضاها و مساوي قرار دادننتیجه بالا با رابطه (4) مقدار x قابل محاسبه است:
(5)
3n
x 

m2m 1مجموع افراد حاضر در صف در الگوریتم جدید از رابطه زیر قابل محاسبه است:
167430489480


n’ x 2x 3x …mx xmm1
2
با قراردادن رابطه (5) در رابطه بالا خواهیم داشت:
n’

3nmm1
2m2m1
در نتیجه داریم:
(6)

n  n
چنانکه از رابطه (6) مشخص است اگر m بزرگ باشد، تعداد افراد 25 درصد کاهش مییابد. اگر m برابر با 8 باشد(قاعده معمول در نانوایی سنگک که حداکثر نان تحویلی 8 عدد است) تعداد افراد 5/20 درصد و اگر m برابر با 50 باشد، تعداد افراد 25/24 درصد کاهش می یابد.
با کاهش افراد منتظر در صف زمان، انتظار کلی نیز به همین نسبت بهبود مییابد.
مشتریان در سیستم است. در ادامه نشان داده شده است بنابراین میتوان گفت که هر متقاضی با نوع تقاضاي
پس از اثبات کاهش زم ان انتظار در سیستم، دومین گام به دست آوردن مدت زمان انتظار براي سرویسدهی بنابراین داریم:
mm1
Tw1 tp

2x
(7)
که Tw(i) زمان انتظار براي سرویسدهی به نوع سرویس iام است. همچنین تعداد افراد حاضر در صف
(n’) را میتوان به صورت زیر بر حسب x نوشت:
n  x  2x  3x … mx 

mm x  x 

2n
2mm 1
با قرار دادن نتیجه رابطه بالا در رابطه (7) داریم:
Tw1 tp

mm1 2n
2mm 1
پس از سادهسازي رابطه (8) حاصل میشود:
(8) Tw1 tpn همانطور که ملاحظه میشود، رابطه (8) مؤید این موضوع است که مدت زمان انتظار براي دریافت سرویس نوع اول برابر با زمان انتظار همه افراد حاضر در صف ضربدر زمان سرویس دهی نوع اول است. با به دست آوردن این رابطه میتوان از آن براي تعمیم به انواع سرویسدهی-هاي دیگر نیز استفاده کرد. بنابراین با استفاده از رابطه
(8) میتوان نوشت:
 Tw 1  t p n
Tw 2  2t p n
……
Tw m   mt p n

که اگر مشترياي که هم اکنون وارد سیستم شده است، متقاضی حجم درخواستی k باشد، زمان انتظار وي برابر زمان سرویس n’ نفر با حجم درخواستی k خواهد بود.
این موضوع مشابه این است که همه افراد حاضر در صف خواهان دریافت حجم درخواستی k باشند. براي اثبات این موضوع فرض کنیدtp زمان سرویسدهی به حجم تقاضاي نوع اول (زمان پخت یک نان در صف نانوائی) باشد. زمان انتظار شخص متقاضی این نوع سرویس که هم اکنون وارد شود، برابر با زمان سرویسدهی x نفر از همه انواع تقاضاها است. چرا که این افراد امتیاز بیشتري دارند( با فرض ورود mx نفر در این فاصله). زمان لازم براي سرویسدهی به حجم درخواستی نوع اول برابر با رابطه زیر است:
Tw1 tpx  2x  3x … mx
مشخص، به صورت مجازي در صفی با همان نوع تقاضا قرار می گیرد.

نتایج عملی پس از اجرا در صف نانوایی
الگوریتم ارایه شده از نظر منطقی عادلانه ترین روش است، اما فرهنگ عمومی جوامع در حال حاضر، پذیرش این شیوه را ندارد؛ چرا که با اجراي این روش در مواقع شلوغ، به عنوان مثال در یک نانوایی سنگک، ممکن است قبل از سرویسدهی به یک نفر با تقاضاي 7 عدد به 10 نفر با تقاضاهاي پائین تر که بعد از او آمدهاند، سرویس داده شود که این موضوع در حال حاضر براي عموم پذیرفتنی نیست. به همین دلیل پس از اجراي الگوریتم بالا، به مدت سه روز آن را اصلاح کرده و به جاي نسبت زمان انتظار به حجم تقاضا، از نسبت دیگري با عنوان زمان انتظار تقسیم بر عددي مرتبط با تعداد تقاضا به اضافه یک ثابت مشخص، استفاده شد( مقدارk در معادله 3) که به هرحجم تقاضا یک k مناسب و متفاوت با دیگري اختصاصمی یابد، که در این روش نسبت زمان انتظار با تعداد وجودنداشت. به طور مثال متقاضی دو عدد حدودا 2 برابر یکیو شش تایی، دو برابر دو تایی منتظر میماند. در ادامه به بررسی و مقایسه سه روش اولویت دهی در صف نانوایی پرداخته شده و نتایج حاصل از اجراي عملی مکانیسم ارایه و مورد بحث قرار گرفته است.

روش آواس
در نانوایی اغلب چهار صف یکی آقایان، چند تایی آقایان، یکی خانمها و چندتایی خانمها وجود دارد که توسط نانوا سرویس داده میشود. طول هر یک از صفها به پارامترهاي زیادي وابسته است که از اساسی ترین آنها میتوان به ساعت و روز اشاره کرد. یکسان نبودن طول صفها سبب میشود تا افراد در بین صفهاي مختلف جابه جا شوند(از یکی به چندتایی و برعکس).
قبل از اعمال الگوریتم اولویتدهی مورد نظر، نمونه گیريهایی انجام شده است؛ اگر چه فاصله زمانی بین نمونه گیري تا پیادهسازي الگوریتم مورد نظر زیاد است و تغییرات زیادي در مدت زمان پخت و در نتیجه مدت زمان انتظار انجام گرفته است، اما در هر صورت این نتایج قابل تأمل است. این نمونهگیري براي دو صف زن و مرد انجام شده است. خلاصه نمونه برداري که در شش زمان مختلف از سه نانوایی انجام شده به شرح جدول 1 است.
همان طور که ملاحظه میشود، متوسط زمان انتظار در حالت کلی 9 دقیقه و 52 ثانیه و براي نانوایی سنگک نیز به طور تقریبی همین مقدار است. متوسط تعداد نان دریافتی در نانوایی سنگک 47,3 است. البته این در حالتی است که صف یکی، جدا بوده و به نوعی زمان انتظار تا حدي کاهش یافته است.

اجراي روش اولویتدهی بر اساس بالاترین امتیاز
براي اجراي الگوریتم پیشنهاد شده، سیستمی طراحی شد تا هنگام ورود افراد، زمان ورود و تعداد نان مورد نیاز را ثبت کرده و شمارهاي را با ذکر زمان ورود، تعداد نان مورد تقاضا و زمان تقریبی انتظار در اختیار مشتري قرار دهد. سپس با فشرده شدن کلیدي توسط شاطر که نشان-دهنده آماده بودن وي براي سرویسدهی به مشتري بعدياست، سیستم با استفاده از معادله(9)، (که همان معادله (4) با 1=k است)، امتیاز همه مشتریان موجود را محاسبهو از بین آنها مشتري با بالاترین امتیاز را به عنوان مشتري واجد شرایط براي سرویسدهی فراخوانی کند.
نحوه محاسبه امتیاز به این شرح است:
(9) تعداد/ (زمان ورود – زمان فعلی ) =امتیاز

جدول 1: خلاصه نتایج نمونهگیري در روش آواس
نمونه کل نان تعداد
دریافتی نمونه متوسط نان دریافتی متوسط
زمان انتظار مجموع زمان انتظار
سنگک مردانه 1 14 137 3,34 0:06:38 04:32:00
سنگک زنانه 1 22 85 3,86 0:5:49 02:02:00
لواش مردانه 2 47 753 16,02 0:11:35 08:58:00
لواش زنانه 2 16 305 19,06 0:8:40 02:19:00
لواش مردانه 3 43 653 15,18 0:8:13 05:53:00
لواش زنانه 3 13 259 1419,92 0:10:14 02:13:00
سنگک مردانه 4 49 170 3,47 0:7:25 06:11:00
سنگک زنانه 4 21 85 4,04 0:14:21 05:00:00
سنگک مردانه 5 44 133 3,02 0:12:17 08:59:00
سنگک زنانه 5 22 80 3,77 0:13:11 04:37:00
بربري مردانه 6 50 218 4,36 0:11:25 09:31:00
بربري زنانه 6 23 103 4,3 0:10:18 03:57:00
مجموع 391 2981 – – 64:17:00
متوسط زمان 0:09:52
متوسط زمان انتظار در یک نمونه براي زن و مرد برابر با 9 دقیقه و 23 ثانیه بوده که با اعمال الگوریتم جدید به مقدار 8 دقیقه و 10 ثانیه کاهش یافته که در این حالت 13% بهبود یافته است. دلیل بهبود 13% به جاي 20% جدا بودن صف یکی و چند تایی در قبل از اعمال این الگوریتم است. اگر چه این شیوه محاسبه با توجه به ثابت نبودن سرعت سرویسدهی از دقت خوبی بهره مند نخواهد بود، اما مقادیر متوسط به دست آمده قابل استناد است. لازم به ذکر است این روش روي تقاضاهاي قبلی انجام شده است که در صورت اطلاع مشتریان از اعمال این روش، نوع تقاضا نیز تغییر کرده و به طور قطع متوسط زمان انتظار کاهش بیشتري پیدا میکرد. با اجراي سیستم نوبتدهی، نمونهگیري نیز به عمل آمده است؛ اما شرایط نسبت به زمان نمونه برداري اولیه تغییر کرده است؛ به طوري که زمان پخت از دو ساعت به سه ساعت افزایش یافته و میزان شلوغی نیز تغییر کرده است. از بین مراجعه کنندگان براي تعدادي از آنها زمان خروج نیز ثبتشده و از آنها در مورد شیوه نوبتدهی نظرسنجی شدهاست. اگر چه تعداد نمونه بیشتر بوده، اما تعداد نان تاحدودي برابر با نمونه قبلی است. نکته قابل توجه اینکههمان طور که انتظار میرفت، متوسط نان دریافتی به طور محسوسی کاهش یافته و از 47/3 به 93/2رسیده است. زمان انتظار در این نمونه خاص برابر با زمان محاسبه شده به صورت تئوري از نمونههاي قبلی است، اما این موضوع تا حدودي اتفاقی است و با توجه به تغییرات انجام شده از نظر مدت زمان پخت و میزان مراجعه، دلیلی براي برابر بودن وجود ندارد. از 37نفر از مراجعه کنندگان به طور اتفاقی نظر سنجی شده است که از این تعداد 29 نفر گزینه خوب یا عالی، 5 نفر گزینه بد یا خیلی بد و 3 نفر گزینه متوسط را انتخاب کردند که میتوان گفت 78% نظر خوب، 13% نظر بد و 9% نیز نظر متوسط دادند. مشکل اساسی که در این حالت بروز کرد، این بود که تعدادي از افراد ناراضی (در حدود 1.5 %)، بسیار ناراضی بوده و بسیار معترض بودند. این حالت براي شاطر قابل پذیرش نبوده و به همین دلیل الگوریتم تصحیح شد. الگوریتم تصحیح شده در قسمت بعد معرفی میشود.

اجراي روش اولویتدهی اصلاح شده
با اجراي آزمایشی الگوریتم معرفی شده در قسمت قبل در مدت 3 روز، چنین نتیجهگیري شد که در شرایط فعلی و بدون فرهنگ سازي قبلی، این روش قابل پیادهسازي نیست و متصديهاي نانوایی مایل به استفاده از سیستمی که تنش زا باشد، نخواهند بود. بنابراین الگوریتم نوبتدهی اصلاح شد. با توجه به اینکه به طور عرفی مردم براي کسی که زودتر رسیده اولویت خاصی در نظر میگیرند، این موضوع نیز در نظر گرفته شد و براي شماره قبلی نسبت به بعدي نیز ارزش ویژهاي قائل شد. در الگوریتم اصلاح شده اولویت به بالاترین امتیاز داده میشود که از رابطه (10) محاسبه می شود:
Bi  ((l i)k1 )



قیمت: تومان


دیدگاهتان را بنویسید