• PDF / 2,574,322 Bytes
• 17 Pages / 595.276 x 790.866 pts Page_size
• 95 Downloads / 234 Views

DOWNLOAD

REPORT

---

RESEARCH PAPER

Hybrid approach based on cuckoo optimization algorithm and genetic algorithm for task scheduling Mehdi Akbari1  Received: 23 February 2020 / Revised: 17 June 2020 / Accepted: 8 August 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020

Abstract One of the most important issues in designing efficient scheduling algorithms in heterogeneous distribution systems is the reduction of execution time. In the proposed algorithm, the modified operators of the cuckoo optimization algorithm and the genetic algorithm are used to achieve a relatively optimal solution with fewer repetitions of the genetic algorithm and less execution time than the cuckoo optimization algorithm. The most important innovation in the proposed algorithm is the introduction of a new operator called spiral search, which increases the variety among the samples produced in each generation. The main idea of this operator is to replace linear search with the spiral search, which allows local search between similar schedules and accelerates the achievement of a relatively optimal answer. Also the multi objective function in the proposed algorithm is used to minimize makespan and maximize parallelization. The results obtained from the proposed algorithm on a large number of standard graphs with a various range of attributes show that it is superior to the other task scheduling algorithms. Keywords  Evolutionary algorithms · Task scheduling · Genetic algorithm · Cuckoo optimization algorithm · Meta-heuristic algorithms · Spiral search

1 Introduction

• The HACG-TS algorithm uses GA operators and COAs

The proposed evolutionary approach is the hybrid approach based on cuckoo optimization algorithm and genetic algorithm for task scheduling (HACG-TS). The main goal in the proposed algorithm is to arrive at a relatively optimal solution with a limited number of replicates. In order to get closer to optimal solution, we need to have a search space in which the variety of samples is maximized so that each generation can find the good samples. This section is done by genetic operators. On the other hand, search in the space of the problem should be done so that the algorithm does not stop in local optimums and it is possible to escape these local optimums in global search. COA operators provide global searches and prevent them from getting caught up in local optimums. The four major contributions of this proposed algorithm are listed below.

• Reducing the number of iteration and increasing the vari-

* Mehdi Akbari [email protected]; [email protected] 1



Faculty of Computer Engineering, Najafabad Branch, Islamic Azad University, Najafabad, Iran

together to create schedules.

ety of samples in the proposed algorithm by applying the functions of the GA and COA. • The proposed algorithm presents the new spiral search, which is promote diversity among the samples that will be produced in each generation. In the spiral search, the modification radius is initially more restrictive, so the search range is wider than the