Unter den kombinatorischen Optimierungsproblemen aus dem Operations Research Bereich nehmen die Verschnitt- und Pack-Probleme wegen ihrer großen Verbreitung beim Anwender eine wichtige Stellung ein. Insbesondere die Glasindustrie interessiert sich für schnelle und hochwertige Lösungen des 2-dimensionalen Verschnittproblems, wo es darum geht, unter Berücksichtigung von Guillotine-Schnitten eine Menge von vorliegenden Scheiben-Bestellungen aus möglichst wenig Glas-Rohlingen herauszuschneiden. Zur Lösung derartiger Probleme hat man häufig die Wahl zwischen exakten Verfahren mit inakzeptabler Rechenzeit und schnellen Heuristiken mit unbefriedigender Lösungsqualität.
Ziel dieses Projektes ist es, durch Verwendung einer neuen algorithmischen Methodik einen günstigeren Tradeoff zwischen Laufzeit und Qualität zu ermöglichen. Bei dem neuen Konzept handelt es sich um das Zusammenspiel von Maximum-Weight-Matchings in gewichteten Graphen mit (im VLSI-Bereich eingeführten) Formfunktionen. Hierdurch entsteht eine Heuristik, die im Gegensatz zu bisherigen Verfahren eine globale Sicht auf die zu schneidenden Rechtecke behält und durch einmalige Bestimmung eines Matchings aus n Rechtecken n/2 dicht gepackte Metarechtecke konstruiert. Die Iteration dieser ``Partnersuche'' soll in Varianten wie 2-Opt, Simulated Annealing und Backtracking gesteuert werden. Des weiteren ist eine wissensbasierte Parallelisierung vorgesehen.
Weiter Informationen zu diesem Thema gibts hier (Postscript, 35kB).