## 3 Algorithm for TSAFP
### Algorithm Description  
The LCS algorithm (Please note that an earlier for the LCS algorithm was previously described by the current author in [21]) operates as a depth-first search of all possible task phasings, employing simple bounding heuristics to help prune the search. The inputs to the algorithm are a task set \(\tau\), and the output of the algorithm is the determined value of \(c_{Max}\). The first step is the calculation of the phase matrix. The initial incumbent solution value \(b\) is set to the maximum of the largest task execution times, and summed execution times of any pairwise phased tasks during this process; \(c_{Max}\) cannot be any less than this. The algorithm then begins to recursively search for congruent subsets of tasks; the main elements of the algorithm are shown in Figure 5.  
Each node of the search tree represents a subset \(T\) of congruent tasks; the depth of recursion corresponds to \(|T|\). The incumbent is updated whenever a subset with (\(T\)) \(>b\) is found. Each node has associated with it its own phase code \(P\). Since only proper congruent subsets can be expanded as child nodes in the search, the \(i^{\text{th}}\) task can only be added into the current subset \(T\) to form a new child node with subset \(T^{\ast}\) if the \(i^{\text{th}}\) bit of \(P\) is set to a '1'. To generate the new phase code in the child node, a logical AND is performed between \(P\)' and \(P^{i}\), the \(i^{\rm th}\) row of the phase matrix. This effectively applies equation (13) in one single operation, and the only bits that will subsequently be set to '1' in \(P\) thus correspond to tasks that are properly congruent with all tasks in \(T\). When an empty phase code is encountered, the algorithm begins to backtrack since either a leaf node has been reached or - since bits are cleared by the algorithm after the corresponding child node has been explored - no further child nodes exist. The call to sub-function \(ssb\) on line 19 locates the next lowest set bit in the current phase code; since these codes are represented as bit-strings, this can be performed in small fixed constant time, e.g. using techniques based around a deBruijn sequence [24]. The pruning rule that is implemented simply prevents the expansion of child nodes which cannot possibly lead to a value greater than the current incumbent. This simple procedure works as follows; suppose the current node represents a subset \(T\), and that a proper child node corresponding to the \(j^{\rm th}\) task is about to be expanded. An upper bound \(b_{up}\) on the best possible value that can be achieved by such an expansion is as follows:  
\[b_{up}=\sum_{i=j}^{n}c_{i} \tag{15}\]  
This bound expresses the fact that the best possible situation - in which _all_ tasks corresponding to unexplored branches - are congruent to \(T\). If this value is not greater than \(b\), then the node need not be expanded. Moreover, since the search progresses in a depth-first, left-to-right search, the current node can be considered fathomed; this bound can only be non-increasing for all child nodes greater than \(j\)  
Figure 5: LCS algorithm, in pseudo-code. This fathoming rule, along with the fact that the algorithm can be implemented entirely using (fast) integer arithmetic, leads to a very efficient formulation. After first showing that the algorithm completely solves the TSAFP, its time complexity is analysed. **Theorem 3**: Algorithm LCS exactly solves the search version of TSAFP. **Proof**: By inspection. It can be seen that LCS will recursively enumerate only congruent subsets of tasks as the search progresses, as follows; line 12 ensures that only subsets of tasks that conform to (14) are considered as valid child nodes in the search, and the IF statement of line 20 ensures that only these nodes are actually expanded. The WHILE statement on line 18 ensures that the algorithm will explore every possible child node, backtracking iff either no unexplored child nodes remain or the current node has been fathomed according to (15).