Reihenfolgeproblem

Ein Reihenfolgeproblem ist ein Optimierungsproblem wobei eine Lösung eines solchen Problems eine Permutation einer Menge M ist. Dementsprechend ist der Definitionsbereich D einer Wertelandschaft eines Reihenfolgeproblems die Menge aller Permutationen von M. Die Nachbarschaftsfunktion wird dann häufig so gewählt, dass zwei Permutationen dann als benachbart gelten, wenn man die Einträge an nur zwei Stellen der einen Permutation austauschen muss, um die andere Permutation zu erhalten. (Also zu (1,2,3,4,5) ist zum Beispiel (1,5,3,4,2) benachbart.)

Zu den Reihenfolgeproblemen gehören:

• das Problem des Handlungsreisenden
• das eindimensionale Packungsproblem, Tetris-Problem
• Scheduling-Probleme (was soll wann gemacht werden)
• Sortieren