# Some Results on Shop Scheduling with S-Precedence Constraints among Job Tasks
## 3 Flow Shop
### Flow Shop with Two Jobs and \(m\) Machines (\(Fm|n=2,s-prec|C_{\max}\))  
In what follows we give an Algorithm 1 that solves \(Fm|n=2,s-prec|C_{max}\). Again we denote the two jobs with A and B, and by \(p_{j}^{A}\) and \(p_{j}^{B}\) the processing time of jobs A and B on machine \(M_{j}\), \(j=1,\ldots,m\), respectively. Notice that a schedule is fully specified by the order of the two jobs on each machine, either AB or BA. In what follows, for a given schedule and a given machine, we call _leader_ the job scheduled first and _follower_ the other job. So if, on a given machine, the jobs are sequenced in the order AB, then, on that machine, [PERSON] is the leader and [PERSON] is the follower. Figure 6: Three schedules for Example 2. Given any feasible schedule, we can associate with it a decomposition of the \(m\) machines into _blocks_, each consisting of a maximal set of consecutive machines in which the two jobs are scheduled in the same order. We denote the block consisting of machines \(M_{u},M_{u+1},\ldots,M_{v}\) as \(<\)\(M_{u},M_{v}\)\(>\) (see Figure 7). In a block, due to the s-precedence constraints, all the tasks of the leader job start at the same time. Given a block \(<\)\(M_{u},M_{v}\)\(>\), we can compute a number of quantities. (Assume for the moment that \(v<m\).) If, in \(<\)\(M_{u},M_{v}\)\(>\), A is the leader, then we call _leader span_ the length of the longest \(A\)-task in the block, and denote it with \(L_{A}(u,v)\):  
\[L_{A}(u,v)=\max_{u\leq j\leq v}\{p_{j}^{A}\}, \tag{1}\]  
and similarly, if [PERSON] is the leader, the leader span is given by:  
\[L_{B}(u,v)=\max_{u\leq j\leq v}\{p_{j}^{B}\}. \tag{2}\]  
Figure 7: A sample schedule for \(Fm|n=2,s-prec|C_{\text{max}}\). The tasks of job A are in grey. Notice that, due to the definition of block, in the block that follows \(<\)\(M_{u},M_{v}\)\(>\), the roles of leader and follower are exchanged. Hence, the time at which the leader completes its longest task in \(<\)\(M_{u}\), \(M_{v}\)\(>\) is also the start time of the other job's tasks in the next block. Given a block \(<\)\(M_{u},M_{v}\)\(>\), suppose again that [PERSON] is the leader. We let \(S_{A}(u,v)\) indicate the _span_ of block \(<\)\(M_{u},M_{v}\)\(>\); i.e., the difference between the maximum completion time of a B-task and the start time of all A-tasks in \(<\)\(M_{u},M_{v}\)\(>\). This is given by:  
\[S_{A}(u,v)=\max_{u\leq j\leq v}\{\max_{u\leq h\leq j}\{p_{h}^{A}\}+p_{j}^{B}\}, \tag{3}\]  
and exchanging the roles of leader and follower in \(<\)\(M_{u},M_{v}\)\(>\), we get  
\[S_{B}(u,v)=\max_{u\leq j\leq v}\{\max_{u\leq h\leq j}\{p_{h}^{B}\}+p_{j}^{A}\}. \tag{4}\]  
Notice that trivial lower and upper bounds for the minimum makespan are given by  
\[LB=\max\{\max_{1\leq j\leq m}\{p_{j}^{A}\},\max_{1\leq j\leq m}\{p_{j}^{B}\}\}\]  
and  
\[UB=\max_{1\leq j\leq m}\{p_{j}^{A}\}+\max_{1\leq j\leq m}\{p_{j}^{B}\}\]  
respectively. In what follows we address the problem of determining a schedule having a makespan not larger than \(K\), or prove that it does not exist. Assuming that all processing time values are integers, a binary search over the interval \([LB,UB]\) allows one to establish the value of the minimum makespan. As we already observed, a relevant difference between \(Fm||C_{max}\) and \(Fm|s-prec|C_{max}\) is that, in a feasible schedule for \(Fm|s-prec|C_{max}\), the value of \(C_{max}\) may not be attained on the last machine, but rather on any machine. This fact requires carefully handling by the algorithm. Let \(F_{A}(v)\) be the minimum sum of leader spans of all blocks from \(M_{1}\) to \(M_{v}\), when A is the leader of the last block (i.e., the block including \(M_{v}\)). Similarly, \(F_{B}(v)\) is the same when B is the leader of the last block. In order to write a functional equation for \(F_{A}(v)\) and \(F_{B}(v)\), we introduce the notation \(\delta(x)=0\) if \(x\leq 0\) and \(\delta(x)=+\infty\) if \(x>0\).