Two Styles Of Hybrid Genetic Algorithms For Task Scheduling Problem In Optical Network Based On Distributed Computing System

In this paper, we introduce the scheduling algorithms for optical network based distributed computing system, which is able to provide services for many advanced applications such as e-science applications, collaborative design, virtual reality, etc. The optical network based distributed computing system interconnects the distributed computing resources with optical network which dynamically provides high bandwidth connection among equipments and resources such as supper computer, storage arrays and so on with low latency.Among the challenges the optical network based distributed computing system faces, we study the task scheduling algorithms in this paper. Due to the limit resources in optical grids and the large requirements from users, it is important to improve the system performance. Besides, the cost of these resources is very high and operating costs for dedicated high-speed optical networks is very expensive, so to execute the applications that users submit as soon as possible means the lower costs for users. So we need an efficient task scheduling algorithm for the optical network based distributed computing system.First, we establish the model of task scheduling which is the DAG model based on task flow for the optical network based distributed computing system. Then we classify the problem to resource constrained project scheduling problems and also introduce the resource constrained project scheduling problems. After the description of the problem, the existing study situation for this problem is introduced. We also present two types of greedy algorithm: the extended list scheduling algorithm and the scheduling critical path algorithm in this article.We present two types of hybrid Genetic Algorithm after the introduction of existing algorithm for scheduling problem of optical network based distributed computing system. One is hybrid genetic algorithm which is based on priority. We design two hybrid genetic algorithms according to task weight and communication weight. The other is weighted hybrid genetic algorithm based on ELS(extended list scheduling).First algorithm is a genetic algorithm which uses the task weight which is represented by node and the communication weight which is represented by directed edge to encode. Then it is sorted by the coding. This algorithm is able to schedule tasks according to the actual execution cost of tasks. We construct a simulator to perform the experiment and evaluate the performance of proposed algorithms. We compare the performance of different algorithms on a simple system with the optimal results calculated by exhaustive algorithm. We also compare the performance of different algorithms on more complex systems. All the experiments prove that the mixed weight hybrid genetic algorithm is able to calculate a better schedule result.Second algorithm is a hybrid algorithm which uses the idea of extended list scheduling algorithm to sort. This algorithm also uses the task weight and communication weight to encode, and is sorted by the bottom level. We also construct a simulator to analyze proposed algorithms. We also compare the performance of different algorithms on more complex systems. All the experiments prove that the mixed weight hybrid genetic algorithm based on ELS is able to calculate a better schedule result than greedy algorithm. Experiments also prove that mixed weight hybrid genetic algorithm based on ELS costs less time complexity than mixed weight hybrid algorithm and general hybrid algorithms which are used to resolve this problem.