## 5 Description of the Heuristics
### Second Phase: Maximum Edge Disjoint Path Problem (MEDPP)--Greedy Heuristics
To avoid increasing the complexity of the tuning task, the domain of some parameters was restricted to the most relevant values. Table 3 shows the domain considered for each parameter and the best value reported by IRACE. Clearly, by increasing the number of iterations both in the Multistart algorithm of phase 2 and in the perturbation and improvement procedure of phase 3, the solution obtained will be better, since both procedures return the best solution found. Clearly, by increasing the number of iterations in the perturbation and improvement procedures of phase 3, the solution obtained will be better, since the procedure returns the best solution found. A similar situation happens with the different heuristics proposed for phase 2. The Simple heuristic will be faster, but the solution obtained with the Multistart Ad-Hoc will be of better quality. Therefore, for these parameters, an analysis of the compromise between the quality of the solution found and the execution time will be made later. The column \"Best value Flows\" refers to the best parameter setting for the version where the sending unit is the complete flow, and the column \"Best value Instances\" for which it considers an instance as a unit. The first parameter listed is the one that selects the approach in phase 1. This first stage is important as its output is a time scheduled for each slot. In the first approach, the scheduling unit is the flow while in the second it is the activation of the flow. In the first case, the algorithms order the queue of pending flows to be sent by the period while in the second it uses the deadline. It is natural then that, when in the following stages, the scheduling is based on the activations, the best option for the first phase is the second approach. As can be seen in the Table 3, in the perturbation procedure in phase 3, in neither of the two approaches it is convenient to delete flows or activations that are being sent to try to make room for others. Furthermore, the best performance is obtained when the percentage of instances and slots to be moved is low. This indicates that the decisions made in the previous phases are adequate and it is not convenient to undo them. It is only useful to make small movements in terms of slot or path used. On the other hand, at higher values of _nTries_, the improvements obtained in the quality of the solutions are negligible or null, and thus the cost in execution time that this requires does not make sense, and with a value of 10 the best performance was obtained. These configurations are kept for the next experiments. In all the tables that follow, the \"Flows/Act columns\" represent the number of flows or activations sent in the solution found by the respective algorithm. The \"N_Saving_F\" or \"N_Saving_A\" column is computed according to Equation (16). To some extent, this considers the effectiveness of the solution with respect to the two objectives, number of flows or activations sent and energy consumption. For heuristics, the Time column expresses the time taken by each one in seconds. ### Validation of the Methodology

This first experiment has the purpose of validating the methodology. Although it is not possible to assert that the behaviour with small cases is similar to that with big systems, it provides an idea of the different speeds and quality of the results in finding a solution. In the first place, small systems were defined in order to obtain solutions from the ILP formulation and compare them with those obtained with the heuristics. To solve the ILP model, CPLEX v20.1.0 was run with the default parameters ([[https://www.ibm.com/docs/en/icos/20.1.0](https://www.ibm.com/docs/en/icos/20.1.0)]([https://www.ibm.com/docs/en/icos/20.1.0](https://www.ibm.com/docs/en/icos/20.1.0)), accessed on 15 February 2022) for a maximum of 1800 [s] using all the computing power of the server for each of the objectives, first to maximize the number of flows or activations sent, and then to minimize the cost power (number of total switches turned on per slot).