# Bi-Objective Dynamic Multiprocessor Open Shop Scheduling: An Exact Algorithm
## 3 Materials and Methods
### Exact Algorithm  
One of the efficient mathematical programming methods that can be used to generate the set of optimal non-dominated solutions is the \(\varepsilon\)-constraint method. It is based on the idea of solving a single-objective mathematical programming model in which one objective is selected, while the values of the other objectives are bounded by upper or lower limits. These limits are the \(\varepsilon\) values which are iteratively updated in an organized fashion to obtain the desired set of non-dominated solutions. As pointed out by [PERSON] [35], the \(\varepsilon\)-constraint method has several advantages over the weighing method that attempts to generate the set of non-dominated solutions by solving a single-objective model in which the objective function is the weighted summation of the considered objectives.  
For the application of the \(\varepsilon\)-constraint method to the studied DMOSP, consider an MILP model composed of the Objective Function (1) and the Constraints (3) to (13). This model is denoted DMOSP-CMAX model. In addition, consider an MILP model composed of the Objective Function (2) and the Constraints (3) to (13), in addition to the \(\varepsilon\)-constraint defined by the Inequality (14). This model is denoted DMOSP-MWFT(\(\varepsilon\)):  
\[C_{max}\leq\varepsilon \tag{14}\]  
Based on the two models, DMOSP-CMAX and DMOSP-MWFT(\(\varepsilon\)), Algorithm 1 outlines the steps of the proposed \(\varepsilon\)-constraint method for the DMOSP.  
```
1:procedure\(\varepsilon\)-constraint( )
2:Input: DMOSP instance
3:Output: Set of non-dominated schedules (\(\mathcal{P}\))
4:\(s_{0}\) = solution of DMOSP-CMAX
5:\(\underline{C}_{max}\) = \(C_{max}(s_{0})\)
6:\(\mathcal{P}=\emptyset\)
7:\(s_{1}\) = solution of DMOSP-MWFT(\(\mathbb{M}\))
8:\(\mathcal{P}=\mathcal{P}\cup\{s_{1}\}\)
9:\(\varepsilon\) = \(\max\limits_{j\in\mathcal{J}}\left\{c_{j}(s_{1})\right\}\) - \(\delta\)
10:while\(\varepsilon>\underline{C}_{max}\)do
11:\(s\) = solution of DMOSP-MWFT(\(\varepsilon\))
12:\(\mathcal{P}=\mathcal{P}\cup\{s\}\)
13:If\(MWFT(s)=MWFT(s_{1})\)then\(\mathcal{P}=\mathcal{P}\backslash\{s_{1}\}\)
14:\(s_{1}=s\)
15:\(\varepsilon\) = \(\max\limits_{j\in\mathcal{J}}\left\{c_{j}(s)\right\}\) - \(\delta\)
16:endwhile
17:endprocedure
```  
**Algorithm 1**\(\varepsilon\)-constraint method for DMOSP  
Algorithm 1 starts its iterations by solving the DMOSP-CMAX model. The resultant \(C_{max}\) is the lowest value that can be achieved for the makespan for the given instance, which is denoted \(\underline{C}_{max}\). This is followed by iteratively solving the DMOSP-MWFT(\(\varepsilon\)) model at different values of \(\varepsilon\). These iterations start with a sufficiently large value of \(\varepsilon\) at \(\mathbb{M}\) which allows for obtaining the minimum value of the \(MWFT\) objective. After solving the DMOSP-MWFT(\(\varepsilon\)) model, the value of \(\varepsilon\) is set equal to a value that is just below the maximum completion time among all jobs of the resultant solution by a small deviation \(\delta\). The value of \(\delta\) needs to be sufficiently small to be able to enumerate all non-dominated solutions. Whenever all \(r_{j}\), \(a_{m}\) and \(d_{j,w,m}\) values are integers, \(\delta\) can be any decimal number in the range [0,1].  
The solution of the DMOSP-MWFT(\(\varepsilon\)) model will have a \(MWFT\) value that is not larger than the previously obtained solution \(s_{1}\). If they have equal \(MWFT\) values, the new solution \(s\) dominates \(s_{1}\), which means that the latter must be removed from the Parto set, which is denoted \(\mathcal{P}\).  
It is important to note here that the initial solution \(s_{0}\) obtained by solving the DMOSP-CMAX model is not included in the efficient non-dominated set \(\mathcal{P}\). Instead, the final solution obtained in the last step of the iterations is included. This solution has the same makespan as \(s_{0}\), while its \(MWFT\) value is not larger than that of \(s_{0}\).