## 5 Heuristic Approaches
### Dynamic Island Model
#### 5.2.1 Principle
The tests allowed to find 13 better solutions compared to the MILPs. The robustness of the metaheuristic on small instances (0.2%) is as good as on large instances (0.8%). Finally, the performance in terms of deviation from the BKS is \(-35\%\) for large instances on average and 0.08% for small to medium instances on average. In terms of deviation, the DIM metaheuristic dominates all the approaches. However, we notice that the performances depend on the characteristics of the instances. For \(\tau=0.9\), the DIM metaheuristic is less robust and need much more iterations to find the optimal solutions. This can be explained by the non-specificity of the mutation operators to tackle instances with scattered release dates and less flexibility. When \(n\geq 50\), the FR heuristics become better than MILPs with reasonable solving times. Moreover, a clear improvement is noticeable with instances for which \(\tau=0.1\). ## 7 Conclusions and Perspectives

This paper proposes two new mathematical formulations for a rather recent research, that is, the OAS problem with release dates, sequence-dependent setup times, TOU costs and CO\({}_{2}\) emissions periods. The provided MILPs are time-indexed; however, these new exact models are limited to solve medium and large instances in presence of sequence-dependent setup times. Without setup, the TI On/Off formulation is the most competitive. In this context, original FR heuristics that approximate setup are developed, taking advantage of time indexation. Better solutions have been found by these heuristics. According to the results obtained on the state-of-the-art benchmark, the best version of FR heuristic is the one with the TI Pulse formulation. Moreover, in this paper, a population-based metaheuristic is also developed. The latter is based on Dynamic Island Model framework. This procedure can solve small to large instances within half a minute on a personal computer with average performance features. Future work can be dedicated to the extension of the problem to other systems such as parallel machines or floor shop. Determining mathematical properties of the studied problem can be undertaken. In addition, further analysis can be devoted to the instance settings \(\tau\) and \(R\) and TOU tariffs policy. Moreover, an extensive analysis on other CO\({}_{2}\) emissions reduction policies is an interesting prospect, as this work only focuses on the taxes on carbon emissions. For instance, a limitation on carbon emissions could be incorporated in the formulation. Extended tests on larger instances \(n>100\) shall be performed in order to assess the performance of FR heuristics. For instance, Benders decomposition approaches can be developed on the presented time-indexed formulations and compare the performances with the provided FR heuristics. As for the DIM, more specific mutation operators shall be developed in order to tackle instances that are difficult to solve. Other solution representation can also be explored in order to compare it with the sequence-based representation. Conceptualization, M.B., O.M. and A.Y. ; methodology, M.B., O.M. and A.Y. ; software, M.B. ; validation, O.M. and A.Y. ; investigation, M.B., O.M. and A.Y. ; writing--original draft preparation, M.B. ; writing--review and editing, O.M. and A.Y. ; supervision, O.M. and A.Y. ; funding acquisition, O.M. and A.Y. All authors have read and agreed to the published version of the manuscript. This research was funded by the Grand-Est Region and the Aube Department in France. The authors gratefully acknowledge this support. Not applicable. The data are available in the following Github repository [[https://github.com/worldstar/OpenGA/tree/master/instances/SingleMachineOASWithTOU](https://github.com/worldstar/OpenGA/tree/master/instances/SingleMachineOASWithTOU)]([https://github.com/worldstar/OpenGA/tree/master/instances/SingleMachineOASWithTOU](https://github.com/worldstar/OpenGA/tree/master/instances/SingleMachineOASWithTOU)) (accessed on 14 January 2020).