Time-Sensitive Networking (TSN) is a set of standards defined by the IEEE 802.1 TSN Task Group and aims at making IEEE 802.3 Ethernet real-time capable. TSN employs a Time Division Multiple Access (TDMA) scheme to achieve temporal isolation between data streams, and thus, provides bounds on worst-case latencies and real-time guarantees. The TDMA scheme divides access to transmission links into slots. Calculating the slots of the TDMA scheme is referred to as scheduling. Scheduling is known to be NP-complete. Current approaches are mainly based on constraint programming and optimization problems, and thus, do not scale well for large problem instances. In previous work Scaling TSN Scheduling for Factory Automation Networks [HGF+20], Hellmanns et al. developed a novel fast scheduling approach to schedule data streams in a TSN network. It significantly outperformed current approaches in execution time. They use a discrete-event network simulator to simulate stream transmissions and to derive a schedule from the simulation results, sacrificing the optimality of the schedule for calculation speed. The authors refer to this approach as tracing-based scheduling. We expand the tracing-based scheduling approach to a full-blown scheduling algorithm. To do that, we propose a novel formulation of the scheduling problem: scheduling as a search problem. Using this formulation, we develop four novel scheduling approaches: Tracing-based Scheduling (TBS) Naive approach, TBS Link Time Remaining Time, TBS Link Time Late Streams, and TBS Link Time Monte Carlo Tree Search (MCTS). We evaluate each approach along the following properties: execution rates, scheduling runtimes, and scheduling capabilities. The MCTS approach exhibits the best performance. It outperforms two contemporary schedulers and can schedule the majority of problem instances in under 1200 s.