## 5 Performance Analysis
### TSOAP Algorithm Testing  
The MULTIFIT and SWAPFIT algorithms were tested both in terms of their computation time and the quality of the schedule they produced. First, task sets were generated as per the previous Section. For each value of \(n\) 1,000 task sets were considered, and the computation time required for both algorithms on each instance was recorded. A summary of the results is given in Table 3 and Figures 12 and 13, with units of seconds. It was observed that in every instance, the value of the objective function found by SWAPFIT (\(z_{s}\)) was \(\leq\  
minute computation time limit was placed on each instance. Every instance with \(n\leq 15\) was solved exactly within this bound; in most cases taking considerably less time, a significant achievement given the complexity of the problem. For instances with \(n>15\), approximately 30% of instances could not be solved exactly within this time bound; however in each of these cases a solution that was probably within 5% of optimality was returned. The best know lower bound was used for the performance comparison. The results allowed the performance of each of the heuristic algorithms to be further analyzed. Table 4 shows the average and maximum deviation from optimality for both algorithms (as a percentage) in these selected instances.  
It can seen from these Tables and Figures that the running time for SWAPFIT was competitive with MULTIFIT, having a marginally better average and worst case running time in most instances. However, whilst SWAPFIT consistently found optimal schedules, and was never further than 4.68% from optimality, with an average deviation of 0.11%, the same could not be said for MULTIFIT. The average deviation was 22.36% for the latter algorithm, with deviations as large as 63.63% being observed. In summary, the SWAPFIT algorithm seems to be far more consistent than MULTIFIT both in terms of its running time and the resulting solution quality; the algorithm seems to capture the essence of the problem much better. Although SWAPFIT can only be considered a local search algorithm, it can be observed that a single pair-wise reversal of tasks in a list has the potential to radically change the entire resulting schedule; this ability to widely explore the search space whilst  
Figure 12: MULTIFIT running times.  
\begin{table}
\begin{tabular}{c c c c c} \hline  & \multicolumn{2}{c}{**SWAPFIT**} & \multicolumn{2}{c}{**MULTIFIT**} \\ \(N\) & **Max** & **Ave** & **Max** & **Ave** \\ \hline
5 & 0.00068 & 0.000009 & 0.000766 & 0.000018 \\
10 & 0.01792 & 0.000836 & 0.005827 & 0.000243 \\
15 & 0.152797 & 0.011035 & 0.042646 & 0.001635 \\
20 & 0.84614 & 0.058131 & 0.988282 & 0.016758 \\
25 & 4.81073 & 0.231637 & 5.02838 & 0.120799 \\
30 & 8.99549 & 0.780521 & 10.3763 & 1.04288 \\ \hline \end{tabular}
\end{table}
Table 3: Summary of algorithm running times (s).  
honing in on a good solution may explain its excellent performance. As a final point, it can also be observed that since task computation times are often over-estimated by as much as 5%, the reported bounds for SWAPFIT and the errors for unsolved ITLB instances can effectively be neglected in most cases, as they are a far smaller source of potential error.