Der Fachbereich Mathematik der TUD veranstaltet in Zusammenarbeit mit dem Zentrum für Mathematik regelmäßig Schülermodellierungswochen. Das folgende Problem wurde während der Modellierungswochen 8. Oktober - 13. Oktober 2000 in Höchst bearbeitet.

Verdrahtung elektronischer Schaltungen

(© Fachbereich Mathematik, TU Darmstadt)

Die Firma Siemens entwirft hochintegrierte Schaltungen. Dabei werden zunächst rechteckige Funktionseinheiten (Zellen) auf der Chipfläche plaziert. Die Anschlüsse dieser Einheiten müssen dann in vorgegebener Weise miteinander verdrahtet werden. Damit sich Leitungen auch überkreuzen können, verlaufen sie in verschiedenen Schichten, die durch eine Art Loch (Via) miteinander verbunden werden können. Es gibt zwei Arten von Verdrahtungsgebieten:

Kanal-Verdrahtung (Channel-routing): In dem Bereich zwischen zwei nebeneinanderliegenden Funktionsblöcken, deren Abstand beliebig gewählt werden kann, müssen die Verbindungen gelegt werden.

Kasten-Verdrahtung (Switchbox-routing): Vier Funktionsblöcke begrenzen ein rechteckiges Gebiet, in dem sie verdrahtet werden müssen.

Für eine oder beide der Varianten sollen Methoden entwickelt werden, die möglichst schnell eine möglichst gute (aber nicht notwendigerweise die beste) Verdrahtung der Funktionsblöcke finden.

Beispiele für eine Kasten-Verdrahtung (Anschlüsse mit gleichen Nummern sollen verbunden werden).

Kastenverdrahtung

Kanalverdrahtung

Weiteres Material: Benshmarkprobleme in Form rechteckiger Gittergebiete des folgenden Typs, bei denen nur entlang der Gitterlinien verdrahtet werden darf.