A Johnson's-Rule-Based Genetic Algorithm for Two-Stage-Task Scheduling Problem in Data-Centers of Cloud Computing

One of the keys to making cloud data-centers (CDCs) proliferate impressively is the implementation of efficient task scheduling. Since all the resources of CDCs, even including operating systems (OSes) and application programs, can be stored and managed on remote data-centers, this study first analyzed the task scheduling problem for CDCs and established a mathematical model of the scheduling of two-stage tasks. The Johnson's rule was combined with the genetic algorithm to create a Johnson's-rule-based genetic algorithm (JRGA), which takes into account the characteristics of multiprocessor scheduling in CDCs. New crossover and mutation operations were devised to make the algorithm converge more quickly. In the decoding process, the Johnson's rule is used to optimize the makespan for each machine. Simulations were used to compare the performance of the JRGA with that of the list scheduling algorithm and an improved list scheduling algorithm. The results demonstrate the validity of the JRGA.