عنوان انگلیسی مقاله :
Sort-Mid tasks scheduling algorithm in grid computing
عنوان فارسی مقاله :
چکیده
زمانبندی وظایف در منابع ناهمگن که در یک سیستم محاسبات شبکه ای توزیع شده اند، یک مساله NP-کامل است. هدف اصلی بسیاری از محققان، توسعه الگوریتم های زمانبندی متنوع برای بهینه سازی این کار است، و این الگوریتمها در زمانبندی وظایف با توجه به انتخاب منابع عملکرد خوبی داشته اند. اما استفاده از توان کاملِ منابع هنوز هم یک چالش محسوب میشود. در این مقاله یک الگوریتم اکتشافی جدید به نام Sort-Mid ارائه میشود. هدف این الگوریتم، حداکثر کردن استفاده از ماشینها و حداقل کردن makespan است. استراتژی جدید Sort-Mid پیدا کردن منابع مناسب است. مرحله اصلی، میانگین گیری بوسیله لیست مرتب سازیِ زمان تکمیل هر وظیفه است. سپس بیشترین میانگین به دست می آید. در نهایت، وظیفه ای که بیشترین میانگین را دارد به ماشینی اختصاص مییابد که کمترین زمان تکمیل را دارد. وظیفه ی اختصاص داده شده حذف میشود، و این مراحل تا زمانی که تمام وظایف تخصیص یابند، تکرار میگردد. آزمایشات نشان می دهند که کارایی الگوریتم پیشنهادی از نظر استفاده از منابع و makespan تقریباً از الگوریتم های دیگر بیشتر است.
Abstract
Scheduling tasks on heterogeneous resources distributed over a grid computing system is an NP-complete problem. The main aim for several researchers is to develop variant scheduling algorithms for achieving optimality, and they have shown a good performance for tasks scheduling regarding resources selection. However, using of the full power of resources is still a challenge. In this paper, a new heuristic algorithm called Sort-Mid is proposed. It aims to maximizing the utilization and minimizing the makespan. The new strategy of Sort-Mid algorithm is to find appropriate resources. The base step is to get the average value via sorting list of completion time of each task. Then, the maximum average is obtained. Finally, the task has the maximum average is allocated to the machine that has the minimum completion time. The allocated task is deleted and then, these steps are repeated until all tasks are allocated. Experimental tests show that the proposed algorithm outperforms almost other algorithms in terms of resources utilization and makespan
