Research On New Models And Algorithms For Multi-Installment Divisible-Load Scheduling

As the magnitude of data processing becomes increasingly large, one single processor in traditional computer system is unable to meet the data processing requirements. Processing workloads on parallel and distributed systems is one of the significant ways to solve this problem. As task scheduling plays an important role in the processing time of workloads under distributed systems, studies on the effective task-scheduling strategies have drawn much attention recently.Divisible-load theory is a great approximation to a variety of real world applications, such as image recognition, large-scale polynomial multiplication, video trans-coding, signature searching in a networked collection of files and so on. It has the advantages of simple form, easy understanding and accuracy in theoretic approximation. This paper mainly focuses on the periodic multi-installment divisible-load scheduling problem in heterogeneous parallel and distributed systems. The main work is summarized as follows:1. The existing researches show that most of the task-scheduling problems are NP-hard problems. It is uncertain whether such problems can be solved by an algorithm with polynomial time complexity. Fortunately, intelligent optimization algorithms, such as genetic algorithms, are suitable for those problems, especially for task-scheduling problems. They can be used to obtain a near-optimal solution in a relatively reasonable time. In this paper, we surveyed the genetic algorithms including encode and decode schemes, crossover, mutation, selection and other genetic operators.2. We studied the existing periodic divisible-load scheduling algorithms under heterogeneous parallel and distributed systems, the most of them used the derivatives of the processing time function of the entire workload. However, the periodic divisible-load scheduling problems are discrete optimization problems and are non-differentiable. Thus these algorithms cannot be applicable to these problems. To overcome this shortcoming, we propose a new model and prove two properties in this paper that helps to determine the ranges of the two variable numbers. Based on this, a new fast periodic multi-installment scheduling algorithm is proposed. Experiment results show that the proposed algorithm can obtain the optimal numbers of processors and installments. So it can outperform the existing algorithm in the processing time.3. Most existing studies on the multi-installment scheduling are based on a given distribution sequence of processors. However, the distribution sequence of processors has a great impact on the processing time of workloads under heterogeneous parallel and distributed systems. Therefore, to get the minimal processing time, we have to find(1) the optimal load partition;(2) the optimal number of processors needed for workload computation;(3) the optimal number of installments;(4) the optimal distribution sequence of processors. To solve this problem, we established a new periodic multi-installment divisible-load scheduling model in this paper and proposed a new global optimization algorithm to solve this model. Experiment results show that compared to the existing algorithms, the proposed algorithm uses the fewer processing time.