## 5 TSN Scheduling Problem Formulation
### TSN Scheduling Problem Constraints
* Size constraint [11, 24, 33, 58, 59, 60, 63, 65, 79, 91, 92, 94, 95, 97, 100, 101, 106, 109, 111, 119]: This limits the size of the windows, the amount of tolerance, the maximum occupancy of a link (e.g., by limiting the maximum number of windows in a link during one cycle for example), etc. * Offset constraint [14, 29, 31, 32, 33, 34, 41, 42, 44, 46, 48, 54, 59, 62, 63, 66, 69, 70, 71, 74, 76, 78, 84, 86, 90, 91, 92, 95, 96, 97, 102, 104, 105, 107, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122]: This controls the absolute positioning of the windows in relation to the gating cycle. This constraint ensures that the transmission of a frame is planned only after its full reception (i.e., enforce store-and-forward mode of functioning). * Overlap constraint [14, 29, 31, 35, 37, 38, 40, 41, 42, 44, 46, 50, 53, 54, 58, 63, 66, 67, 69, 70, 71, 74, 76, 77, 78, 84, 86, 87, 90, 92, 95, 96, 97, 98, 99, 102, 104, 106, 107, 110, 111, 116, 117, 118, 119, 120, 121, 122]: This ensures the temporal isolation between frames on link usage and prevents the double assignment of a transmission window to a frame. * Spacing constraint [24, 41, 48, 59, 62, 98]: This limits the spacing between windows of the same stream or different streams. This could be due to hardware limitations (as in [41]). * **Constraints on the resources [11, 31, 32, 42, 48, 49, 54, 63, 67, 69, 72, 78, 96, 97]: Some works additionally consider resource constraints related to limiting the length of the schedule or the application memory and CPU requirements if application placement is regarded (e.g., ref. [78]). * **Constraints specific to the problem [29, 30, 47, 104, 110]:** Some of the constraints in the reviewed literature are very dependent on the research question treated by the respective approach. Those constraints are not related to the scheduling problem itself; rather, they are needed to find feasible solutions. An example of such constraints are the ones used to comply with the functional safety standards, such as ASIL reqs constraints, as in [110], or the stability constraint used in [29] to enforce a stability margin in the solution. Other works treating application embedding introduced a constraint for the unique bending of the application in the end-hosts. Topology constraints are also considered problem-specific, as optimizing the topology is a step prior to its configuration. The constraints presented above have different importance, which is reflected by how often they are used in the reviewed papers. Some constraints are very crucial to the scheduling problem formulation itself, while others are less relevant. To illustrate the relevance of the different constraints and to understand the interaction between them in more detail, we illustrate in Figure 8 a network graph showing the relation between the different constraints. In the figure, the nodes represent the constraints, and an edge connecting two constraints represents how often they are used together in the same work. Figure 8 identifies a subset of constraints that are central to the scheduling problem and classifies the rest as peripheral. We note the repeated coexistence of the maximum latency constraint, the overlap constraint, and the offset constraint as very crucial in the formulation of the scheduling problem. The accessibility constraint, the routing constraint, and the periodicity constraint occur less often. This illustrates that the focus on achieving a feasible solution with smaller latencies was more important than achieving a higher level of determinism. Determinism could be enhanced using the accessibility constraint or the maximum jitter constraint, which were not very present in the works. The remaining constraints, other than these six, are less important, although useful.