Test scheduling for core-based systems


Journal Article

We present optimal solutions to the test scheduling problem for core-based systems. We show that test scheduling is equivalent to the m-processor open-shop scheduling problem and is therefore NP-complete. However, a commonly-encountered instance of this problem (m = 2) can be solved in polynomial time. For the general case (m > 2), we present a mixed-integer linear programming (MILP) model for optimal scheduling and apply it to a representative core-based system using an MILP solver. We also extend the MILP model to allow optimal test set selection from a set of alternatives. Finally, we present an efficient heuristic algorithm for handling larger systems for which the MILP model may be infeasible.

Duke Authors

Cited Authors

  • Chakrabarty, K

Published Date

  • December 1, 1999

Published In

Start / End Page

  • 391 - 394

International Standard Serial Number (ISSN)

  • 1092-3152

Citation Source

  • Scopus