با توجه به مطالبی که در این فصل مورد بررسی قرار گرفت استفاده از روشهای تکاملی میتواند یک راهحل مناسب برای حل مسئله زمانبندی باشد. اگرچه زمان اجرایی این روشها نسبت به روشهای حریصانه بیشتر است ولی به جواب، به مراتب بهتری نسبت به روشهای حریصانه دست پیدا میکنند. با همین رویکرد برای حل مسئله زمانبندی از الگوریتم ژنتیک برای حل مسئله زمانبندی استفاده شده و از روشهای ارائه شده توسط Nesmachnow و همکارانش [34,35] که در سالهای 2011 و 2012 ارائه شده است ایده گرفته شده است.
الگوریتمهای پیشنهادی
4-1 مقدمه
در این فصل روشهای پیشنهادی برای حل مسئله زمانبندی را بیان میکنیم. برای حل مسئله زمانبندی 5 راهکار را پیشنهاد میدهیم که 2 مورد مربوط به روشهای حریصانه، 2 مورد مربوط به الگوریتمهای توازن و یک روش ترکیبی از الگوریتم ژنتیک به همراه الگوریتم توازن میباشند. در ادامه به بررسی جزئیان این روشها میپردازیم.
روش پیشنهادی اصلی ترکیبی از یک جستجوی محلی (الگوریتم توازن) و الگوریتم ژنتیک میباشد. جستجوی محلی یک راهحل را دریافت کرده و با جابجایی و انتقالهایی که صورت میدهد سعی میکند زمان اتمام آخرین کار را برای راهحل مربوطه کاهش داده و باعث ایجاد توازن بار روی ماشینها گردد به نحوی که زمان اتمام کلیه ماشینها را به هم نزدیک کند. جستجوی محلی عملکرد خوبی در ایجاد توازن بار دارد ولی باعث کاهش چشمگیری در زمان اتمام نمی شود و عملکردش وابسته به راهحلی میباشد که به عنوان ورودی پذیرفته است. برای اینکه جستجوی محلی بتواند تاثیر خود را روی کاهش زمان اتمام نیز داشته باشد، بایستی راهحلهای مناسبی را به عنوان ورودی دریافت کند تا نتیجه مطلوبی را داشته باشد. تنوع راهحلهای ورودی به جستجوی محلی میتواند خروجیهای متفاوتی را داشته باشد و باعث کاهش یا افزایش زمان اتمام آخرین کار شود. برای اینکه راهحلهای متفاوتی را تولید و به جستجوی محلی واگذار کنیم از الگوریتم ژنتیک استفاده میکنیم. الگوریتم ژنتیک به دلیل ساختارش کمک میکند تا راهحلهای متنوعی را تولید نمائیم و این مسئله میتواند به هر چه بهتر عمل کردن جستجوی محلی کمک نماید. در روش ارائه شده سعی میکنیم از مزایای الگوریتم ژنتیک نیز استفاده کنیم و صرفا برای تولید یکسری راهحل، بکار گرفته نمیشود. در ادامه ابتدا فرضیات و تعاریف مهم را آورده وسپس دو الگوریتم حریصانه ارائه شده برای زمانبندی کارهای دستهای را مورد بحث قرار میدهیم، پس از آن دو روشی را که برای ایجاد توازن بار به کار بردهایم را مورد بررسی قرار میدهیم و در آخر الگوریتم اصلی که ترکیبی از الگوریتم ژنتیک و جستجوی محلی میباشد را ارائه میکنیم. برای پیادهسازی الگوریتم ژنتیک از روشهای که توسط Nesmachnow و همکارانش[34,35] که در سالهای 2011 و 2012 برای الگوریتم ژنتیک ارائه شده است، استفاده میکنیم.
4-2 فرضیات و تعاریف
فرض کنید نشان دهنده یک مجموعه n تایی از کارهای مستقل از یکدیگر و نشان دهنده یک مجموعه m تایی از منابع در محیط گرید محاسباتی میباشد.
در زمان شروع تمام منابع و کارها جهت پردازش در دسترس میباشند. زمان مورد انتظار پردازش برای هر کار روی هر منبع، در ماتریس ETC قرار دارد. ماتریس ETC یک ماتریس n*m میباشدکه n تعداد کارها و m تعداد منابع میباشد. ETC (i,j) نشاندهنده زمان مورد انتظار پردازش کار i روی ماشین j میباشد. زمان اتمام کار i، طبق فرمول (1) محاسبه می شود
(1)
نشاندهنده میزان حجم کار منبع j ، قبل از شروع پردازش کار i میباشد (زمانی که کار i بایستی روی منبع j منتظر بماند تا شروع به اجرا کند).
جهت ارزیابی کیفیت الگوریتم های زمانبند معیارهای متفاوتی موجود است که متداولترین معیارها عبارتند از :
زمان اتمام آخرین کار: محبوب ترین معیار بهینهسازی به حداقل رساندن زمان اتمام آخرین کار میباشد. این معیار توان سیستم گرید، را نشان میدهد. زمان اتمام آخرین کار طبق فرمول (2) محاسبه میشود.
(2)
مجموع زمان اتمام کلیه کارها: این زمان کیفیت خدمات سیستم گرید را نشان می دهد. زمان اتمام کلیه کارها طبق فرمول (3) محاسبه میشود.
(3)
بهره وری منابع (سودمندی منابع): این معیار توازن بار سیستم گرید را نشان میدهد. بهره وری منابع طبق فرمول (4) محاسبه میشود.
(4)
نشان دهنده میزان حجم کار منبع j میباشد.
برای حل مسئله زمانبندی الگوریتمهای Asuffrage، MaxSuffrage، دو الگوریتم توازن و یک الگوریتم ترکیبی را ارائه کردهایم که به شرح آنها میپردازیم.
4-3 الگوریتم پیشنهادی Asuffrage
در الگوریتم حق رای هزینه هر کار را براساس اختلاف مابین دومین کمترین زمان اتمام و اولین کمترین زمان اتمام محاسبه میشود و کار با بالاترین اختلاف انتخاب میگردد؛ در واقع الگوریتم حق رای فقط یک مرحله بعد را در انتخاب کار در نظر میگیرد و ضرری را که به واسطه انتخاب نشدن بهترین منبع برای کار متحمل میشویم را معیار ارزیابی قرارداده و با توجه به این فاکتور کارها را به منابع واگذار میکند.
در الگوریتم پیشنهادی (Asuffrage) سعیمی کنیم افق دید خود را گسترش داده و به جای ملاک قراردادن یک مرحله بعد، تعدادی از مراحل را در تصمیم گیری دخیل کنیم. در هر دور به جای زمان اتمام دومین کمترین زمان اتمام، میانگین زمان اتمام را برای کار i روی منابع موجود بدست میآوریم (فرمول (6)) تا بتوانیم بازه تغییرات زمان اتمام را در تصمیمگیری دخالت دهیم. جهت اولویتدهی به کارهایی که سریعتر به مرز میانگین تغییرات خود نزدیک می شوند، تعداد منابعی که زمان اتمامشان کمتر از میانگین زمان اتمام برای کار i میباشد را شمارش مینمائیم (فرمول (8)) و عدد بدست آمده را در اختلاف میانگین زمان اتمام (فرمول (6)) و کمترین زمان اتمام (فرمول (7)) ضرب میکنیم (فرمول (5)) تا اولویت کارهایی که زودتر به مرز میانگین تغییرات میرسند بیشتر شود.
(5)
(6)
(7)