# Blocking Cyclic Job-Shop Scheduling Problems
## 4 Blocking Cjss Problem with Sequence-Dependent Setup Times
### Blocking CJSS Problem with Nonanticipatory Sequence-Dependent Setups (NS)  
As mentioned previously, NS need both the job and machine to be available. The constraints sets (12) and (13) were modified as follows to ensure that the operational sequence restrictions of jobs on machines according to the inequalities in Equation (17) in the nonanticipatory case.  
\[\begin{split} D_{j,\rho(j,m)}+NS_{j,j^{\prime},m}+P_{j^{\prime}, \rho(j^{\prime},m)}-\widehat{M}\left(1-X_{j,j^{\prime},m}+B_{j^{\prime},m} \right)\leq D_{j^{\prime},\rho(j^{\prime},m)}\\ \forall\ m\in M,\ j\
eq j^{\prime}\in J_{m}\\ D_{j,\rho(j,m)}+NS_{j,j^{\prime},m}+P_{j^{\prime},\rho(j^{\prime},m)} \leq D_{j^{\prime},\rho(j^{\prime},m)}+T\\ \forall\ m\in M,\ j\
eq j^{\prime}\in J_{m}\end{split} \tag{22}\]  
Moreover, nonanticipatory setups directly affect the processing constraints as presented in Figure 2 for job \(j^{\prime}\). The relationship between two consecutive operations of a job is stabilized considering the NS and processing time. NS need both the job and machine to be available, and hence, between two consecutive operations of a job there will be a time period to perform the NS. As a result, the NS directly affect the processing constraints. The inequalities in Equations (2) and (3) were presented for the case without any sequence-dependent setup times. To ensure these restrictions applied between two consecutive operations of a job in CJSS with NS, the inequalities in Equations (2) and (3) were extended to Equations (24) and (25).  
\[D_{j,i-1}+NS_{j^{\prime},j,m}+P_{j,i}\leq D_{j,i} \tag{24}\]  
\[D_{j,i-1}+NS_{j^{\prime},j,m}+P_{j,i}\leq D_{j,i}+T \tag{25}\]  
where job \(j^{\prime}\) operates on machine \(m\) before job \(j\), and \(NS_{j^{\prime},j,m}\) is the sequence-dependent NS. The variable \(R\) determined the occupying conditions, and hence, the processing constraints sets (4) and (5) were modified as constraints sets (26) and (27) based on Equations (24) and (25).  
\[\begin{split} D_{j,\rho(j,m)-1}+X_{j^{\prime},j,m}\times NS_{j^{ \prime},j,m}+P_{j,\rho(j,m)}-W\,R_{j,m}\leq D_{j,\rho(j,m)}\\ \forall\ m\in M,j\
eq j^{\prime}\,I_{m},1<o(j,m)\\ D_{j,\rho(j,m)-1}+X_{j^{\prime},j,m}\times NS_{j^{\prime},j,m}+P_ {j,\rho(j,m)}\leq D_{j,\rho(j,m)}+T\\ \forall\ m\in M,j\
eq j^{\prime}\in J_{m},1<o(j,m)\end{split} \tag{26}\]  
Thus, the proposed MILP model for the CJSS problem with sequence-dependent nonanticipatory setups was extended as follows:  
\[[MIP-NS]\left\{\begin{array}{ll}\text{minimise}&T\\ \text{subject to}&\\ &Constraints\ sets:\ (\ (1),\ (6)-(10),\ (15),\ (22)-(27)\\ &T\geq D_{j,\rho(j,m)}\ \ \forall\ m\in M,\ j\in J_{m}\\ &X,R,B\ \in\ \{0,1\}\\ &T,D\ \in\ \mathbb{R}^{+}\\ &U\ \in\ \mathbb{R}\end{array}\right.\]  
The size of the basic formulation, as a function of an instance size with \(J\) jobs and \(K\) machines, is \(\mathcal{O}(J^{2}K)\) variables and \(\mathcal{O}(J^{2}K)\) constraints. The size is dominated by the \(X_{j,j^{\prime},m}\) variables with corresponding separation constraints (12)-(15) for each such \(X\) variable. The anticipatory and nonanticipatory variants simply modify the separation constraints but add neither new variables nor additional constraints.