Ok, das hat mich jetzt doch interessiert und ich habe mich etwas eingelesen: Es geht darum die Breite des Bandes einer Bandmatrix zu minimieren.
Imho würde sich ein
Branch-and-Bound-Verfahren anbieten: Jeden anfügen eines Elemente ist ein Branch-Schritt.
Wenn du das Minimum (oder einen "akzeptablen" Wert) erreicht hast brichst du ab; wenn du irgendwann beim Sortieren die bisherige obere Schranke überschreitest, kannst du den Branch abschneiden: egal wie du den Suffix sortierst, der Zielwert wird nicht besser.
Eine untere Schranke findet man leicht: Die minimale Breite des Bandes ist die maximale Anzahl von Abhängigkeiten eines Elementes.
Dann wäre es natürlich schön, eine möglichst gute erste obere Schranke zu haben.
Das könntest du mit einem Greedy-Verfahren versuchen: Fange mit einem Element mit maximal vielen Abhängigkeiten an, dann füge immer ein Element hinzu, das die älteste Abhängigkeit von Vorgängern erfüllt. Das Ergebnis ist vermutlich nicht optimal, aber vermutlich besser als ausgewürfelt. Alternativ hast du vielleicht Informationen, die du für eine erste Sortierung nutzen kannst, z.B. räumliche Anordnung.