A grid computing system consists of a group of programs and resources that are spread across machines in the grid. A grid system has a dynamic environment and decentralized distributed resources, so it is important to provide efficient scheduling for applications. Task scheduling is an NP-hard problem and deterministic algorithms are inadequate and heuristic algorithms such as particle swarm optimization (PSO) are needed to solve the problem. PSO is a simple parallel algorithm that can be applied in different ways to resolve optimization problems. PSO searches the problem space globally and needs to be combined with other methods to search locally as well. In this paper, we propose a hybrid-scheduling algorithm to solve the independent task-scheduling problem in grid computing. We have combined PSO with the gravitational emulation local search (GELS) algorithm to form a new method, PSO–GELS. Our experimental results demonstrate the effectiveness of PSO–GELS compared to other algorithms

چکیده

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

1-مقدمه

محاسبات شبکه در دهه 1990 توسط یک کمیته ابر محاسباتی معرفی شد که هدف آنها استفاده از منابع محاسباتی به گونه ای مناسب برای انجام محاسبات پیچیده با اشراف بر این حقیقت بود که این منابع به صورت جغرافیایی توزیع شده و پراکنده هستند. محاسبات شبکه امکان کنترل محدوده وسیعی از منابع توزیع شده و ناهمگن را به منظور اجرای محاسبات و کاربردهای داده متمرکز فراهم می آورد...