Testplanung für kerngestützte Systeme mittels gemischt-ganzzahliger linearer Programmierung

Wir präsentieren optimale Lösungen für das Problem der Testplanung für kerngestützte Systeme. Gegeben sind eine Menge von Aufgaben (Testmengen für die Kerne), eine Menge von Testressourcen (z.B. Testbusse, BIST-Hardware) und eine Testzugangsarchitektur. Wir bestimmen Startzeiten für die Aufgaben, sodass die gesamte Testanwendungszeit minimiert wird. Wir zeigen, dass das Entscheidungsproblem der Testplanung äquivalent zum Scheduling-Problem für m-Prozessor-Offene Werkstätten ist und daher NP-vollständig ist. Eine häufig vorkommende Fallvariante dieses Problems (m=2) kann jedoch in polynomialer Zeit gelöst werden. Für den allgemeinen Fall (m>2) präsentieren wir ein gemischt-ganzzahliges lineares Programmierungsmodell (MILP) für die optimale Planung und wenden es auf ein repräsentatives kerngestütztes System unter Verwendung eines im öffentlichen Bereich verfügbaren MILP-Lösers an. Darüber hinaus erweitern wir das MILP-Modell, um die optimale Auswahl von Testmengen aus einer Menge von Alternativen zu ermöglichen. Schließlich präsentieren wir einen effizienten heuristischen Algorithmus zur Handhabung größerer Systeme, für die das MILP-Modell möglicherweise unlösbar ist.