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 

 چکیده

زمانبندی وظایف در منابع ناهمگن که در یک سیستم محاسبات شبکه ­ای توزیع شده­ اند، یک مساله NP-کامل است. هدف اصلی بسیاری از محققان، توسعه الگوریتم­ های زمانبندی متنوع برای بهینه سازی این کار است، و این الگوریتم­ها در زمانبندی وظایف با توجه به انتخاب منابع عملکرد خوبی داشته ­اند. اما استفاده از توان کاملِ منابع هنوز هم یک چالش محسوب می­شود. در این مقاله یک الگوریتم اکتشافی جدید به نام Sort-Mid ارائه می­شود. هدف این الگوریتم، حداکثر کردن استفاده از ماشین­ها و حداقل کردن makespan است. استراتژی جدید Sort-Mid پیدا کردن منابع مناسب است. مرحله اصلی، میانگین­ گیری بوسیله لیست مرتب­ سازیِ زمان تکمیل هر وظیفه است. سپس بیشترین میانگین به دست می­ آید. در نهایت، وظیفه ­ای که بیشترین میانگین را دارد به ماشینی اختصاص می­یابد که کمترین زمان تکمیل را دارد. وظیفه­ ی اختصاص داده شده حذف می­شود، و این مراحل تا زمانی که تمام وظایف تخصیص یابند، تکرار می­گردد. آزمایشات نشان می­ دهند که کارایی الگوریتم پیشنهادی از نظر استفاده از منابع و makespan تقریباً از الگوریتم­ های دیگر بیشتر است.

-1مقدمه

سیستم­ های محاسبات شبکه [1،2]، سیستم ­های توزیع شده­ ای هستند که اشتراک منابع بزرگ را بین میلیون­ها سیستم کامپیوتری در یک شبکه جهانی مانند اینترنت امکان­پذیر می­سازند. منابع شبکه به دلیل پویایی، ناهمگن بودن، و توزیع جغرافیایی با منابع سیستم­ های پردازشی توزیع شده­ ی معمولی تفاوت دارند. زیرساخت­ شبکه (گرید) چهار سطح دارد. اول: سطح مبنا که از مولفه ­های فیزیکی تشکیل شده است. دوم: سطح میان افزار که در واقع نرم­ افزارِ مسئولِ مدیریت منابع، اجرای وظایف، زمانبندی وظایف، و امنیت است. سوم: سطح سرویس (خدمات) که خدمات کارامدی را به فروشندگان/کاربران ارائه می­کند. چهارم: سطح کاربرد که شامل خدماتی مانند ابزارهای عملیاتی و کسب و کار است.

زمانبندی به یکی از موضوعات تحقیقاتی اصلی تبدیل شده است زیرا بر کارایی اپلیکیشن­ های شبکه تاثیر مستقیم دارد. زمانبندی وظایف [3] مرحله اصلی مدیریت منابع شبکه است و با استفاده از الگوریتم­ها و سیاست­ های زمانبندی، کارها را مدیریت می­کند تا به منابع مناسب تخصیص یابند. در زمانبندی ایستا فرض می­شود اطلاعات تمام منابع و تمام وظایف، هنگام زمانبندی اپلیکیشن مشخص است. علاوه­ براین، هر وظیفه یک بار به یک منبع اختصاص می­یابد. اما در زمانبندی پویا، تخصیص وظیفه همزمان با اجرای اپلیکیشن انجام می­ شود و تعیین زمان اجرا در آن ممکن نیست. وظایف به صورت پویا وارد می­شوند و زمانبند باید برای تخصیص منابع، تصمیمات سختی بگیرد. مزیت زمانبندی پویا نسبت به زمانبندی ایستا این است که لازم نیست سیستم، رفتارِ زمان اجرای اپلیکیشن را قبل از اجرای آن بداند…