Test scheduling and TAM optimization for core-based SoCs is a challenging problem. Test schedules must be crafted with the objectives of minimizing testing time to reduce test cost, under the constraints of total available TAM width. Moreover, precedence relations and power constraints must be met to ensure safe, effective, and high-quality testing. Prior research in test scheduling has mainly used constructive approaches such as rectangle packing to solve this problem, but these approaches fail to address the problem of creating a simple, standard representation for SoC test schedules that can be used by a wide range of optimization algorithms. In this paper, we present a novel and efficient method to represent SoC test schedules and TAM width assignment based on the use of k-tuples. The proposed approach provides a compact, standardized representation of test schedules. This facilitates fast and efficient evaluation of SoC test automation solutions to reduce test costs. We propose heuristic algorithms based on the use of k-tuples to solve scheduling problems for SoCs in an efficient manner; extensions to our method to incorporate precedence relations among tests and power constraints in the schedule are also presented. Finally, experimental results using the new ITC?02 SoC benchmarks validate the quality of our solutions.