# Some Results on Shop Scheduling with S-Precedence Constraints among Job Tasks
## 3 Flow Shop
### Two-Machine Flow Shop (\(F2|s-prec|C_{\max}\))  
We next consider the two-machine flow shop problem, so \(p_{1}^{k}\) and \(p_{2}^{k}\) denote the processing times of job \(J_{k}\) on \(M_{1}\) and \(M_{2}\) respectively, \(k=1,\ldots,n\). Note that, as in the classical \(F2||C_{\max}\), with no loss of generality we can assume that in any feasible schedule the machine \(M_{1}\) processes all the jobs consecutively with no idle time between them. We next show that problem \(F2|s-prec|C_{\max}\) can be solved in linear time. **Proposition 2**. : _Given an instance of \(F2|s-prec|C_{\max}\), there always exists a schedule \(\sigma^{*}\) having makespan \(\max\{\sum_{k=1}^{n}p_{1}^{k},\sum_{k=1}^{n}p_{2}^{k}\}\), which is therefore optimal._  
Proof. Given an instance of \(F2|s-prec|C_{\max}\), partition the jobs into two sets, \(J^{\prime}\) and \(J^{\prime\prime}\), such that \(J^{\prime}=\{J^{k}|p_{1}^{k}\leq p_{2}^{k}\}\) and \(J^{\prime\prime}=J\setminus J^{\prime}\). Then, build \(\sigma^{*}\) by scheduling, on both machines, first all jobs of \(J^{\prime}\) in arbitrary order, and then all jobs of \(J^{\prime\prime}\), also in arbitrary order. If we let \(C(1)\) and \(C(2)\) denote the completion time of the last job of \(J^{\prime}\) on \(M_{1}\) and \(M_{2}\) respectively, one has \(C(1)<C(2)\). From the definition of \(J^{\prime}\), one gets that up to \(C(2)\), no idle time occurs on \(M_{2}\). From then on, all jobs of \(J^{\prime\prime}\) are scheduled, and two cases may occur. \((i)\) No idle time ever occurs on \(M_{2}\), in which case the makespan equals \(\max\{\sum_{k=1}^{n}p_{1}^{k},\sum_{k=1}^{n}p_{2}^{k}\}\). \((ii)\) Some idle time occurs on \(M_{2}\). Consider the first time that \(M_{2}\) is idle and \(M_{1}\) is still processing a job \(J_{k}\). Upon completion of \(J_{k}\), the two machines will simultaneously start the next job, say, \(J_{k}\), but since \(J_{k}\in J^{\prime\prime}\), \(M_{1}\) will still be processing it while \(M_{2}\) returns idle. Since all remaining jobs belong to \(J^{\prime\prime}\), this will happen for each job until the end of the schedule. In particular, when the last job is scheduled, again, \(M_{2}\) completes first, so in conclusion, the makespan of \(\sigma^{*}\) is \(\sum_{k=1}^{n}p_{1}^{k}\). The above proof contains the solution algorithm. For each job \(J^{k}\), put it into \(J^{\prime}\) if \(p_{1}^{k}\leq p_{2}^{k}\) and in \(J^{\prime\prime}\) otherwise. Then, schedule all jobs of \(J^{\prime}\) followed by all jobs of \(J^{\prime\prime}\) (in any order). Since establishing whether a job belongs to \(J^{\prime}\) or \(J^{\prime\prime}\) can be done in constant time, and since jobs can be sequenced in arbitrary order within each set, we can conclude with the following result. **Theorem 3**. : \(F2|s-prec|C_{\max}\) _can be solved in \(O(n)\)._  
While \(F2|s-prec|C_{\max}\) appears even simpler than the classical \(F2||C_{\max}\), one may wonder whether other simplifications occur for \(m>2\). While the complexity status of \(Fm|s-prec|C_{\max}\) is open, we point out a difference between \(Fm||C_{\max}\) and \(Fm|s-prec|C_{\max}\), which may suggest that the problem with s-precedence constraints is not necessarily easier than the classical counterpart. Figure 5: Graph \(G(1,1)\) in the example. It is well known [10] that in \(Fm||C_{\max}\) there always exists an optimal schedule in which the job sequences on \(M_{1}\) and \(M_{2}\) are identical, and the same holds for machines \(M_{m-1}\) and \(M_{m}\). (As a consequence, for \(m\leq 3\) the optimal schedule is a permutation schedule.) This is no more true in \(Fm|s-prec|C_{\max}\), even with only two jobs. **Example 2**. : _Consider an instance with three machines and two jobs, \(A\) and \(B\):_  
\[ \begin{array}{c||c|c|c}j&1&2&3\\ \hline\text{ine }A&4\text{,}M_{1}&6\text{,}M_{2}&1\text{,}M_{3}\\ B&10\text{,}M_{1}&4\text{,}M_{2}&9\text{,}M_{3}\\ \text{ine}&\end{array}