High temperature has become a major problem for system-on-chip testing. In order to reduce the test application time while keeping the temperatures of the cores under test within safe ranges, a thermal-aware test scheduling technique is required. This paper presents an approach to minimize the test application time and, at the same time, prevent the temperatures of cores under test going beyond given limits. We employ test set partitioning to divide test sets into shorter test sequences, and add cooling periods between test sequences so that overheating can be avoided. Moreover, test sequences from different test sets are interleaved, such that the cooling periods and the bandwidth of the test bus can be utilized for test data transportation, and hence the test application time can be reduced. The test scheduling problem is formulated as a combinatorial optimization problem, and we use the constraint logic programming (CLP) to build the optimization model and find the optimal solution. As the optimization time of the CLP-based approach increases exponentially with the problem size, we also propose a heuristic which generates longer test schedules but requires substantially shorter optimization time. Experimental results have shown the efficiency of the proposed approach.