# Bi-Objective Dynamic Multiprocessor Open Shop Scheduling: An Exact Algorithm
## 3 Materials and Methods
### Demonstrative Example  
To demonstrate the application of the \(\varepsilon\)-constraint method in solving the DMOSP based on the presented MILP model, consider a small maintenance shop consisting of five workstations \(\mathcal{W}=\{1,2,3,4,5\}\). The sets of machines are defined as \(M_{1}=\{m_{1,1}\}\), \(M_{2}=\{m_{2,1},m_{2,2}\}\), \(M_{3}=\{m_{3,1},m_{3,2}\}\), \(M_{4}=\{m_{4,1}\}\) and \(M_{5}=\{m_{5,1}\}\). At the beginning of the schedule (i.e., at time zero), all machines are ready, i.e., \(a_{m}=0\ \forall m\in\mathcal{M}\). Four outstanding jobs, \(\mathcal{J}=\{A,B,C,D\}\) with priorities \(p_{A}=2\), \(p_{B}=4\), \(p_{C}=10\) and \(p_{D}=6\), are waiting to be processed, i.e., \(r_{j}=0\ \forall j\in\mathcal{J}\). Table 1 provides the required workstations and processing times for the jobs. The corresponding MILP model is prepared using the OPL language [36] and is solved using IBM ILOG CPLEX version 12.8. The value of \(\mathbb{M}\) is set to 10,000 and the value of \(\delta\) is chosen to be 0.1. A total of four solver runs are needed to generate the set of non-dominated solutions, one using the DMOSP-CMAX model and three iterations using the DMOSP-MWFT(\(\varepsilon\)) model. Figure 1 shows the Gantt charts of the generated three non-dominated schedules. As demonstrated in Figure 1, despite the relatively small differences in the values of the two objective functions, the three schedules exhibit large discrepancies in the processing sequences on machines and job routes. Of course, the small differences in the values of the objective functions will accumulate over the scheduling periods affecting the system's performance on the long run. Next, we demonstrate how the developed model and the \(\varepsilon\)-constraint algorithm can be used for guiding the rescheduling decisions whenever a new job arrives to the system during the execution of a selected schedule. Consider a situation in which the decision maker chooses \"Schedule #2\" from the set of the originally generated non-dominated schedules shown in Figure 1. A new job \(E\) arrives at time 80 which requires the processing on workstations 1, 3, and 5, and has a priority \(p_{E}=10\). Assuming that the processing intervals provided by Schedule #2 are strictly followed with no deviation, the rescheduling problem can be formulated using the developed MILP model as follows. Since the processing of a job cannot be interrupted, the unfinished processes at time 80 will continue and their corresponding finish times define the machine available times. Meanwhile, the remaining operations that did not start yet at time 80 form a modified set of jobs which are denoted \(\bar{A}\), \(\bar{B}\), \(\bar{C}\) and \(\bar{D}\) and their priorities remain unchanged. Table 2 shows the corresponding machine available times, job ready times, and the processing times for the rescheduling problem. The \(\varepsilon\)-constraint method is applied to the rescheduling problem. Three non-dominated schedules are generated with the following pairs of objective function values (\(C_{max}\), \(MWFT\)): (257, 816), (252, 816.8), and (242, 826.8). If the decision maker opts to choose the schedule with the minimum makespan, the corresponding Gantt chart of the modified schedule is shown in Figure 2. \begin{table}
\begin{tabular}{l c c c c c c} \hline \hline \multirow{2}{*}{**Jobs**} & \multicolumn{6}{c}{**Workstations**} \\ \cline{2-7}  & **1** & **2** & & **3** & **4** & **5** \\ \cline{2-7}  & \(m_{1,1}\) & \(m_{2,1}\) & \(m_{2,2}\) & \(m_{3,1}\) & \(m_{3,2}\) & \(m_{4,1}\) & \(m_{5,1}\) \\ \hline \(A\) & & 96 & 91 & 57 & 60 & 68 \\ \(B\) & & 84 & 79 & & & 85 \\ \(C\) & 33 & 104 & 85 & 73 & 79 & \\ \(D\) & 44 & 82 & 76 & 56 & 61 & 31 & \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Initially required workstations and processing times for the jobs in the demonstrative example. Figure 1: Optimal Pareto front and the Gantt charts of the corresponding schedules for the demonstrative example.