Papers Published

1. Chakrabarty, K, Test scheduling for core-based systems, Ieee/Acm International Conference on Computer Aided Design, Digest of Technical Papers, Iccad (December, 1999), pp. 391-394, IEEE [doi] .
   (last updated on 2022/12/30)

   Abstract:
   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.