The production of semiconductor assembly and testing is wide variety, and the cost of produce time of switch between different products is not the same, which could lead to its utilization is lower, production cycle longer. Thus lot release control plays an important role for improving utilization and shorter production cycle for semiconductor assembly and testing system. In this paper, we modeled as a graph theory for solving constrained minimum spanning tree problem. Using mainstream Prim algorithm, we solve it to give each product sequence and specific lot release time. It have solved the extra time problem that caused by blinding lot release, and finally, through applied research we verified the effectiveness and superiority of it. The proposed strategy can reduce the change machine costs, shorten production cycle and improve production efficiency.