# Bi-Objective Dynamic Multiprocessor Open Shop Scheduling: An Exact Algorithm
## 3 Materials and Methods
### Mixed Integer Linear Programming Model
\begin{array}{llll}a_{m}&=&\text{Non-negative ready time of machine }m\in\mathcal{M}\\ r_{j}&=&\text{Non-negative release (arrival) time of job }j\in\mathcal{J}\\ p_{j}&=&\text{Priority of job }j\in\mathcal{J}\\ d_{j,w,m}&=&\text{Processing time of operation }o_{j,w}\text{ on machine }m\in M_{w}\\ \end{array} \]  
Decision variables:  
\[ \begin{array}{llll}x_{j,w,q}&=&\text{A binary variable that equals 1 if operation }o_{j,w}\text{ is processed before operation }o_{j,q}\text{ and equals 0, otherwise,}\\ &&\text{where }w,q\in W_{j}\,\&\,q>w\\ y_{j,w,m}&=&\text{A binary variable that equals 1 if operation }o_{j,w}\text{ is decided to be processed on machine }m\in M_{w}\text{ and equals 0, otherwise}\\ z_{j,k,w,m}&=&\text{A binary variable that equals 1 if operation }o_{j,w}\text{ is processed before operation }o_{k,w}\text{ on machine }m\in M_{w}\text{ and equals 0, otherwise, where }j\
eq k\text{ and }w\in W_{j}\cap W_{k}\\ s_{j,w}&=&\text{Start time of processing operation }o_{j,w}\\ c_{j}&=&\text{Completion time of job }j\\ C_{max}&=&\text{Maximum completion time (makespan)}\\ MWFT&=&\text{Mean weighted flow time}\\ \end{array} \]  
Accordingly, the developed MILP model is formulated as follows:  
\[\text{Minimize} C_{max} \tag{1}\] \[\text{Minimize} MWFT=\sum_{j\in\mathcal{J}}p_{j}\left(c_{j}-r_{j}\right) \Big{/}|\mathcal{J}| \tag{2}\]Subject to the following constraints:  
\[C_{max}\geq c_{j} \forall j\in\mathcal{J} \tag{3}\] \[c_{j}\geq s_{j,w}+\sum_{m\in M_{w}}d_{j,w,m}y_{j,w,m} \forall o_{j,w}\in O_{j}\ \ \forall j\in\mathcal{J}\] (4) \[\sum_{m\in M_{w}}y_{j,w,m}=1 \forall o_{j,w}\in\mathcal{O}\] (5) \[s_{j,w}\geq r_{j} \forall o_{j,w}\in O_{j}\ \ \forall j\in\mathcal{J}\] (6) \[s_{j,w}\geq\sum_{m\in M_{w}}a_{m}y_{j,w,m} \forall w\in W_{j}\ \forall j\in\mathcal{J}\] (7) \[s_{j,q}-s_{j,w}\geq\sum_{m\in M_{w}}d_{j,w,m}y_{j,w,m}-\mathbb{ M}\left(1-x_{j,w,q}\right) \forall w,q\in W_{j}\ \&\ q>w\ \forall j\in\mathcal{J}\] (8) \[s_{j,w}-s_{j,q}\geq\sum_{m\in M_{q}}d_{j,q,m}y_{j,q,m}-\mathbb{ M}x_{j,w,q} \forall w,q\in W_{j}\ \&\ q>w\ \forall j\in\mathcal{J}\] (9) \[z_{j,k,w,m}+z_{k,j,w,m}\leq\frac{1}{2}\left(y_{j,w,m}+y_{k,w,m}\right) \forall m\in M_{w}\ \forall w\in W_{j}\cap W_{k}\ \forall j,k\in\mathcal{J}\ \&\ j\prec_{lex}k\] (10) \[\text{Minimize} MWFT=\sum_{j\in\mathcal{J}}p_{j}\left(c_{j}-r_{j}\right) \Big{/}|\mathcal{J}| \tag{2}\]0  
\[\text{Minimize} MWFT=\sum_{j\in\mathcal{J}}p_{j}\left(c_{j}-r_{j}\right) \Big{/}|\mathcal{J}| \tag{2}\]1 \[\text{Minimize} MWFT=\sum_{j\in\mathcal{J}}p_{j}\left(c_{j}-r_{j}\right) \Big{/}|\mathcal{J}| \tag{2}\]2  
In the developed MILP model, the makespan minimization objective is represented by Equation (1), and the objective of minimizing the mean weighted flow time is represented by Equation (2). Constraints (3) define the relationships between the makespan and the completion times of the jobs; while Constraints (4) relate the completion times of the jobs to the completion times of their operations. Constraints (5) limit the number of machines that will be assigned to an operation to only one in its corresponding workstation. Constraints (6) and (7) restrict the start time of every operation not to be less than the release time of its corresponding job and the available time of its assigned machine. The processing sequence of the operations belonging to a given job (job route) is represented by the disjunctive Constraints (8) and (9). Depending on the relative order of every pair of operations defined by the binary variables \(x_{j,w,q}\), the start time of an operation must be greater than or equal to the finish time of its preceding operation. Constraints (10) and (11) together restrict the disjunctive relationships in Constraints (12) to every pair of operations that are assigned to the same machine. The notation \(j\prec_{lex}k\) is used to represent a lexicographic order of the elements in the set of jobs.