An improved Sort-Mid algorithm for scheduling heterogeneous grid tasks
Khamis, Soheir; Reda, Naglaa M.; Zakaria, Wael;
Abstract
Grid scheduling is one of the most known NP-complete problems. Heterogeneity of machines causes mapping of tasks to be a challenging problem. Several meta-heuristic algorithms have been designed to reach optimality as possible. Sort-Mid is a recent efficient scheduler of excellent resource utilization. Its strategy was based on computing the mean of two consecutive middle values in the sorted list of completion time. Thereafter, it maps the task with the maximum mean to the machine having the minimum completion time. However, Range-Suffrage scheduler obtains a better makespan. It was built on searching for the maximum average value of completion times among certain tasks. These tasks were selected according to their suffrage values under specified constraint. This paper proposes RSSM as highly efficient scheduler. It combines Sort-Mid and Range-Suffrage algorithms to achieve the maximum resource utilization and the minimum makespan. RSSM methodology is based on sorting only the completion time corresponding to tasks satisfying Range-Suffrage constraint. Experimental tests manifest the superiority of proposed algorithm over the two original meta- heuristics and other promising algorithms such as Min-Min.
Other data
Title | An improved Sort-Mid algorithm for scheduling heterogeneous grid tasks | Authors | Khamis, Soheir ; Reda, Naglaa M.; Zakaria, Wael | Keywords | Grid computing | Heuristic scheduling algorithm | Makespan | Range-Suffrage | Resource utilization | Sort-Mid | Issue Date | 15-Jul-2021 | Publisher | SPRINGER | Related Publication(s) | journal | Journal | Journal of Supercomputing | ISSN | 09208542 | DOI | 10.1007/s11227-021-03984-1 | Scopus ID | 2-s2.0-85110185179 | Web of science ID | WOS:000673897700003 |
Attached Files
File | Description | Size | Format | Existing users please Login |
---|---|---|---|---|
Khamis2021_Article_AnImprovedSort-MidAlgorithmFor.pdf | 2.5 MB | Adobe PDF | Request a copy |
Similar Items from Core Recommender Database
Items in Ain Shams Scholar are protected by copyright, with all rights reserved, unless otherwise indicated.