زمانبندی ایستای وظایف و تخصیص آن به منابع در سیستم محاسباتی گرید با استفاده از الگوریتم جستجوی گرانشی

مسیله تضمین کیفیت سرویس به کاربران گرید از طریق رزرو نمودن پیشاپیش منابع فراهم می شود. رزرو نمودن پیشاپیش، مکانیسمی است که توانایی تخصیص منابع به کاربران را براساس توافق بر روی نیازمندی های کیفیت سرویس و افزایش تعداد درخواست های پذیرفته شده کاربران در سیستم گرید فراهم می کند. زمانبندی و رزرو نمودن پیشاپیش منابع در گرید یک مساله NP-complete است، پس نمی توان از الگوریتم های قطعی برای بهبود آن استفاده نمود. روش های هیوریستیک برای این منظور عبارتند از الگوریتم ژنتیک، سرمایش شبیه سازی شده، تپه نوردی و روش های جستجوی دیگر. در این مقاله روش هیوریستیک جدیدی به نام الگوریتم جستجوی تصادفی تقلید نیروی گرانشی GELS برای حل مساله زمانبندی و رزرو نمودن پیشاپیش منابع در گرید را نشان می دهیم. این الگوریتم بر پایه مفاهیم جستجوی تصادفی، دو تا از چهار پارامتر اصلی سرعت2 و نیروی گرانشی3 در فیزیک استفاده می نماید. الگوریتم پیشنهادی راGELSAR4 نامیده و برای تصدیق آن، الگوریتم را پیاده سازی نموده و با الگوریتم ژنتیک مقایسه نموده ایم. بر اساس نتایج بدست آمده مشاهده می شود که تعداد کارهای رزروشده نسبت به الگوریتم ژنتیک 7.5 درصد افزایش یافته و نیز زمان اجرای الگوریتم تا 50 درصد کاهش می یابد.

Keywords:

تعویض , رزرو منابع , زمانبندی وظایف , سرعت , قانون نیوتن , نیروی گرانشی