## 2 Disjunctive Formulation of Job Shop Scheduling Problem  
The disjunctive formulation has several sets: A set \(J\) of \(n\) jobs, where, \(J=\{J_{1},J_{2},\ldots,J_{n}\}\); a set \(M\) of \(m\) machines where \(M=\{M_{1},M_{2},\ldots,M_{m}\}\); and a set \(O\) of operations where \(O=\{1,\ 2,\ 3,\ldots\}\). These operations form \(k\) subsets of operations for each one of the jobs \((J_{k}\subseteq O)\) and machines \((M_{k}\subseteq O)\).  
Each operation \(i\) has a processing time of \(p_{i}\). In a job \(J_{k}\), each pair of operations \(i,j\) possesses a relationship of precedence \((i<j)\). Only one operation performed by a machine \(M_{k}\), can be executed at any given point in time. Given the previously mentioned problem restrictions, the function of the starting time, s of each operation can be represented in the following manner:  
The constraint in (1) indicates that the starting time of the operation \(j\) must be greater than or equal to zero; meaning only positive values are accepted. The constraint in (2) is a precedence constraint. It indicates that within one job which contains operations \(i\) and \(j\), in order for \(j\) to begin, \(i\) must be completed. The constraints in (3) are disjunctive. These constraints ensure that two operations, \(i\) and \(j\), which are performed by the same machine \(M_{k}\) are not carried out simultaneously. The constraints in (4) indicate that the time necessary to complete an operation \(j\) must be less than or equal to the makespan (\(C_{max}\)). The objective is to minimize the makespan, defined as the maximum time of completion of the last job, which is determined according to the starting times, and can be expressed as (5). The time units in the makespan are open, thus they can be assigned as seconds, minutes, hours, and so on, as long as these are consistent units. In this work the makespan is simply labeled as units of time.  
\[\forall i\in O,\ s_{i}\geq 0 \tag{1}\]  
\[\forall(i,j)\in O\land(i<j)\in J_{k}\ (s_{i}+p_{i})\leq s_{j} \tag{2}\]  
\[\forall(i,j)\in O\ \land\ (i,j)\in M_{k}\ \ (s_{i}+p_{i})\leq s_{j}\lor\left(s_{j}+p_ {j}\right)\leq s_{i} \tag{3}\]  
\[\forall i\in O\ (s_{i}+p_{i})\leq C_{max} \tag{4}\]  
\[min(f)=min\left[\frac{max}{i\in O}(s_{i}+p_{i})\right] \tag{5}\]  
Figure 1 shows the disjunctive graph model G = (A, E, O) for a JSSP of \(3\times 3\) (three machines and three jobs). This disjunctive graph is formed by three sets. The operations set, O, is made up of the nodes in G, numbered one to nine. The processing time appears next to each operation. The beginning and ending operations (I and * respectively) are fictitious, with processing times equal to zero. The set A is composed of conjunctive arcs, each one of these arcs unites a pair of operations that belongs to the same job \(J_{i}\) and each one represents a precedence constraint. The operations 1, 2, and 3 are connected by these arcs and therefore form job one (\(J_{1}\)). Jobs two (\(J_{2}\)), and three (\(J_{3}\)) are connected in the same way with operations (4, 5, 6) and (7, 8, 9), respectively. Each clique that belongs to E contains a subset of operations that are executed by the same machine (\(M_{k}\)). Operations 1, 6, and 7 are executed by \(M_{1}\) and generate a clique. Machines two (\(M_{2}\)) and three (\(M_{3}\)) generate a clique, each one with operations (2, 5, 8) and (3, 4, 9), respectively. The resources capacity constraints are represented between each pair of operations in E.