# Blocking Cyclic Job-Shop Scheduling Problems
## 3 Mathematical Formulation of a Basic Model
### Operational Constraints of Each Machine  
The operational sequence constraints prevent the formation of conflicts in the usage of machines. Each machine should be unloaded before loading the next part on it and starting its processing operation. Figure 11 illustrates the operational sequence of parts on machines in the case where machine \(m\) is occupied or free at the start of the cycle.  
To state the relation between the last and first parts of consecutive operations, the variable \(B\) is used. Variable \(B\) determines the first part that leaves each machine during the cycle time and the following constraints set (9) guarantees that each machine will have just one.  
\[\sum_{j\in J_{m}}B_{j,m}=1\qquad\forall\ m\in M \tag{9}\]  
It is clear that if a machine is occupied by some part at the start of the cycle, then this part will be the first to depart, resulting in the following constraint set:  
\[R_{j,m}\leq B_{j,m}\qquad\forall\ m\in M,\ j\in J_{m} \tag{10}\]  
Due to the operational sequence of parts on machines when the part \(j^{\prime}\) is the successor of part \(j\) on machine \(m\) then either  
\[D_{j,i}+P_{j^{\prime},j^{\prime}}\leq D_{j^{\prime},j^{\prime}}\quad\text{ or }\quad D_{j,i}+P_{j^{\prime},j^{\prime}}\leq D_{j^{\prime},j^{\prime}}+T. \tag{11}\]  
The second inequality only holds for the case where \(j\) is the last part to depart from machine \(m\) before the end of the cycle and \(j^{\prime}\) departs at the start of the next cycle. The following constraints sets (12) and (13) are proposed based on these inequalities:  
\[D_{j,\alpha(j,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)}\qquad\forall\ m\in M,\ j\
eq j ^{\prime}\in J_{m} \tag{12}\] \[D_{j,\rho(j,m)}+P_{j^{\prime},\rho(j^{\prime},m)} \leq D_{j^{\prime},\rho(j^{\prime},m)}+T\quad\forall\ m\in M,\ j\
eq j ^{\prime}\in J_{m} \tag{13}\]  
Figure 11: The operational sequencing restrictions of any machine \(m\); (**a**,**b**) presents the restriction when \(m\) is occupied and free at the start of the cycle, respectively.  
It should be also noted that in the case of a zero buffer between the machines, the completed parts have to remain on the machines until the machine for performing its next operation becomes available. If part \(j^{\prime}\) is the successor of part \(j\) on machine \(m\) then  
\[D_{j,\rho(j,m)}\leq\begin{cases}D_{j^{\prime},\rho(j^{\prime},m)-1}+T&\text{if machine $m$ is idle at the start of the cycle with first job $j^{\prime}$}\\ D_{j^{\prime},\rho(j,m)-1}&\text{otherwise}\end{cases} \tag{14}\]  
Note that the first case only arises if \(j\) departs \(m\) at the end of a cycle but part \(j^{\prime}\) does not arrive until the start of the next cycle. The constraints set (15) is formulated based on this inequality as follows:  
\[D_{j,\rho(j,m)}-M(1-X_{j,j^{\prime},m}+B_{j^{\prime}m}-R_{j^{\prime}m})\leq D _{j^{\prime},\rho(j^{\prime},m)-1}\hskip 56.905512 pt\forall\ m\in M,\ j\
eq j^{\prime}\in J _{m},1<o(j^{\prime},m) \tag{15}\]  
This inequality holds if (a) \(j^{\prime}\) is after \(j\) on machine \(m\) so \(X_{j,j^{\prime},m}=1\) and (b) we do not have \(B_{j^{\prime},m}-R_{j^{\prime},m}=1\) which would indicate that job \(j^{\prime}\) arrived after the start of the cycle.