The Research Of The Task Scheduling Algorithm Based On Availability For Heterogeneous Systems

With the rapid development of computer technology, distributed heterogeneous system has become an effective tool to solve complex problems. Its main objective is to achieve the system-wide resources sharing by an interconnection network, and then through the efficient resource management and the task scheduling technology, we could improve resource utilization and system throughput to obtain a high performance system. Task management, task scheduling and resource management are three important basic functions in the distributed heterogeneous systems. As one of these three important basic functions, task scheduling is a very important component to determine the system performance. It aims at scheduling a set of partially ordered computational tasks onto a multiprocessor system by a given strategy in order to obtain a better system performance. Because it can't be finished in polynomial time, the scheduling problem is known to be NP-hard.In the classical scheduling theory, the basic assumption is that all machines are always available for processing. This assumption might be reasonable in some cases, but when there are certain breakdowns, maintenance requirements, or other constraints, which make the machines unavailable for processing, it becomes not valid. In addition, the makespan is also an improtant factor that affects the system performance. As a result, when we want to design a scheduling, we could take into account availablity and makespan to improve the system performance. This paper includes two aspects. First, inspired by the genetic alggorithm, we propose a task scheduling algorithm based on availability. In this algirhtm, we assume that all tasks are independent of each other, and different nodes have different computing power and availability requirements, and then, different tasks own different execution time on different nodes, too. Based on above hypothesis, next, we create the new system architecture model and task model. And genetic operators are also re-designed. Experiments prove that the new algorithm is effective. Because we consider availability and makespan at the same time in this paper, it brings some trouble to us. Since availability and makespan are two conflicting objectives, that is because if we want to improve one of these two issues, another objective will be influenced, and it is difficult to achieve balance for the results of many algorithms. So we also present an optimization strategy to solve this problem. Then we call the optimization strategy within our new algorithm and another exeixting algorithm. Experimental results show that the optimization strategy provides noticeable improvement.