# Bi-Objective Dynamic Multiprocessor Open Shop Scheduling: An Exact Algorithm
## 3 Materials and Methods
### Mixed Integer Linear Programming Model  
Mathematical programming models can be used to solve small instances and can provide a basis of efficient algorithmic developments for the scheduling problems. In combinatorial optimization problems, like the studied DMOSP, different mathematical programming models can be developed for the same problem [27]. In the scheduling literature, MILP models can be classified into three types depending on how the binary scheduling decision variables are defined. These types are firstly appeared in the literature of the job shop scheduling problem. The first type is a discrete-time model in which the time span of the schedule is divided into small time units and the binary decision variables are related to the assignment of one time unit on a machine to process a given job. This model is due to [PERSON] [28]. It is not favored in most of the published work due to the huge number of decision variables and the complexity of formulating the constraints. The other two MILP models utilize different binary decision variables for representing permutations of operations. Permutations for the OSP and its generalizations refer to both the processing sequences of jobs on machines or the visiting order of jobs to workstations. The second MILP model is due to [PERSON] [29]. It is a permutation-position model in which binary variables are defined to decide whether an operation is assigned to a position in a permutation or not. The third MILP model is due to [PERSON] [30]. It is a disjunctive model in which permutations are indirectly represented by a pairwise job precedence relationships; that is, if job \(j\) succeeds job \(k\), the binary variable takes the value of one, and it takes a value of zero, otherwise. In the scheduling literature, comparisons of the different MILP models are provided for the flow shop scheduling problem [31], for the OSP [32], for the flexible job shop scheduling [33] and for the job shop scheduling problem [34]. The disjunctive MILP models have less size in terms of the number of decision variables and number of Constraints [32]. In terms of the speed of an MILP solver of finding optimal solutions, [PERSON] et al. [31] found out that permutation-position models can provide quicker results for the flow shop scheduling problem. This may be due to the structure of problem in which processing order on machines is naturally represented by permutations while jobs have fixed order in visiting the machines. On the other hand, for the flexible job shop scheduling problem, the computational experiments by [PERSON] and [PERSON] [33] show that the disjunctive models provide quicker results. The same conclusion is confirmed by [PERSON] and [PERSON] [34] for the job shop scheduling problem. For the MOSP, [PERSON] [20] developed a disjunctive model for the objective of minimizing the makespan. In this paper, that model is extended for the multi-objective DMOSP. The following are the lists of the used notations. Sets:  
\[ \begin{array}{llll}\mathcal{W}&=&\text{Set of workstations}=\{1,2,3,\ldots\}\\ M_{w}&=&\text{Set of parallel machines in workstation}\ w\in\mathcal{W}\\ \mathcal{M}&=&\bigcup_{w\in\mathcal{W}}M_{w}=\text{Set of all machines in the system}\\ \mathcal{J}&=&\text{Set of arriving jobs}\\ W_{j}&=&\text{Subset of workstations required for job }j\in\mathcal{J}\\ J_{w}&=&\text{Subset of jobs that require processing on workstation}\ w\in\mathcal{W}\\ O_{j}&=&\text{Set of operations of job }j\in\mathcal{J}\\ \mathcal{O}&=&\bigcup_{j\in\mathcal{J}}O_{j}=\text{set of all operations to be processed}\\ \end{array} \]  
Indexes and labels:  
\[ \begin{array}{llll}w,q&=&\text{Workstation indexes from set }\mathcal{W}\\ m&=&\text{Machine index from set }\mathcal{M}\\ j,k&=&\text{Job indexes from set }\mathcal{J}\\ o_{j,w}&=&\text{Label for the operation of processing job }j\in\mathcal{J}\text{ in workstation }w\in W_{j}\\ \end{array} \]  
Given data:  
\[