OR

AG OR/ML - Prof. Dr. Andreas Drexl

ML


Das Verallgemeinerte Zuordnungsproblem


Das Verallgemeinerte Zuordnungsproblem (Generalized Assignment Problem, GAP) besteht darin, Jobs kostenminimal Prozessoren mit beschränkter Kapazität zuzuordenen. Das GAP ist NP-schwer. Es hat vielfältige Anwendungsmöglichkeiten, von denen einige dargestellt werden. Zur Lösung des GAP existieren zahlreiche Verfahren; nach wie vor können jedoch nur kleine "schwierige" Instanzen in vertretbarer Rechenzeit optimal gelöst werden. In dieser Arbeit wird gezeigt, dass die Ganzzahligkeitslücke mit einer neuen Klasse von Ungleichungen ("Extended Cover Inequalities") deutlich verkleinert werden kann.


back - Mathematics - OR - LNM - Theoretical Computer Science - Computer Science - University of Osnabrück.

B.Hammer