We present a mathematical model for the problem of scheduling tests for core-based system-on-chip (SOC) VLSI designs. Given a set of tests for each core in the SOC and a set of test resources (e.g., test access mechanisms (TAM)), we determine the test plan for the application of the tests to the SOC. Test planning in this paper refers to the combined activities of test access architecture partitioning and test scheduling. These activities must be performed in conjunction as the choice of the test access architecture influences the test schedule. We justify the formulation of test scheduling w.r.t. minimum average completion time criterion as compared to minimum makespan. We show that then the problem of scheduling tests on TAMs can be mapped onto a graph theoretic problem which has a polynomial time optimal solution. We have implemented our algorithm as a test planner tool TPLAN. We present the theoretical analysis of our approach in this paper, and compare our results against those published earlier using integer linear programming techniques with encouraging results.