Multi-objective league championship algorithm for real-time task scheduling
- PDF / 782,707 Bytes
- 12 Pages / 595.276 x 790.866 pts Page_size
- 88 Downloads / 242 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL ARTICLE
Multi-objective league championship algorithm for real-time task scheduling Saroja Subbaraj1
•
Revathi Thiagarajan1 • Madavan Rengaraj2
Received: 15 July 2018 / Accepted: 18 December 2018 Springer-Verlag London Ltd., part of Springer Nature 2019
Abstract League championship algorithm is a recently proposed population-based evolutionary algorithm for finding global optimal solutions in continuous optimization problems. The proposed work adopts the algorithm by modifying the team formation step for solving real-time task scheduling problem in heterogeneous multiprocessors. Two different objectives: tardiness and energy consumption were considered for scheduling. Our proposed algorithm is implemented using Java and tested using the graphs generated by the benchmark tools: task graph for free and task graph generator. Simulation results prove the performance of the proposed algorithm is better in terms of the objective functions over the other existing metaheuristic algorithms such as genetic algorithm, ant colony optimization and particle swarm optimization. Keywords Heterogeneous multiprocessors Global optimum Scheduling
1 Introduction Recently, most of the applications pertaining to either scientific or industrial domain have a demand to receive the results in clear-cut deadline. This imposes the developers to solve such applications by exploiting the parallelism offered by multiprocessors. Over the past several decades, chip manufacturers are producing heterogeneous multiprocessors, with each core customized for a different subset of application characteristics, no single core is well suited for all applications [1]. Hence, to exploit its power to the greater extent, input tasks need to be mapped wisely to the right core. Scheduling is the process determines where and when to allocate the tasks. Task scheduling on multiprocessors has been shown to be an NP-HARD problem [2]. During the initial days, scheduling has a single objective: completing the given job before its deadline (if it is real time) or to complete the job as early as possible. In addition to this objective, nowadays, the objectives of the & Saroja Subbaraj [email protected] 1
Department of Information Technology, Mepco Schlenk Engineering College, Sivakasi, India
2
Department of Electrical and Electronics Engineering, PSR Engineering College, Sivakasi, India
scheduling are manifold: energy consumption, temperature, reliability, tardiness, utilization and so on. Hence, this makes the researchers formulate scheduling as a multiobjective problem. Scheduling algorithms can be classified as a list based [3–6] or clustering based [7–12]. Also, they may be classified into static [13–16] or dynamic [17, 18]. In the static scheduling, all characteristics of a task such as arrival time, execution time are known in advance, whereas in case of dynamic scheduling, these are not known. The proposed work focuses on static scheduling and hence all the parameters are known. There exist m
Data Loading...
