## 5 Related Work and Discussion  
One of the first sufficient schedulability tests for non-preemptive fixed-priority multiprocessor scheduling was described in [PERSON]'s paper in el. published in 2008 [25]. The authors bounded the number of tasks doing carry-in jobs in the \"problem window\" to obtain this test. The definition of carry-in job is given as follows: a carry-in job is released before the interval of interest, but its deadline is within the interval. To bound the number of carry-in jobs, the authors consider jobs that execute as late as possible. This test is later improved to quadratic time complexity [26]. [PERSON] et al. propose a sufficient schedulability test for the same case without the carry-in limitation [6]. In this test, they analyze job interference. Interference is the amount of execution of other tasks that interferes with the execution of the task of interest. The proposed test is based on using the upper bound of interference. [PERSON] et al. consider a superset of fixed-priority preemptive multiprocessor scheduling and fixed-priority non-preemptive multiprocessor scheduling [27]. They call this superset Global Fixed Priority Scheduling with Deferred Preemption (gFPDS). The authors propose two types of sufficient schedulability test for this case: with and without the carry-in limitation technique. These tests are interesting as generalizations of the two cases: preemptive and non-preemptive scheduling. In 2017, [PERSON] proposed a test for non-preemptive fixed-priority multiprocessor schedulability based on an improved carry-in limitation technique [7]. This improvement, related to previous research, is to consider the critical instant for a task. The critical instant is the point in time at which a job request results in the longest task response time. \begin{table}
\begin{tabular}{c c} \hline \hline
**Utilisation** & **Infeasibility Ratio** \\ \hline \([0.0,0.2)\) & 0.09 \\ \hline \([0.2,0.4)\) & 0.4 \\ \hline \([0.4,0.6)\) & 0.75 \\ \hline \([0.6,0.8)\) & 0.91 \\ \hline \([0.8,0.1)\) & 0.94 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Performance of our infeasibility test 2 in terms of acceptance ratio. The first exact schedulability test for the special case of fixed-priority non-preemptive multiprocessor scheduling is provided by [PERSON] et al. in 2019 [17]. This special case considers self-suspensible tasks with fixed preemption points. The authors reduce schedulability analysis to the reachability problem in synchronized automata (TA). They use the UPPAAL model checker [35] to solve this reachability problem. [PERSON] and [PERSON], in 2020 [8], improved the interference upper bound proposed in 2014 [6]. This improvement is based on the analysis of tasks with higher priority than the task of interest. In [28], [PERSON] and [PERSON] propose the first infeasibility test for fixed-priority non-preemptive multiprocessor scheduling. This approach finds a task priority that makes a set of tasks schedulable. If this algorithm cannot create such a priority for a particular set of tasks, the set is infeasible. The main feature of the proposed approach is the checking of a special constraint on the infeasibility of a task. This constraint is based on an analysis of the bounds of the sum of the total number of executions of higher priority tasks in the problem window for the task of interest. Using this constraint eliminates the need to consider all combinations of priority assignments, since this constraint depends only on the higher-priority tasks. Thus, this approach is based on the constraint testing using a decreasing order of priorities. The main advantage of our work compared to the above is the quadratic complexity of the exact test for multiprocessor scheduling (Algorithm 1). If a tasks' parameters are unstable, this test can be used without modification at a higher planning level as an online acceptance test to determine the schedulability of the system with changed characteristics, which, however, remains within the specified task-to-processor ratio.