Research On Multi-objective Constraints P2P Task Scheduling Based On Genetic Algorithm

With the development of P2P networks, how to construct a distributed peer-to-peer network computing system with high performance, strong stability and good scalability has become a hot topic in recent years. Task scheduling is a key technology in distributed P2P computing, which direct impact on the computing performance of the entire P2P computing system. Task scheduling is that assigning a group of tasks which need to schedule to the processing nodes based on a certain strategy, it has been recognized as an NP-complete problem.At present, task scheduling can be divided into reliant task scheduling and parallel task scheduling based on different task models, the features of the P2P network make its task scheduling performance constrain by multi-factor, which includes the time of execute task, the time of communication between processing nodes, scheduling cost and so on. These factors must be considered in task scheduling based on P2P network.Aiming at solving the problem of multi-objective constraints reliant task scheduling, a task scheduling based on multi-objective genetic algorithm was proposed. A new double chromosome was designed which is used to solve the problem of genetic Algorithm bring illegal result when solve task scheduling, and the corresponding double genetic operate was also designed in order to avoid the illegal result. Execution time, task scheduling cost and communication time among nodes were selected as criteria to select the processing nodes, object function of execution time, task scheduling cost and communication time were constructed. Experimental results indicate the validity of the proposed scheduling strategy in shortening the execution time and communication time, as well as saving the scheduling costs.Aiming at solving the problem of multi-objective constraints parallel task scheduling, a task scheduling based on multi-attribute and combinatorial auction was proposed. Execution time, task scheduling cost and communication time among nodes were selected as criteria to determine the combinatorial auction winner from tenderee's perspective. Mathematical model of multi-attribute and combinatorial auction was established. A multi-partheno genetic algorithm, the new heurist chromosome and self-adaptive variation operator were designed in order to find the winner of combinatorial auction. Experimental results demonstrated that the task scheduling based on multi-attribute and combinatorial auction had better performances than the traditional methods.