Real-time Networks-on-Chips (RT-NoCs) provide timing guarantees for communication in many-cores. However, RT-NoCs customized routers may conflict with other non-functional requirements such as low-energy consumption, safety, and security. To alleviate the effects of non-functional requirements on the NoC design, we proposed a framework to deal with hard real-time flows without modifying the NoC architecture. One of the drawbacks of the previous framework was its scalability due to the employed integer-linear programming (ILP) backend. In this work, we propose a breadth-first depth backend with parameterized search to accelerate the scheduling to polynomial-time. Due to the large solution spaces, ILP solvers struggle with performance, even for medium-sized applications. Results show that our framework computes a feasible hard real-time flow scheduling with acceptable performance.