Research On Release Time Aware Divisible Load Scheduling Models And Algorithms

With the rapid development of computer technology and applications and the growing functional requirements in the field of information science, a single computing node has been unable to meet many great challenging issues, and more powerful and higher-speed computer systems are needed urgently, thus workstation clusters, grid, wireless sensor networks and other network-based parallel and distributed systems emerged. Efficient task scheduling algorithm is the premise of fully utilizing resources of network platforms. Meanwhile, since the tasks in the network, which can be computationally intensive or data-intensive, are complex and diverse, how to reasonably schedule the complex application tasks to each node in the system in order to achieve the shortest task finish time is a very critical issue to improve the quality of service and system performance.Divisible load theory(DLT) gives a simple method which can get the closed-form solutions of optimal scheduling under some conditions. Due to its comprise between simplicity and accuracy, divisible load scheduling in parallel and distributed systems has become a hot research topic in the field of scheduling. This paper mainly focuses on studying divisible load scheduling models and algorithms in parallel and distributed systems and the main works are as follows:1. Divisible load scheduling(DLS) in parallel and distributed system has been proven to be NP-hard problem, and genetic algorithm(GA), as an effective algorithm to solve the optimization problems, has been widely used in a variety of NP-hard problems. This paper first introduces the basic principle and framework of genetic algorithm, and mainly studies the divisible load scheduling algorithm based on GA in parallel and distributed systems.2. Most existing scheduling models assume that all processors are idle at the beginning of workload assignment. In fact, in the real parallel and distributed environments, many processors may 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. Our studies are all based on the assumption that the processors inthe system have different release time.3. By studying the divisible load scheduling in homogeneous system, a detailed analysis of divisible load scheduling under three different time constraints in homogeneous star networks is made, and then a novel release time aware divisible load scheduling model with hybrid time constraints is proposed. This paper designed an effective genetic algorithm to solve it. Experimental results show that, compared with the existing exhaustive algorithm, the proposed algorithm can find the optimal solution efficiently and accurately, thus proving the feasibility of the algorithm.4. Taking into account the existence of heterogeneous platforms in parallel and distributed system environments, release time aware divisible load scheduling in heterogeneous star networks is studied and analyzed, and a novel divisible load scheduling optimization model with hybrid time constraints is proposed. An effective global optimal genetic algorithm with new encoding scheme and genetic operators is designed to solve it, and meanwhile a new local search strategy is put forward in order to accelerate the convergence speed. Theoretical analysis and experimental simulation results show that, compared with several existing scheduling algorithms, the proposed algorithm can get better scheduling scheme, which demonstrates the effectiveness of the proposed algorithm.