## 4 Algorithms for TSOAP
### The SWAPFIT Algorithm  
The LPT algorithm for multiprocessor scheduling first sorts the tasks in order of decreasing execution time, and assigns the tasks one by one onto the first available processor; the latter operation is known as list processing. It has been proven that the makespan resulting from LPT is no further than 33% from optimal. The rationale behind SWAPFIT is simple; there is a permutation of the tasks such that application of list processing produces an optimal makespan, and in [17], it is shown that the list produced by sorting for non-increasing execution times produces a permutation that is very close to optimal. Starting from a good, initial solution, an attempt is made to sort the list into a better order, guided by resulting changes in the value of the objective function. In the SWAPFIT algorithm, list processing is modified as follows; each task in the list is assigned, one by one, an offset (bounded by _p'_) that minimizes the worst-case release of the task. LPT is initially employed to obtain a starting solution. Next, every pairwise set of tasks in the list is reversed, one by one; if such a reverse causes the objective function to decrease when the tasks are list processed, it is accepted. If not, the change is rejected, and the tasks swapped back. The SWAPFIT algorithm is shown in Figure 7.  
For SWAPFIT, it can be seen that the inner loop of pairwise reversals performs approximately 0.5 \(n^{2}\) reverses and list processes, and this process continues until either no more beneficial changes can be made, or an upper bound on allowed iterations is reached. As with most local search techniques, no sub-exponential bound can be placed on the number of iterations of this outer loop; in practice, this seems proportional to (but significantly less than) \(n\). By setting an upper bound as \(n\) and simply returning the best solution found if this bound is exceeded, the algorithm again runs in pseudo  
Figure 7: SWAPFIT algorithm, in pseudo-code.  
polynomial time for fixed \(n\), with complexity _O_(_max(\(n^{3}\), np'\({}_{max}\))_). Since LCS is called multiple times, the _gcd_'s of each pair of tasks are again computed once only and stored in an array.  
Before moving onto describing the computational experiments, it is worthwhile discussing performance bounds for the two algorithms. The quoted performance bounds for the original versions of both MULTIFIT and LPT are known to be extremely tight for multiprocessor scheduling [13, 17]. However, it is clear that the performance bounds do _not_ hold for the current algorithms. When periods are evenly divisible, it can be seen that FFP results in a packing that is identical to First Fit (FF); however for general problem instances, no bounds are currently known. That said, it can be conjectured that both heuristics will produce a 'good' schedule; exactly how good this schedule is likely to be for general instances of the problem is investigated in Section 5. A general lower bound (\(z_{l}\)) for the optimal value of general problem instances can be obtained through (20):  
\[z_{l}=\max(u\cdot t_{{}_{\mathit{mck}}},(\max(c_{i})i\in\tau)) \tag{20}\]  
where \(u\) is the task set utilization. However it can be observed that this bound can be arbitrarily far from the true value, simply by considering subsets of tasks with co-prime periods; it follows from the Chinese remainder theorem that no choice of task offsets can avoid them being congruent. In many cases a tighter bound can be obtained by employing LCS to determine the largest co-prime task phasing. This observation leads to an alternate formulation for exact solutions to the problem; the Iteratively Tightening Lower Bound (ITLB) algorithm.