## 3 Developed Solution Approach
### Measuring Dissimilarity between Two Solutions  
An essential characteristic of the scatter search metaheuristic is maintaining diversity among the solutions in the reference set \(\mathcal{R}\) along with their quality throughout both the initialization and the improvement phases. Accordingly, before a solution to set \(\mathcal{R}\) is added, its dissimilarity with existing solutions in this set is checked. This is done here by measuring the degree of dissimilarity, which is defined for any two solutions \(\mathbb{S}^{1}\) and \(\mathbb{S}^{2}\) using a distance function denoted as \(\Delta(\mathbb{S}^{1},\mathbb{S}^{2})\), which is provided in Abdelmaguid [29]. A solution can be added only when its evaluated distances with all existing solutions in set \(\mathcal{R}\) exceed a predefined limit.  
The distance function \(\Delta(\mathbb{S}^{1},\mathbb{S}^{2})\) is based on comparing the vectors of permutations of the two solutions, \(\mathbb{S}^{1}\) and \(\mathbb{S}^{2}\), and counting the minimum number of moves that are needed to convert one solution to another. To illustrate how the distance function \(\Delta(\mathbb{S}^{1},\mathbb{S}^{2})\) is evaluated, consider the two sample solutions shown in Figure 4 for the Bi-DMOSP instance described in Section 3.2. Determining the minimum number of moves required to convert the two strings of the second solution's chromosome involves the determination of the common sub-strings in both chromosomes and then choosing the moves that will result in the minimal number of common sub-strings in the resulting strings. Details are provided in [29] for a computationally efficient algorithm that can be used for that task. Figure 5 illustrates the minimal moves that are required to convert the chromosome of the second solution into the first one's. The first move (labeled with the circled number 1 in Figure 5) corresponds to exchanging the positions of operations D1 and D3 in the jobs' string. Meanwhile, the move labeled with the number 3 corresponds to moving operation F1 after the position of the machine separator while shifting operation E1 backward in the workstations' string. Such a move changes the sequence of processing for the operations of the machines of the workstation, and it changes the machine assignment for operation F1. Other moves are conducted similarly. As a result of the illustrated minimal moves, the distance between both solutions equals 5 in this case.  
Figure 4: Chromosomes of two sample solutions to the sample DMOSP instance presented in Section 3.2: (**a**) first solution and (**b**) second solution.  
This distance function's advantage is that it does not depend on the objective functions' values, enabling the search procedures to explore diverse areas in the search space. To explain, consider the two sample solutions presented in Figure 4. The objective functions' values for the first solution, \(\mathbb{S}^{1}\), are \(C^{1}_{max}=327\) and \(MWFT^{1}=1134\), and for the second solution, \(\mathbb{S}^{2}\), they are \(C^{2}_{max}=353\) and \(MWFT^{2}=1372.33\). Accordingly, the differences between the objective functions' values for both solutions are not a small quantity compared to the value of \(\Delta(\mathbb{S}^{1},\mathbb{S}^{2})=5\). Therefore, if the distance based on the differences between the objective functions' values is utilized, both solutions would have been added to the reference set. Nevertheless, in this case, one of the solutions would easily reach the same structure as the other one in a few neighborhood search moves. Therefore, using the value of \(\Delta(\mathbb{S}^{1},\mathbb{S}^{2})\) will ensure true diversity as related to the neighborhood search moves that are utilized in the local search procedure based on tabu search.