زمانبندي وظايف در سيستم محاسباتي گريد با استفاده از الگوريتم جستجوي گرانشي

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