# Near-Optimal Heuristics for Just-In-Time Jobs Maximization in Flow Shop Scheduling
## 3 A Mixed Integer Linear Programming Model  
The flow shop scheduling problem can be generically formulated as follows. Consider a set of \(n\) independent jobs (\(J=\{J_{1}\), \(J_{2}\),..., \(J_{n}\}\)), all of which have the same weight or priority, cannot be interrupted, are released for processing at zero time, have to be executed in \(m\) machines (\(M=\{M_{1}\), \(M_{2}\),..., \(M_{m}\}\)) and are physically arranged to follow identical unidirectional linear flows (i.e., all the jobs are processed through the machines at the same sequence). Each job (\(J_{j}\)) requires a processing time (\(p_{jk}\)) in each machine (\(M_{k}\)) and have its due date represented by \(d_{j}\), both considered known and fixed. The solution consists of finding a schedule that maximizes the number of jobs finished at exactly their respective due dates. To formulate a mathematical model to represent the problem, consider the following parameters, indices and variables. _Parameters and indices:_ \begin{tabular}{l l l} \(n\) & number of jobs \\ \(m\) & number of machines \\ \(i,j\) & job index \\ \(k\) & machine index \\ \(p_{jk}\) & processing time of job \(J_{j}\) on machine \(M_{k}\) \\ \(d_{j}\) & due date of job \(J_{j}\) \\ \(B\) & very large positive integer, the value considered in Section 5 is: \(B=100\sum_{j=1}^{n}\sum_{k=1}^{m}p_{ij}\) \\ \(I_{0}\) & dummy job--the first in the scheduling \\ \(M_{0}\) & dummy machine--theoretically considered before the first (physical) machine \\ _Decision variables:_ \\ \(C_{jk}\) & completion time of job \(J_{j}\) on machine \(M_{k}\) \\ \(U_{j}\) & equals 1 if job \(J_{j}\) is just-in-time or 0 otherwise \\ \(x_{ij}\) & equals 1 if job \(J_{i}\) is assigned immediately before job \(J_{j}\) or 0, otherwise \\  & \(j=0,\ldots,n,j=1,\ldots,n,i\
eq j\). \\ \end{tabular}   
The mixed integer programming model given by Expressions (1)-(12) is based on the approach proposed by [PERSON] et al. (2016). \[\text{Max }Z=\sum_{j=1}^{n}U_{j} \tag{1}\]  
Subject to:  
\[C_{jk}-C_{ik}+B(1-x_{ij})\geq p_{jk},\ i=0,\ldots,n,\ j=1,\ldots,n,\ i\
eq j,\ k=1,\ldots,m \tag{2}\]  
\[C_{jk}-C_{j(k-1)}\geq p_{jk},\ j=1,\ldots,n,\ k=1,\ldots,m \tag{3}\]  
\[C_{jm}-B(1-U_{j})\leq d_{j},\ j=1,\ldots,n \tag{4}\]  
\[C_{jm}+B(1-U_{j})\geq d_{j},\ j=1,\ldots,n \tag{5}\]  
\[\sum_{j=1}^{n}x_{0j}=1, \tag{6}\]  
\[x_{0j}+\sum_{i=1,i\
eq j}^{n}x_{ij}=1,\ j=1,\ldots,n \tag{7}\]  
\[\sum_{j=1,j\
eq i}^{n}x_{ij}\leq 1,\ i=0,\ldots,n \tag{8}\]  
\[C_{j0}=0,\ j=0,\ldots,n \tag{9}\]  
\[C_{jk}\in\Re_{+},\ j=0,\ldots,n,\ k=0,\ldots,m \tag{10}\]  
\[C_{jk}-C_{ik}+B(1-x_{ij})\geq p_{jk},\ i=0,\ldots,n,\ j=1,\ldots,n,\ i\
eq j,\ k=1,\ldots,m \tag{2}\]0  
\[C_{jk}-C_{ik}+B(1-x_{ij})\geq p_{jk},\ i=0,\ldots,n,\ j=1,\ldots,n,\ i\
eq j,\ k=1,\ldots,m \tag{2}\]1  
The optimization criterion expressed in Equation (1) is to maximize the number of just-in-time jobs. Expressions in Equation (2) ensure the consistency of the completion times of jobs, that is, if job \(J_{i}\) immediately precedes job \(J_{j}\) (i.e., \(x_{ij}=1\)), the difference between their completion times on each machine must be at least equal to the processing time of job \(J_{j}\) on the machine considered; otherwise (if \(x_{ij}=0\)), if there is no relationship between the completion times of this pair of jobs, then the constraints in Equation (2) are redundant. Constraints in Equation (3) require that the \(k\)th operation of job \(J_{j}\) be completed after the \((k-1)\)th operation plus the processing time (\(p_{jk}\)). Generally, the value of \(B\) is an upper bound to the makespan. The expressions in Equations (4) and (5) jointly establish that the variable \(U_{j}\) equals 1 if job \(J_{j}\) finishes on time or 0 otherwise. When job \(J_{j}\) does not finish on time, i.e., \(U_{j}=0\), these two sets of constraints become redundant. The constraints in Equation (6) ensure that only one job is assigned to the first position in the sequence (not considering the dummy job \(J_{0}\)).