## 4 Exact Approaches
### On/Off Formulation  
In this model, each binary decision variable \(x_{jt}=1\) indicates whether the order \(j\) is processed at time \(t=r_{j},\ldots,\bar{d_{j}}\), or not \(x_{jt}=0\). In the same way, the binary decision variables \(y_{jt}=1\) corresponds to a unit of processed setup of an order \(j=1,\ldots,n\) at time \(t=r_{j},\ldots,\bar{d_{j}}-p_{j}\). For any order \(j=0,\ldots,n\), the binary decision variable \(a_{j}\) takes value \(1\) if order \(j\) is accepted; \(0\) otherwise. For any pair of orders \(i,j=0,\ldots,n\) the binary decision variable \(u_{ij}\) equals \(1\) if order \(i\) precedes directly order \(j\). Finally the integer decision variables \(T_{j}\in\mathbb{N}\) represent the tardiness of any order \(j=1,\ldots,n\) and \(C_{j}\in\mathbb{N}\) its completion time. The MILP for the TI On/Off formulation is written as follows. \[\textbf{maximize}\sum_{j=1}^{n}\left(a_{j}e_{j}-w_{j}T_{j}-\sum_{t=r_{j}}^{ \bar{d_{j}}}\big{(}x_{jt}+y_{jt}\big{)}c_{jt}\right) \tag{2}\]  
\[\sum_{j=1}^{n}\big{(}x_{jt}+y_{jt}\big{)}\leq 1\qquad t=1,\ldots,T \tag{3}\]  
\[C_{j}\geq(t+1)(x_{jt}-x_{jt+1}) \tag{4}\]  
\[j=1,\ldots,n\quad t=r_{j},\ldots,\bar{d_{j}} \tag{5}\]  
\[C_{j}\leq\bar{d_{j}}a_{j}\qquad j=1,\ldots,n \tag{6}\]  
\[T_{j}\geq C_{j}-d_{j}a_{j}\qquad j=1,\ldots,n \tag{7}\]  
\[\sum_{ \begin{subarray}{c}j=1\\ i\
eq j\end{subarray} }^{n}u_{ij}\leq a_{i}\quad i=0,\ldots,n \tag{8}\]  
\[\sum_{ \begin{subarray}{c}j=0\\ i\
eq j\end{subarray} }^{n}u_{ij}=a_{i}\quad i=1,\ldots,n \tag{8}\]  
\[\sum_{j=1}^{n}x_{jt}=p_{j}a_{j}\qquad j=1,\ldots,n \tag{9}\]  
\[\sum_{t=r_{j}}^{t-p_{j}}x_{jt}+\sum_{t^{\prime}=t+p_{j}}^{\bar{d_{j}}}x_{jt} \leq p_{j}(1-x_{jt}) \tag{10}\]  
\[j=1,\ldots,n,\quad t=r_{j},\ldots,\bar{d_{j}}\]  
\[\sum_{t=r_{j}}^{\bar{d_{j}}-p_{j}}y_{jt}\leq\sum_{ \begin{subarray}{c}i\
eq j \\ i\
eq j\end{subarray} }^{n}s_{ij}u_{ij}\qquad j=1,\ldots,n \tag{11}\]  
\[y_{jt}-y_{jt+1}-x_{jt+1}\leq 0\]  
\[j=1,\ldots,n\quad t=r_{j},\ldots,\bar{d_{j}} \tag{12}\]  
\[\sum_{t^{\prime}=r_{i}+1}^{t-1}x_{it^{\prime}}\geq p_{i}(u_{ij}+y_{jt}-1) \tag{13}\]  
eq j\quad t=r_{j},\ldots,\bar{d_{j}}\]\[\sum_{t^{\prime}=r_{j}}^{t-1}y_{jt^{\prime}}\geq s_{ij}(u_{ij}+x_{jt}-1) \tag{14}\] \[i=0,\ldots,n\quad j=1,\ldots,n\quad i\
eq j\quad t=r_{j},\ldots, \bar{d}_{j}\] \[\sum_{t=0}^{r_{j}-1}x_{jt}=0\qquad j=1,\ldots,n\] (15) \[\sum_{t=0}^{r_{j}-1}y_{jt}=0\qquad j=1,\ldots,n\] (16) \[\sum_{t=\bar{d}_{j}+1}^{T}x_{jt}=0\qquad j=1,\ldots,n\] (17) \[\sum_{t=\bar{d}_{j}-p_{j}+1}^{T}y_{jt}=0\qquad j=1,\ldots,n\] (18) \[x_{00}=1 \tag{19}\]  
The objective function (2) is the maximization of the total profit, i.e., the revenue minus the possible tardiness penalties and the environmental costs. Constraints (3) state that at each time the machine is either doing nothing, processing an order or doing a setup operation. Constraints (4) compute the completion times of order \(j\) by retrieving the instant \(t+1\) when the production ends, that is, when \(x_{jt}=1\) and \(x_{jt+1}=0\). Constraints (5) limit the completion time of an accepted order \(j\) to its deadline. Constraints (6) refer to the calculation of the tardiness of an accepted order \(j\) with its completion time minus its due date. Constraints (7) indicate that an accepted order can have at most a successor. Constraints (8) impose that each accepted order must have a predecessor. Constraints (9) impose to any order \(j\) to be processed exactly \(p_{j}\) time units. Constraints (10) guarantee non-preemption by forcing the contiguity of the decision variables \(x_{jt}\). To be more specific, if at time period \(t\) order \(j\) is produced (\(x_{jt}=1\)), constraints exclude production \(p_{j}\) units before and after \(t\) in \(r_{j},\ldots,t-p_{j}\) and \(t+p_{j},\ldots,\bar{d}_{j}\). Implicitly, this means that order \(j\) is produced in the interval \(t-p_{j}+1,\ldots,t+p_{j}-1\). Constraints (11) define the setup operation of at most \(s_{ij}\) time units between each order \(j\) and its predecessor order \(i\).