## 5 Heuristic Approaches
### Dynamic Island Model
#### 5.2.1 Principle
To prevent duplicate orders in the child solution, the orders appearing in the children that have already been inserted are not considered (Figure 7). #### 5.2.5 Initial Population

The initial population is built with 80% of random solution. The other 20% of the population are created with greedy heuristics. Random Solution

This procedure starts by inserting all orders to the sequence and shuffle it. Then, completion times are calculated. This greedy heuristic sorts the sequence of orders using the Earliest Released Job rule. Completion times are computed accordingly. Figure 7: Example of the crossover operator application. m-ATCS

This greedy heuristic is taken from the work of [PERSON] et al. [38]. The procedure starts with \(L=1,\ldots,n\) the list of orders, \(l=0\) the initial scheduled order and \(t=0\) the starting time. It iteratively inserts order \(i\) from \(L\) into a sequence \(s\) using the Apparent Tardiness Cost with Setups (ATCS) index at time \(t\), knowing the previous scheduled order \(l\). The formula is given in Equation (45). The order \(i\) with the largest ATCS(\(i\),\(l\),\(t\)) is added in \(s\) and erased from \(L\), then \(t\) is set to \(\max(t,r_{i})+p_{i}+s_{l,i}\). This continues until \(L\) is empty. Completion times are computed according to this sequence. \[\text{ATCS}(i,l,t)=\frac{e_{i}}{p_{i}}e^{\max(d_{i}-p_{i}-t,0)/p}e^{-s_{l,i}/s} \tag{45}\]

In (45), \(s\) corresponds to the average setup times and \(\bar{p}\) refers to the average processing times. ## 6 Computational Results

### Experimental Design

Experimental designs aim at determining levels of influence and interaction of external factors on a process. In this research, both the FR heuristics and the metaheuristic depend on many factors such as the OW length or the setup values for the FR heuristics and such as the mutation, crossover or learning rates for the DIM metaheuristic. Taguchi method has been chosen to carry out these experimental designs for the proposed approaches. The reasons are that this easy-to-implement method has proven itself to be efficient and robust to tune GA and heuristics in this domain. Details are available in the Appendix A. ### Benchmark and Material

The benchmark is from [PERSON] et al. [12] with sequence-dependent setup times. It contains 45 instances with various number of orders \(n=10,15,25,50,100\) and two parameters to control the tardiness factor \(\tau=0.1,0.5,0.9\) and the due date range \(R=0.1,0.5,0.9\). These parameters aim at having a diverse set of instances. Figures 8 and 9 illustrate the impact of \(\tau\) and \(R\) on instance characteristics. The instances represented share the same processing times \(p\) but differ on release dates \(r\), due dates \(d\) and deadlines \(\bar{d}\) depending on the value of \(\tau\). In the figures, the possible production span between \(r_{j}\) and \(d_{j}\) for an order \(j\) is indicated as a white rectangle, whereas the penalty interval between \(d_{j}\) and \(\bar{d}_{j}\) is indicated as a gray rectangle. Figure 8: Influence of \(\tau\) on instance characteristics (with \(R\) fixed). As displayed in Figure 8, the value of \(\tau\) determines the dispersion of the release dates (\(r_{j}\)) as well as the production slack, that is, the length of the production interval between release and due dates (\(d_{j}\)). The greater \(\tau\) is, the more scattered the release dates are and the less flexible the production is. Note that more flexibility increases the combinatorial aspect of the problem. In Figure 9, the impact of \(R\) on the instances is shown. \(R\) controls the length of the interval for each order \(j\) between due dates (\(d_{j}\)) and deadlines (\(\tilde{d}_{j}\)), that is, the penalty interval. \(R\) affects also the slope of the tardiness penalty (\(w_{j}\)). When \(R\) is large, the penalty interval is large as well and the tardiness penalty decreases less quickly. The implementation of the FR heuristics has been made in C++17 using the IBM CPLEX library \(v.12.10\).