An optimal algorithm for serial test tasks scheduling based on matching theory

In automatic test system sometimes two serial tasks have to set the same state and test the same process repeatedly. So the test efficiency is very low. For this problem, a time relation model of serial test tasks based on graph theory was established. The relation of test sequence and test time is described by "graph", so the project problem is transformed into mathematics problem about graph theory. Based on the model, an optimal scheduling algorithm named MTS for serial test tasks was proposed. For many serial test tasks, the task sequence that has the shortest test time is found by using the algorithm, so the test time is reduced effectively. The algorithm was based on matching theory and its correctness and the feasibility were analyzed with theory and practical example. The algorithm was validated with experiment in actual system and the result showed the system's test efficiency was enhanced greatly.