An improved genetic algorithm for task scheduling in the cloud environments using the priority queues: Formal verification, simulation, and statistical testing

Cloud computing is a new platform to manage and provide services on the internet. Lately, researchers have paid attention a lot to this new subject. One of the reasons to have high performance in a cloud environment is the task scheduling. Since the task scheduling is an NP-Complete problem, in many cases, meta-heuristics scheduling algorithms are used. In this paper to optimize the task scheduling solutions, a powerful and improved genetic algorithm is proposed. The proposed algorithm uses the advantages of evolutionary genetic algorithm along with heuristic approaches. For analyzing the correctness of the proposed algorithm, we have presented a behavioral modeling approach based on model checking techniques. Then, the expected specifications of the proposed algorithm is extracted in the form of Linear Temporal Logic (LTL) formulas. To achieve the best performance in verification of the proposed algorithm, we use the Labeled Transition System (LTS) method. Also, the proposed behavioral models are verified using NuSMV and PAT model checkers. Then, the correctness of the proposed algorithm is analyzed according to the verification results in terms of some expected specifications, reachability, fairness, and deadlock-free. The simulation and statistical results revealed that the proposed algorithm outperformed the makespans of the three well-known heuristic algorithms and also the execution time of our recently meta-heuristics algorithm. (C) 2016 Elsevier Inc. All rights reserved.