## 5 Heuristic Approaches
### Dynamic Island Model
#### 5.2.1 Principle
In Figure 5, both the transition matrix \(M\) and the population size of each island are represented with a directed graph (DG). Each edge \((i,j)\) from vertex \(i\) to vertex \(j\) has a weight that corresponds to \(M_{ij}\). As the edges represent stochastic transition between vertices, the sum of the weights of the out-coming edges must be 1. Finally, the vertices in this diagram are proportional to the size of the population. #### 5.2.2 Solution Representation

A solution \(s\) is represented by a sequence \(\{i_{1},\ldots,\)\(i_{k},\ldots i_{\kappa}\}\) of size \(\kappa\leq n\) where \(i_{k}=1,\ldots,n\) is the \(k\)th order to be scheduled. Moreover, an integer \(origin=1,\ldots,v\) is used to represent the residence island at previous iteration. Associated completion times, \(C_{i_{k}}\), for all \(k=1,\ldots,\kappa\) are computed in the decoding phase (Figure 6). Completion times \(C_{i_{k}}\) are calculated so that each order \(i_{k}\) starts as soon as possible at time period \(ST_{i_{k}}=\max(C_{i_{k-1}},r_{i_{k}})\), thus \(C_{i_{k}}=ST_{i_{k}}+p_{i_{k}}+s_{i_{k-1}i_{k}}\) when \(C_{i_{k}}>\bar{d}_{i_{k}}\) the order is rejected. #### 5.2.3 Mutations Operators

Each island is characterized by a mutation operator. The majority of these operators can lead to the rejection of orders in the sequence. Completion times are thus updated accordingly whenever an operator is applied. Add

This operator picks randomly a order \(\bar{a}\) among the rejected order list and inserts it at a random position \(k\) in the sequence. Swap

The operator swap takes randomly two orders \(i_{j}\) and \(i_{k}\) and swaps their position \(j\) and \(k\) in the sequence. Exchange

This operator picks randomly a rejected order \(\bar{a}\) and an order \(i_{k}\) in the sequence and replaces them. That is, the order \(i_{k}\) is rejected and the order \(\bar{a}\) is put at position \(k\) in the sequence. Shift

This operator aims at shifting all the orders at the best starting time in terms of energy cost without causing tardiness or rejection. This operator examines for all order \(i_{k}\) the best

Figure 5: Directed Graph (DG) for an example with 3 islands. Figure 6: Decoding a solution by updating completion times. insertion period by computing exhaustively the energy cost between the starting times \(ST_{A}\) and \(ST_{B}\) and choosing \(t_{best}\) where the energy cost is minimal. \[ \begin{split} t_{best}&=\operatorname*{argmin}_{t=ST_{A },\ldots,ST_{B}}\sum_{t^{\prime}=t}^{t+p_{i_{k}}+s_{i_{k}-i^{\prime}k}}c_{i_{k}t^ {\prime}}\\ ST_{A}&=\max(C_{i_{k-1}},r_{i_{k}})\\ ST_{B}&=\min(ST_{i_{k+1}},d_{i_{k}})-p_{i_{k}}-s_{i _{k-1}i_{k}}\end{split}  \tag{44}\]

Scramble

The scramble operator picks two position \(k\) and \(j\) randomly between \(1,\ldots,\kappa\) and shuffles the sequence between these positions. Inversion

This operator generates randomly two positions \(k\) and \(j\) between \(1,\ldots,\kappa\) with \(k<j\). Then, between \(k\) and \(j\) the sequence is inverted. For the purpose of efficiency, a version of the operators _Add_ and _Exchange_ that take into consideration the revenue load ratio (\(RL_{j}=\frac{e_{j}}{p_{j}}\)) has been developed. For the operator _Add_, this consists in systematically add the best rejected order according to this ratio. For the _Exchange_ operator, this implies choosing the worst order according to \(RL\) and replace it the best rejected order, in accordance with the revenue load ratio. These versions are respectively referred as _AddGreedy_ and _ExchangeGreedy_. #### 5.2.4 Crossover Operator

For the considered problem, the crossover operator from in [57] has been utilized. This crossover takes as input two parents solutions \(p_{1}\) and \(p_{2}\). The sequence of \(p_{1}\) is examined at each position. For each position, orders are successively add up to the children sequence, using a random number to either inserts the order from \(p_{1}\) or the one from \(p_{2}\).