Wir betrachten ein Computersystem mit 2 Prozessoren, die unterschiedlich seien können. Wir wollen ein großes Programm auf diesem Computer laufen lassen. Diese enthält verschiedene Module, die während der Ausführung interagieren. Die Kosten, die bei der Ausführung jedes Moduls auf den Prozessoren entstehen, seien vorher bekannt, und können für die beiden Prozessoren unterschiedlich seien. Diese notieren wir mit a_i b_i , für die Prozessoren i=1,2. Die Zuweisung verschiedener Module zu verschiedenen Prozessoren kann zu weiteren Kosten führen, da Interprozessorkommunikation notwendig werden kann. Seien c_i,j die Kosten, die entstehen, wenn Modul i und j auf verschiedenen Prozessoren laufen. Wir wollen eine Zuweisung der Module zu den beiden Prozessoren finden, so dass die Gesamtkosten aus Rechen und Interaktionskosten minimal sind. Wir kann man eine solche finden? Die folgende Tabelle gibt Beispieldaten. Bestimme anhand derer eine Kosten-minimale Zuweisung