## 4 Algorithms for TSOAP
### Breaking Symmetry  
Symmetry, in the current context, occurs when two sets of task offsets \(O\) and \(O\)' result in identical periodic behavior over the hyperperiod \(h\), the only difference being the relative start point of the schedules at \(t=0\). In such cases, the value of \(c_{Max}\) for both schedules is identical. A simple example can illustrate the concept of symmetry: suppose we have two tasks with periods {3,5}. Although offsets in the range 0-2 and 0-4 can seemingly be considered, the periods are coprime; all choices of offset are in fact identical and result in the same periodic behavior, shifted only at the origin. Obviously, to reduce the search space it is wished to only consider one set of offsets in situations where symmetry exists. Previous work in the area of offset-free preemptive scheduling by [PERSON] [11] has shown that in most periodic task system in which one is free to assign offsets, many classes of equivalent offset combinations exist. It is clear from the proofs developed in this previous work (specifically Theorem 9) that this can be also be shown to hold for the case of the offset-free non-preemptive thrift scheduler. [11] also outlined a method to break symmetries as part of a backstepping search algorithm; this can be adapted to develop a simple polynomial-time symmetry breaking algorithm, which is called once (and once only) before a search begins. Also, this method does not require the manipulation of any large integers--which in practice causes integer overflow even for moderately low \(n\)--and is also somewhat faster in practice. Let \(p\)' be the _phase capacity_ of a task, which is used to place an upper bound on the choice of its offset, such that if offsets for task \(i\) are selected in the range \(0\leq o_{i}<p\)' then all (and only) redundant configurations of offsets will be removed from the search. Since the evaluation of each offset configuration in the search space requires the solution of a coNP-Hard problem, this clearly has many benefits. For the first task, \(p\)' is always zero; this follows from Theorem 6 in [11]. For all \(1<i\leq n\), \(p\)' can be calculated as the \(lcm\) of the pairwise \(gcd\)'s between task \(i\)'s period, and all other periods less than \(i\):  
\[p_{i}\,\text{'}=lcm(\gcd(p_{i},p_{1})...\gcd(p_{i},p_{j}))\forall j,j<i \tag{17}\]  
**Theorem 4**: Considering task offsets upper bounded by \(p\)' only removes all (and only) redundant offset configurations from a search. **Proof**: Trivially follows from Theorem 10 in [11], the definition of \(p\)' given by (17) and the basic numerical properties of \(gcd\) and \(lcm\). Given the complexity results outlined in Section 2, it is unlikely that even small instances of the offset assignment problem may be solved exactly in a tractable time. In order to obtain relatively quick 'good' solutions to the problem, heuristics can be employed. Given the similarity of the considered problem to the multiprocessor scheduling problem, it follows that algorithms that have been useful in this area may also be applied in the current context. Before describing two such algorithms, the notion of symmetry will be extended further. In previous papers, the potential effects of symmetry on the hyperperiod of the task set have not been considered. From (12) and (13), it is clear that only the relative offsets of individual tasks define the subsets of tasks that are congruent. Thus, let the _harmonic period_\(h\)' of a task \(i\) be defined as follows:  
\[h_{i}=lcm(\gcd(p_{i},p_{i})...\gcd(p_{i},p_{j}))\forall j,j\
eq i \tag{18}\]  
This is a simple extension of the notion of phase capacity. Suppose we now consider a _reduced task_ set \(\tau\)', in which the tasks are identical to those in \(\tau\), with the exception that each and every period \(p\) is replaced by \(h\).