A multi-objectives scheduling algorithm based on cuckoo optimization for task allocation problem at compile time in heterogeneous systems |
| |
| Affiliation: | 1. Faculty of Computer and Information Technology Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran;2. Department of Mathematics and Computer Science, Allameh Tabataba''i University, Tehran, Iran;1. IBM Integrated Supply Chain, IBM Corporation, Poughkeepsie, NY 12601;2. Department of Industrial Engineering, Pennsylvania State University, The Behrend College, Erie, PA 16563;3. Department of Systems Science and Industrial Engineering, State University of New York at Binghamton, Binghamton, NY 13902;1. Universitat Politècnica de València, Camino de Vera s/n, 46022, Valencia, Spain;2. Universidad Tecnologica de la Mixteca, Oaxaca 69000, Mexico;3. University of Brescia, via Branze, 38, Brescia, Italy;1. Department of Physics and Computer Science, Faculty of Science, Dayalbagh Educational Institute, Dayalbagh, Agra 282005, Uttar Pradesh, India;2. Department of Electrical Engineering, Faculty of Engineering, Dayalbagh Educational Institute, Dayalbagh, Agra 282005, Uttar Pradesh, India;3. Dayalbagh Educational Institute, Dayalbagh, Agra 282005, Uttar Pradesh, India;1. Faculty of Computing and Informatics, Multimedia University, Persiaran Multimedia, Cyberjaya, 63000, Selangor, Malaysia;2. Universiti Sains Malaysia, Gelugor, 11800, Pulau Pinang, Malaysia |
| |
| Abstract: | To handle scheduling of tasks on heterogeneous systems, an algorithm is proposed to reduce execution time while allowing for maximum parallelization. The algorithm is based on multi-objective scheduling cuckoo optimization algorithm (MOSCOA). In this algorithm, each cuckoo represents a scheduling solution in which the ordering of tasks and processors allocated to them are considered. In addition, the operators of cuckoo optimization algorithm means laying and immigration are defined so that it is usable for scheduling scenario of the directed acyclic graph of the problem. This algorithm adapts cuckoo optimization algorithm operators to create proper scheduling in each stage. This ensures avoiding local optima while allowing for global search within the problem space for accelerating the finding of a global optimum and delivering a relatively optimized scheduling with the least number of repetitions. Moving toward global optima is done through a target immigration operator in this algorithm and schedules in each repetition are pushed toward optimized schedules to secure global optima. The results of MOSCOA implementation on a large number of random graphs and real-world application graphs with a wide range characteristics show MOSCOA superiority over the previous task scheduling algorithms. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
