Research On Release-Time Aware Divisible-Load Scheduling Models And Algorithms

With the rapid development of computer science and technology, the requirements for memory, computational speed and bandwidth are constantly increasing. A single computing node has been unable to meet the needs of many application scenarios, which led to the development of parallel and distributed computing. One of the key issues in parallel and distributed systems is finding an efficient task-scheduling strategy so that the processing time of the entire workload could be minimized. However, designing an efficient task scheduling strategy under parallel and distributed systems is much more complex than under a single processor, because there are lots of factors need to be considered. Due to its complexity and importance, the designing efficient task-scheduling algorithms has become a hot topic in recent years.Divisible load theory(DLT) gives a simple, intuitive and effective idea of designing efficient task-scheduling algorithm, and gets a very good compromise between the simplicity and accuracy of scheduling models. Thus designing efficient task-scheduling algorithms becomes a hot topic in the research domain of parallel and distributed systems. This paper mainly focuses on studying divisible-load scheduling models and algorithms in parallel and distributed systems and the main works can be summarized as follows:1. Divisible load scheduling(DLS) in parallel and distributed system has been proven to be an NP-hard problem, and genetic algorithms(GAs), as a kind of random heuristic algorithm, have been widely used in solving a variety of NP-hard problems and achieved a great success. To solve the divisible-load scheduling problem with release times of processors, we build new models and design genetic algorithms in this paper. Experimental results show the effectiveness of the proposed models and the efficiency of the proposed algorithms.2. Most existing divisible-load scheduling models assume that all processors are idle at the beginning of workload assignment. However, in the real parallel and distributed systems, many processors may be still in the busy state when a new workload arrived. Processors may have different waiting time from the busy state to the idle, that is, processors have different release time. For the release-time aware divisible-load scheduling problems under homogeneous distributed systems, first a detailed analysis of divisible-load scheduling under three different time constraints is made, and then a novel release-time aware divisible-load scheduling model with hybrid time constraints is proposed. To solve the proposed model, we design a new genetic algorithm. Experimental results show that the proposed algorithm can divide and distribute the workload to processors according to their release times, which avoids the waiting time of the workload computation, thus reducing the processing time of the entire workload.3. The realistic parallel and distributed systems are often composed by heterogeneous processors and the distribution sequence of processors plays a significant role in the processing time. For the release-time aware divisible-load scheduling under heterogeneous distributed systems, first a detailed analysis of divisible-load scheduling under three different time constraints in heterogeneous distributed systems is made. Then a new release-time aware divisible load scheduling model taking into account the optimal distribution sequence is proposed. To solve the model, an effective global optimal genetic algorithm is designed with new encoding scheme and genetic operators. Meanwhile, a new local search strategy is put forward in order to accelerate the convergence speed of the proposed algorithm. Experimental results show that compared with the existing scheduling algorithms, the proposed algorithm can obtain shorter processing time.