The application of optimal search strategies to scheduling for distributed real-time systems is, in general, plagued by an inherent computational complexity. This has effectively prevented the integration of strategies such as branch-and-bound (B&B) in scheduling frameworks and tools used in practice today. To show that optimal scheduling is, in fact, a viable alternative for many real-time scheduling scenarios, we propose an approach that can reduce the average search complexity to levels comparable with that of a polynomial-time heuristic.Our approach is based on making intelligent choices in the selection of strategies for search tree vertex traversal and task deadline assignment. More specifically, we conjecture that effective complexity reduction is achieved by (i) traversing vertices in the search tree in a depth-first fashion and (ii) assigning local task deadlines that are non-overlapping fractions of the application end-to-end deadline.Through an extensive experimental study, we find that our approach contribute to reducing the average search complexity by several orders of magnitude for a frequently-used class of distributed real-time applications.