# Some Results on Shop Scheduling with S-Precedence Constraints among Job Tasks
## 2 The Job Shop with Two Jobs and Two Machines
### Generating Initial No-Idle Subschedules  
We denote by \(A[i,M_{j}]\) and \(B[h,M_{j}]\), the subset of tasks of \(A[i]\) and \(B[h]\) respectively, requiring machine \(M_{j}\), \(j=1,2\); i.e.,  
\[A[i,M_{j}] =\{A_{r}:r\leq i,M(A_{r})=M_{j}\}\quad j=1,2,\] \[B[h,M_{j}] =\{B_{q}:q\leq h,M(B_{q})=M_{j}\}\quad j=1,2.\]  
We also let \(P(A[i,M_{j}])\) and \(P(B[h,M_{j}])\) indicate the total processing time of tasks in \(A[i,M_{j}]\) and \(B[h,M_{j}]\); i.e.,  
\[P(A[i,M_{j}]) =\sum_{r\in A[i,M_{j}]}p_{r}^{A},\] \[P(B[h,M_{j}]) =\sum_{q\in B[h,M_{j}]}p_{q}^{B}.\]  
If an INIS of tasks \(A[i]\cup B[h]\) exists, its makespan is given by  
\[\max\{P(A[i,M_{1}])+P(B[h,M_{1}]),P(A[i,M_{2}])+P(B[h,M_{2}])\}.\]  
**Proposition 1**. : _In any optimal schedule, there are indices \(i\) and \(h\) such that the subschedule involving tasks \(A[i]\cup B[h]\) is an INIS._  
In fact, given an optimal schedule, consider the subschedule of the tasks scheduled on the two machines from time \(0\) to the end of the first idle interval of the schedule, assuming, e.g., that such an idle interval occurs on \(M_{1}\). If the subschedule is not an INIS, we can iteratively remove the last task scheduled on \(M_{2}\) in the subschedule, until the definition of INIS is met. In view of Proposition 1, we are only interested in schedules in which the initial part is an INIS. However, not all initial no-idle subschedules are candidates to be the initial part of an optimal schedule. We first address the following question. Can we determine all operation pairs \((i,h)\) such that an INIS of \(A[i]\cup B[h]\) exists? We show next that this question can be answered in polynomial time. The idea is to build the no-idle partial schedules from the beginning of the schedule onward. To this aim, let us define an unweighted graph \(G\), which we call _initial no-idle graph_. Nodes of \(G\) are denoted as \((i,h)\), representing a NIS of \(A[i]\cup B[h]\) (for shortness, we use \((i,h)\) also to denote the corresponding INIS). If the schedule obtained appending \(B_{h+1}\) to schedule \((i,h)\) is still an INIS, we insert node \((i,h+1)\) and an arc from \((i,h)\) to \((i,h+1)\) in \(G\). Symmetrically, if the schedule obtained appending \(A_{i+1}\) to \((i,h)\) is an INIS, we insert \((i+1,h)\) and an arc from \((i,h)\) to \((i+1,h)\) in \(G\). As illustrated later on (cases \((i)-(iv)\) below), while building the graph \(G\), we can also determine whether or not a certain INIS can be the initial part of an optimal schedule. If it can, we call it a _target node_. Figure 1: In instance (**a**), the set \(A[2]\cup B[2]\) does not form an INIS (initial no-idle subschedule); in instance (**b**) it does. Consider any node \((i,h)\) in \(G\), and the machine completing soonest in the INIS. Ties can be broken arbitrarily, but to fix ideas, suppose that \(M_{2}\) is still busy when \(M_{1}\) completes. (Note that, since there is no idle time, \(M_{1}\) completes at time \(P(A[i,M_{1}])+P(B[h,M_{1}])\).) If \(i<n_{A}\) and \(h<n_{B}\), the two available tasks are \(A_{i+1}\) and \(B_{h+1}\), and four cases can occur. 1. \(M(A_{i+1})=M(B_{h+1})=M_{2}\). In this case, \(M_{1}\) is necessarily idle until \(M_{2}\) completes (Figure 2a). Hence, there is no way to continue an INIS, and therefore node \((i,h)\) has no outgoing arcs. In this case, \((i,h)\) is a target node. 2. \(M(A_{i+1})=M_{1}\) and \(M(B_{h+1})=M_{2}\). In this case, when \(A_{i}\) completes, the only way to continue an INIS is to start task \(A_{i+1}\) on \(M_{1}\) (Figure 2b). Thus we generate node \((i+1,h)\) and the arc from \((i,h)\) to \((i+1,h)\), which is the only outgoing arc of \((i,h)\). In this case as well, \((i,h)\) is a target node. 3. \(M(A_{i+1})=M_{2}\) and \(M(B_{h+1})=M_{1}\). A symmetrical discussion to the previous case holds; i.e., the only way to continue an INIS is to start task \(B_{h+1}\) on \(M_{1}\) (Figure 2c), so we generate node \((i,h+1)\) and the arc from \((i,h)\) to \((i,h+1)\), which is the only outgoing arc of \((i,h)\). In this case also, \((i,h)\) is a target node. 4.