بخشی از مقاله
چکیده
یکی ازمسائلی که درگریدهای امروزی بسیار مورد توجه است، زمانبندی فعالیتها بر روی شبکه گرید برای اجرای بهینه از نظر زمان اجراست دراین مقاله علاوه بر اینکه زمان اتمام کارها در نظرگرفته شده، به مسئله قابلیت اطمینان منابع نیز پرداخته شد. در این مقاله ابتدا مدلی برای محاسبه قابلیت اطمینان در شبکه گرید ارایه شده و سپس با استفاده از الگوریتم بهینهسازی ازدحام ذرات روشی برای زمانبندی فعالیتها جهت نیل به اهداف متضاد حداقل کردن زمان اتمام کارها و افزایش قابلیت اطمینان منابع محاسباتی ارائه گردید این روش را با نتیجه شبیهسازی دو الگوریتم موفق LAGA و HBMO مقایسه نمودهایم و نتایج برتری الگوریتم پیشنهادی به میزان0/1275 نسبت به الگوریتم LAGA و0/1325 نسبت به الگوریتم HBMO را نشان می دهد.
-1 مقدمه
یکی از مسائلی که درگریدهای امروزی بسیار مورد توجه است، زمانبندی فعالیتها بر روی شبکه گرید برای اجرای بهینه از نظر زمان اجراست3]،2،[1، چرا که منابع گرید معمولا بسیار کمتر از درخواستها برای استفاده از آن است. در راستای افزایش بهرهوری شبکه گرید و همچنین کاهش زمان اجرای فعالیتها بر روی آن، نیاز است به مفهومی بنام قابلیت اطمینان1 نیزپرداخته شود6]،5،.[4 قابلیت اطمینان در یک تعریف ساده عبارت است از احتمال عدم بروز خرابی دریک بازه زمان خاص 8]،.[7 لذا برای محاسبه آن میتوان معیاری به نام نرخ خرابی را برای هریک ازمنابع موجود در شبکه گرید مانند لینکهای ارتباطی، تجهیزات مسیریابی شبکه،منابع محاسباتی و ... درنظرگرفت. با استفاده از این معیار احتمال عدم خرابی را میتوان محاسبه کرد.
بررسی قابلیت اطمینان در زمانبندیها اثر قابل مشاهدهای خواهد داشت، چرا که اگر برای مثال یک راهحل زمانبندی خاص دارای زمان اجرای بسیار پایین و مناسبی باشد اما احتمال خرابی در آن بالا باشد، بصورت متوسط زمان اجرای فعالیتها در آن بسیار بالاتر از حد تصور خواهد بود، چرا که همزمان با خرابی یک منبع در شبکه گرید همه محاسبات صورت گرفته از بین خواهد رفت حتی اگر اجرای فعالیتها در مراحل پایانی باشد. لذا نیاز خواهد بود که کل فرایند اجرای فعالیتها مجدد شروع گردد، که در نهایت زمان اجرای فعالیتها را بسیار بالاتر از حد تصور خواهد برد.
بنابراین لازم است در روشهای زمانبندی فعالیتها بر روی شبکه گرید، قابلیت اطمینان نیز لحاظ گردد تا در نهایت بتوان متوسط اجرای فعالیتها را کاهش دهد، یا به عبارتی اعتبار راهحلهای زمانبندی ارائه شده را با افزایش دقت آنها در تخمین زمان متوسط پایان فرایند اجرا افزایش داد. از آنجا که بیشینه سازی قابلیت اطمینان و کمینه سازی زمان اجرا دو فعالیت متناقض هستند[18-16]، لذا برای رسیدن همزمان به این دو هدف نیاز است روشی برای ایجاد تعادل2 بین آنها مورد استفاده قرار گیرد.
در روشهای مختلف که مدلهای متفاوتی نیز دارند راههای مختلفی برای رفع این مشکل مورد استفاده قرار گرفته است. در برخی موارد محققان بیشترین تلاش خود را بر بهینهسازی زمان اجرا قرار داده اند و تنها در مواردی که دو راه حل زمان اجرای یکسانی دارند موردی را استفاده میکنند که قابلیت اطمینان بیشتری دارد که در عمل این روش کارایی مناسبی از خود نشان نداده است. روش دیگری که مورداستفاده محققان بوده استفاده از یک حد آستانهبرای زمان اجرا است.
به این صورت مثلا فرض میشود برای یک مجموعه از فعالیتهای خاص، راه حل پیشنهادی نباید بیش از صد ثانیه زمان نیاز داشته باشد. سپس از میان راهحلهایی که کمتر از صد ثانیه زمان نیاز دارند راهحلی که بیشترین قابلیت اطمینان را دارد مورد استفاده قرار میگیرد. اماروشی که در این پایاننامه مورد استفاده قرار گرفته است به این شکل است که برای هرراه حل دومعیار زمان اجرا و قابلیت اطمینان به صورت نرمال شده امتیازبندی مستقلی دارند. سپس این دو امتیاز با ضرایبی که برای هر یک درنظر گرفته میشود با یکدیگر جمع میگردند تا درنهایت امتیازی بین صفر و یک برای هر راهحل بتوان درنظر گرفت. با این روش بنا به نظرکاربر گرید میتوان اهمیت نسبی زمان اجرا به قابلیت اطمینان یا برعکس را افزایش داد.
-2 کارهای انجام گرفته
در مطالعات مختلفی که محققان بر روی مسئله بهینه سازی زمان اجرا و قابلیت اطمینان در محیط گرید صورت دادهاند اکثرا ابتدا یک مدل برای محاسبه قابلیت اطمینان هر راه حل زمانبندی پیشنهاد کرده وسپس با استفاده از انواع روشهای بهینه سازی روشی را برای استفاده از آن مدل بکار گرفتهاند. از آنجا که یافت بهترین چینش ممکن بر روی شبکهای از منابع غیرهمگن برای دستیابی به بهترین کارایی وبیشترین قابلیت اطمینان مسئلهای NP-Hard است 14]،[13، لذا همه مطالعات صورت گرفته تا بحال سعی در استفاده از نوعی الگوریتمهای اکتشافی برای یافتن جواب مناسب داشتهاند.[19]در این بین میتوان به موارد متعددی اشاره کرد که برخی از آنها از روشهای اکتشافی لیستی استفاده کردهاند [14] ودر اکثر موارد نیز از روشهای مبتنی برای الگوریتمهای ژنتیک استفاده شده است .[15]
