1. einer Blockzuweisung, die jedem Gebiet v V eine entsprechende Menge B_v von DAB-Blöcken, d. h. Ensembles B S zuordnet
2. einer Kanalzuweisung, die jedem Gebiet v V und jedem dort übertragenen Block B B_v einen Kanal f(v,B) zuordnet

Dabei muss, wie bereits im letzten Abschnitt diskutiert, jeweils die Blockgröße eingehalten werden, und es müssen sämtliche Versorgungsanforderungen erfüllt werden. D. h.:

Ferner muss die zugehörige Kanalzuweisung interferenzfrei sein, d. h.:

(Man beachte, dass entsprechend den Systemeigenschaften von DAB gleiche Blöcke stets auch gleiche Kanäle erhalten dürfen.) Die zu optimierende Größe ist schließlich die Anzahl der verwendeten Kanäle f(v,B),v V,B B_v, die minimiert werden soll.

Um dieses zweistufige Optimierungsproblem zu lösen, bietet es sich an, die beiden Teilprobleme zu betrachten: (1) Ermittlung einer Blockzuweisung und (2) Berechnung einer zugehörigen Kanalzuweisung. Wie wir gleich sehen werden, handelt es sich beim ersten Teilproblem im Prinzip um ein sogenanntes Packungsproblem, während sich das zweite Teilproblem erwartungsgemäß auf das uns schon bekannte Graphfärbungsproblem zurückführen lässt.

Packen der DAB-Blöcke Beim Packungsproblem handelt es sich um die Aufgabe, eine Menge S von Gegenständen s mit gegebenen Größen _s auf Behälter gleicher Größe M zu verteilen. Die kleinste Anzahl von Behältern, mit der dies möglich ist, bezeichnen wir mit p_M(S) (Packungszahl von S). Zwar ist auch das Packungsproblem NP-vollständig, es lässt sich jedoch im Unterschied zum Graphfärbungsproblem gut approximieren. Eine gebräuchliche Methode ist der folgende „First Fit“-Algorithmus mit fallenden Element-Größen (FFD = „First Fit Decreasing“), vgl. auch [Garey/Johnson 1979]:

• Man ordne die zu packenden Elemente nach fallenden Elementgrößen.
• Beginnend mit einer leeren Liste von Behältern, betrachte man nun nacheinander die Elemente in der zuvor berechneten Reihenfolge.
• Jedes Element s wird dem ersten Behälter B in der Liste zugefügt, in den es noch hineinpasst (d. h. _B + _s < M); existiert kein solcher, so wird ein neuer Behälter B = {s} am Ende der Liste angefügt.