Research On Parallel Test System Task Scheduling Based On Petri Nets And Ant Colony Algorithm

With the rapid development of modern science and technology, and widely use of computer technology, microelectronics and communications technology, it Makes the test system have been expanding, the structure of test system becomes more and more complicated, task scheduling of test system becomes a bottleneck which restricts system performance. Thus, the study of parallel test system task scheduling has become a hot research field of automatic test. Based on the above analysis, this paper studies the modeling of parallel testing system task scheduling process and task scheduling algorithm, through the analysis of the parallel test system task scheduling process, establishes the petri net model of task scheduling, and proposes the scheduling algorithm based on petri net modeling and ant colony algorithm. The main research contents are as follows:1. Contrary to the description, features and research status of the parallel test scheduling issue, this paper conducts a research and analysis. Then introduces the relevant theory of petri nets, and gives the general steps which to establish stochastic petri net model.2. Contrary to the insufficient which uses petri nets to analysis parallel test system task scheduling issue, the paper describes the principles and methods of task decomposition in parallel test system. Finally, to establish petri net model of the parallel test system task scheduling process, and through the simulation analysis to verify the feasibility, which to use petri nets to solve this problem.3. Contrary to the insufficient of pheromone when the standard ant colony algorithm searches in early stage that is easy to fall into local optima, and use petri nets to solve this problem easily lead to the state space information overload of model, through to improve the standard ant colony algorithm, then propose the task scheduling algorithm(P-ACO algorithm) which is based on ant colony algorithm and petri nets. In other words, one way is: the setting mode of restrict list for ant colony algorithm is changed by substituting the traditional restrict list, the probability selection rule of ant colony algorithm is improved by adding the constraint test of distribution into the selection rule. And the transitions which do not conform to the distribution restrain, ants do not choose this transition, thereby accelerating the speed of search; The other way is: at the beginning of search, when updating of the local pheromone, adding an attenuation factor, thus expanding the scope of the search, avoiding the algorithm to fall into local optima.Finally, through comparing with the simulation of three scheduling algorithms, the experimental results show that the P-ACO algorithm has a very good performance in the execution time and load-balancing capabilities, It proves the effectiveness of the algorithm.