## 5 Heuristic Approaches
### Fix-and-Relax Heuristics
#### 5.1.3 On/Off Model  
The TI On/Off model described in Section 4.1 is adapted to suit to the FR heuristic procedure. The previously introduced decision variables \(\alpha_{j}\) and \(\beta_{j}\) are defined by the group of constraints (30), for all \(j\in J_{k}\).  
\[\sum_{l=a_{k}}^{\min(b_{k}\tilde{d_{j}}-p_{j})}x_{jt}\leq p_{j}\alpha_{j}\qquad j \in J_{k} \tag{30a}\] \[\alpha_{j}+\beta_{j}\leq 1\qquad j\in J_{k}\] (30b) \[\alpha_{l}=1,\quad\beta_{l}=0 \tag{30c}\]  
Constraints (30a) give value 1 to \(\alpha_{j}\) as soon as order \(j\) is processed within the OW, i.e., from \(a_{k}\) to \(b_{k}\), provided that it can be processed completely before its deadline \(\tilde{d}_{j}\), and 0 if the order is not produced yet. Constraints (30b) ensure that an order \(j\) is either starting before the end of the OW (\(\alpha_{j}=1\)) or completely produced after (\(\beta_{j}=1\)) or is not scheduled at all (\(\alpha_{j}=0\), \(\beta_{j}=0\)). Constraints (30c) indicate that the previously processed job in the previous step is fixed in the OW and cannot be processed in the AW.  
To make precedence constraints (14) and (15) relevant only for orders in the OW, constraints (7) and (8) are modified in (31) and (32), respectively.  
\[\sum_{\begin{subarray}{c}j\in I_{k}\\ i\
eq j\end{subarray}}u_{ij}\leq\alpha_{i}\quad i\in J_{k}\cup\{l\} \tag{31}\] \[\sum_{\begin{subarray}{c}j\in I_{k}\cup\{l\}\\ i\
eq j\end{subarray}}u_{ji}=\alpha_{i}\quad i\in J_{k} \tag{32}\]  
Constraints (31) state that an order \(i\) scheduled in the OW can have at most a successor order \(j\). Constraints (32) ensure that if order \(i\) is processed during the OW, it must have exactly a predecessor order \(j\). These reformulated constraints imply that any order \(i\) that are scheduled in the AW have \(u_{ij}\) values set to zero, as a consequence the right-hand side of constraints (14) and (15) are canceled.  
Expressions of constraints (33) and (34) are replaced by  
\[\begin{split}\sum_{t^{\prime}=\max\{\tau_{j},a_{k}\}}^{t-1}y_{ji^{ \prime}}\geq s_{ij}(u_{ij}+x_{\mu}-1)-s_{ij}\beta_{j}\\ i\in J_{k}\cup\{l\}\quad j\in J_{k}\\ t=\max\{r_{j},a_{k}\},\ldots,\min\{\bar{d}_{j},b_{k}\}\end{split} \tag{33}\]  
Constraints (33) ensure that when an order \(j\) starts in the AW (\(\beta_{j}=1\)), the right-hand side is canceled and thus the \(y_{ji}\) are free. This implies that the setup times between order \(i\) and \(j\) are not forced to last at least \(s_{ij}\) time-units.  
\[\begin{split}\sum_{t^{\prime}=\max\{a_{k},r_{j}\}+1}^{t-1}x_{it^{ \prime}}\geq p_{i}(u_{ij}+y_{ji}-1)-p_{i}\beta_{j}\\ i=J_{k}\cup\{l\}\quad j\in J_{k}\quad i\
eq j\\ t=\max\{r_{j},a_{k}\},\ldots,\min\{\bar{d}_{j},b_{k}\}\end{split} \tag{34}\]  
In the same way, constraints (34) ensure that when an order \(j\) starts in the AW (\(\beta_{j}=1\)), the right-hand side of the constraint is canceled. This means that if an order \(i\) (whether \(\beta_{i}=1\) or \(\beta_{i}=0\)) precedes an order \(j\) that is known to be processed in the AW, the setup operation order \(j\) is not constrained to starts \(p_{i}\) units after the processing of order \(i\). The objective function (2) is rewritten as follows, where \(lb=\max\{r_{j},a_{k}\}\) and \(ub=\min\{\bar{d}_{j},b_{k}\}\).  
\[\textbf{maximize}\sum_{j\in J_{k}}(\alpha_{j}e_{j}-w_{j}T_{j}-\sum_{t=lb}^{ub }\big{(}x_{jl}+y_{ji}\big{)}c_{jl}+r\beta_{j}e_{j}) \tag{35}\]  
In expression (35), the real profit is calculated for any order \(j\in J_{k}\) that is scheduled in the OW. The profit of orders that are scheduled in the AW is approximated by \(r\beta_{j}e_{j}\) with \(r=0.8\) this is the revenue discounted by a rate \(r\). It encourages the model to schedule orders as much as possible in the OW.