## 4 TSN Network-Wide Scheduling--Approaches Overview, Challenges, and Future Directions
### Methods and Approaches for Scheduling in TSN
#### 4.1.1 Schedulability and Dynamism  
The schedulability and dynamism of a network are crucial objectives, particularly for use cases that involve dynamic reconfiguration like fog computing. Improving the dynamism within the network, such as through dynamic reconfiguration, can be viewed as a means to enhance traffic schedulability. Consequently, various research works have focused on increasing both the schedulability of traffic and the dynamism of the network, employing different optimization objectives to achieve these goals. For instance, one approach, introduced in [34], is the urgency-based scheduler (UBS), which supports scheduling of urgent traffic. Similarly, study [36] presented an alternative approach to address the same objective, suggesting enhancements to TAS (traffic-aware scheduling) and introducing a protection band. This band allows for the transmission of emergency traffic while isolating it from LTS and BE traffic. Another strategy to enhance network dynamism involves optimizing runtime scheduling. In this regard, [PERSON] et al. [61] proposed an extensibility-aware algorithm based on simulated annealing to maximize the schedulability of dynamic traffic. On the other hand, [PERSON] et al. [59] formulated a mixed integer problem, leveraging the similarities between the scheduling problem and vector bin packing. However,  
Figure 3: An overview of the objectives in the surveyed literature classified into aim groups, together with references to the corresponding papers. The objectives are enumerated for easier reference in the other parts of the paper. both approaches ([59, 61]) did not propose offline scheduling methods to prepare for schedule extension during runtime. Another approach to optimizing runtime scheduling assumes the existence of a pre-configured schedule in the network and focuses on developing online reconfiguration algorithms. For example, study [65] utilized column generation to maximize the traffic acceptance rate, while study [66] introduced an incremental routing and scheduling approach to maximize the number of schedulable flows at runtime. In addition to maximizing online schedulable flows, several approaches aim to minimize reconfiguration time. Study [67] presented a joint-ILP formulation and a scheduling compatibility heuristic, while study [68] introduced HERMES, a heuristic for reducing reconfiguration time. Another avenue to enhance network dynamism is through fast scheduling. Approaches that accelerate schedule synthesis include simplifying topology [69], incremental scheduling using divide and conquer [70], leveraging divisibility theory [33], partial scheduling [71], exploring the correlation between periods [72], and optimizing routing to expedite scheduling [73]. The interdependence between scheduling and routing has also been considered. For instance, authors in [47] employed a genetic algorithm where the chromosomes represent choices for routing along with application bending. In contrast, study [15] formulated an ILP to minimize the maximum load in a port, routing HTS traffic through different ports to reduce conflicts, particularly in larger networks. Additionally, Authors of [71] utilized a partial scheduling approach for space probing guided by conflicts, proposing EPIC, a heuristic for fast network scheduling in larger networks. Various techniques have been employed to maximize schedulability. For instance, study [60] proposed several scheduling heuristics based on bin packing, dot product, coefficient of variation, and other methods. The authors of [74] focused on the trade-off between schedulability and optimality of solutions, using a constraint programming formalism. In [75], authors suggested a real-time routing scheduler to ensure the schedulability of HTS streams, while authors of [32] utilized an injection time planning algorithm to maximize the scheduling of HTS streams. Furthermore, some approaches have suggested enhancements in TSN hardware to improve schedulability. However, not only pure HTS schedulability has been considered.