Test scheduling for core-based systems using mixed-integer linear programming

Journal Article (Journal Article)

We present optimal solutions to the test scheduling problem for core-based systems. Given a set of tasks (test sets for the cores), a set of test resources (e.g., test buses, BIST hardware) and a test access architecture, we determine start times for the tasks such that the total test application time is minimized. We show that the test scheduling decision problem 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 available in the public domain. 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.

Full Text

Duke Authors

Cited Authors

  • Chakrabarty, K

Published Date

  • October 1, 2000

Published In

Volume / Issue

  • 19 / 10

Start / End Page

  • 1163 - 1174

International Standard Serial Number (ISSN)

  • 0278-0070

Digital Object Identifier (DOI)

  • 10.1109/43.875306

Citation Source

  • Scopus