Branch-and-bound Verfahren beruhen auf dem Backtracking: Es wird zunächst ein Baum aufgebaut, der in den Blättern alle möglichen Reihenfolgen der Jobs enthält. Ob eine Reihenfolge möglich ist, bestimmen hauptsächlich Regeln, die angeben, ob ein Job vor oder nach einem anderen ausgeführt werden muß. Es können aber auch weitere Zeitbedingungen angegeben werden. Die restlichen Knoten enthalten Teilfolgen von Jobs. Der Baum wird dann mit einer Tiefensuche oder einer Breitensuche durchsucht, um eine funktionierende oder die optimale Lösung zu finden.
Das Aufbauen und Durchsuchen des Baumes ist sehr aufwendig, insbesondere wenn man die Jobs sehr feingranular einteilt. Besonders feine Einteilungen bekommt man, wenn die Threads unterbrechbar sind, da man in diesem Fall mit nicht unterbrechbaren Einheiten wie Prozessorbefehlen als Jobs rechnen muß. Daher kann dieses Verfahren nur offline eingesetzt werden. Es hat seine Anwendungen im Bereich des Operations Research, wo ein optimaler Maschinenbelegungsplan einmal ausgerechnet und dann sehr oft ausgeführt wird.