# Solving Non-Permutation Flow Shop Scheduling Problem with Time Couplings
## 2 Problem Formulation
### Mathematical Model  
Let \(\mathcal{J}=\{1,2,\ldots,n\}\) and \(\mathcal{M}=\{1,2,\ldots,m\}\) be sets of \(n\) jobs and \(m\) machines, respectively. Each job \(j\) is composed of \(m\) operations from the set \(\mathcal{O}_{j}=\{l_{j}+1,\ l_{j}+2,\ \ldots,\ l_{j}+m\}\), where \(l_{j}=m(j-1)\). Thus, there are \(nm\) operations in total and sets \(\mathcal{O}_{j}\) partition set \(\mathcal{O}\)--the set of all operations. Each job \(j\) has to be processed on the machines in the natural order: \(1\to 2\rightarrow\cdots\to m\). The processing time of job \(j\) on machine \(i\) (i.e., operation \(l_{j}+i\)) is denoted \(p_{i,j}>0\). Moreover, let \(\hat{r}_{i}\geq 0\) denote the minimum idle time machine \(i\) is allowed between the processing of subsequent operations. Similarly, \(\hat{d}_{i}\geq\hat{r}_{i}\) denotes the maximum idle time. While the order in which jobs are processed is fixed, the processing order for each machine is a decision variable. Let \(\pi_{i}\) be an \(n\)-element sequence of jobs that are to be processed on machine \(i\), such that \(\pi_{i}(j)\) is the \(j\)-th job to be processed on \(i\). Then, the overall processing order is given by sequence \(\pi=(\pi_{1},\pi_{2},\ldots,\pi_{m})\). Sequence \(\pi\) will be called a solution. Based on solution \(\pi\), one can build a corresponding _schedule_. The schedule \((S,C)\) consists of two matrices. The first matrix is given by \(S=[S_{i,j}]^{m\times n}\), where \(S_{i,j}\) is the starting time of the \(j\)-th operation to be processed on machine \(i\) in \(\pi\). Similarly, we can define the matrix of operation completion times \(C=[C_{i,j}]^{m\times n}\), where element \(C_{i,j}\) is the completion time of \(j\)-th operation to be processed on machine \(i\) according to \(\pi\). For a schedule \((S,C)\) to be feasible, it needs to meet the following constraints:  
\[\forall i\in\mathcal{M}\ \ \forall j\in\mathcal{J} C_{i,j}=S_{i,j}+\rho_{i,j}, \tag{1}\] \[\forall i\in\mathcal{M}\ \ \forall j\in\mathcal{J}\setminus\{1\} \hat{r}_{i}\leq S_{i,j}-C_{i,j-1}\leq\hat{d}_{i},\] (2) \[\forall i\in\mathcal{M}\setminus\{1\}\ \forall j\in\mathcal{J} S_{i,j}\geq C_{i-1,\pi_{i-1}^{-1}(\pi_{i}(j))}, \tag{3}\]  
where \(\rho_{i,j}\) is a shorthand for \(p_{i,\pi_{i}(j)}\), and \(\pi_{i}^{-1}(j)\) is the position of job \(j\) in \(\pi_{i}\) (i.e., \(\pi_{i}^{-1}(k)=j\iff\pi_{i}(j)=k\)). In other words, \(\pi^{-1}\) is inversion of permutation \(\pi\). We also assume, without losing generality, that the first operation on the first machine starts at time \(0\), resulting in \(S_{1,1}=0\). Constraint (1) means the processing of operations cannot be interrupted. Constraint (2) enforces that minimum and maximum machine idle times are respected, but also requires that operation \(a\) on machine \(i\) is only started after previous operation on \(i\) (i.e., machine predecessor of \(a\)) has completed. Similarly, (3) ensures that operation \(a\) of job \(j\) is started only after previous operation of job \(j\) (i.e., the technological predecessor of \(a\)) has completed. From (1), one can observe that a feasible schedule can be described unambiguously by either \(S\) or \(C\), which will be used throughout the paper. A schedule is called _left-shifted_ if no operations can start sooner without violating the constraints or changing the processing order. A method for computing a left-shifted schedule \(S\) from a solution \(\pi\) will be presented in Section 3. **Example 1**. : _Consider the FSSP instance from Table 1 for \(n=5\), \(m=3\) and order of jobs \(\pi=((2,5,4,3,1),\ (2,4,5,1,3),\ (4,5,2,1,3))\).