## 5 Description of the Heuristics
### Second Phase: Maximum Edge Disjoint Path Problem (MEDPP)--Greedy Heuristics
To do this, in the _make_feasible_ procedure it uses the _bfs_shortest_path_ routine to search a path between source and destination through already used switches first. This is done in feasible or usable slots that have not been used by that flow/activation. If it is not possible to complete the flow/activation, it is removed and all paths and slots used are released. After this, a flow from those that has not been previously scheduled is chosen and allocated if possible (_improve_ procedure). Finally, a certain number of iterations are made (this is an input parameter, \(MAX\_ITERS\)). In case this value is zero, the first solution is the one adopted. If it is higher, the solution is disturbed, and new allocations are tried. ```
0: Network \(R\), sequence of set of (source, destination) flows \(S=\langle S_{1},\ldots,S_{H}\rangle\) with priorities, \(MAX\_ITERS\in\mathbb{N}\)
0:\(\overline{P}=\langle\overline{P_{1}},\ldots,\overline{P_{H}}\rangle\), where \(\overline{P_{h}}\) indicates the set of disjoint paths in \(R\) followed in slot \(h\) by the flows delivered in that slot \(\overline{P}\leftarrow\langle\rangle\) for\(h=1,\ldots,H\)do \(\mathit{niters}\leftarrow\mathit{MAX\_ITERS}\) \(\mathit{assigned\_count}\leftarrow\{f:0,f\in S_{h}\}\) \(S\leftarrow\mathit{sort\_by\_priorities}(S_{h})\) \(\mathit{best\_AR}\leftarrow\mathit{disjoint\_paths}(R,S)\) while\(\mathit{niters}>0\)do \(S\leftarrow\mathit{shuffle}(S_{h})\) \(\mathit{assign\_result}\leftarrow\mathit{disjoint\_paths}(R,S)\) if\(\mathit{f}\) is assigned in \(\mathit{assign\_result}\)then \(\mathit{assigned\_count}[f]\leftarrow\mathit{assigned\_count}[f]+1\) endif if\(\mathit{assign\_result}\) is better than \(\mathit{best\_AR}\)then \(\mathit{best\_AR}\leftarrow\mathit{assign\_result}\) endif \(\mathit{niters}\leftarrow\mathit{niters}-1\) endwhile \(S\leftarrow\mathit{sort\_by\_assigned\_count}(S_{h})\) \(\mathit{assign\_result}\leftarrow\mathit{disjoint\_paths}(R,S)\) if\(\mathit{assign\_result}\) is better than \(\mathit{best\_AR}\)then \(\mathit{best\_AR}\leftarrow\mathit{assign\_result}\) endif \(\overline{P}\leftarrow\mathit{add\_back}(\mathit{best\_AR})\) endfor return\(\overline{P}\)
```
**Algorithm 6** Multistart Ad-Hoc Greedy Heuristic. ```
0: Network \(R\), set of flows \(F\), \(\overline{P}=\langle\overline{P_{1}},\ldots,\overline{P_{H}}\rangle\), where \(\overline{P_{h}}\) indicates the set of disjoint paths in \(R\) followed in slot \(h\) by the flows delivered in that slot (could be not feasible), \(MAX\_ITERS\in N\), \(rRemove\in[0,1]\), \(rInst\in[0,1]\), \(rStot\in[0,1]\), \(nTries\in N\)
0: An feasible assignment of flows \(P=\langle P_{1},\ldots,P_{H}\rangle\), where \(P_{h}\) indicates the set of disjoint paths in \(R\) followed in slot \(h\) by the flows delivered in that slot \(\overline{P}\leftarrow\text{make\_feasible}(\overline{P})\)\(\overline{P}\leftarrow\text{improve}(\overline{P})\)\(P\leftarrow\overline{P}\)\(\mathit{inters}\gets MAX\_ITERS\)while\(\mathit{niters}>0\)do\(\overline{P}\leftarrow\text{perturbation}(\overline{P},rRemove,rInst,rStot,nTries)\)\(\overline{P}\leftarrow\text{improve}(\overline{P})\)\(\mathit{niters}\gets\mathit{niters}-1\)if\(\overline{P}\) is better than \(P\)then\(P\leftarrow\overline{P}\) endif endwhile returnP
```

**Algorithm 7** Third phase algorithm. The _perturbation_ procedure first removes a certain percentage (given by the input parameter \(rRemove\)) of flows/instances. Then, the schedule is randomly modified by changing the slots and paths in which some flows are transmitted. This process is controlled by three input parameters. The parameter \(rInst\) indicates the percentage of instances to be considered, while \(rStot\) the percentage of slots or paths to be modified. Finally, \(nTries\) sets the maximum number of slots in which a new path will be searched. If after \(nTries\) attempts a path is not found in a new slot, the current slot and path are kept. The pseudo-code for these procedures is omitted because of its simplicity.