# Some Results on Shop Scheduling with S-Precedence Constraints among Job Tasks
## 2 The Job Shop with Two Jobs and Two Machines
### Minimizing the Makespan  
Now we can address the main question. How to schedule the tasks on the two machines so that the overall makespan is minimized. The key idea here is that any active schedule can be seen as the juxtaposition of no-idle subschedules. In fact, suppose that after processing a certain task \(A_{i}\), one machine stays idle until the other machine completes task \(B_{h}\). It is important to observe that this may happen for one of _two_ reasons:  
* When a machine completes, it is blocked because both available tasks require the other machine;
* When a machine completes, there _is_ one task the machine can process, but it might be profitable to wait for the other machine to free up another task. Note that in both of these two cases \((i,h)\) is a target node of \(G\). On the contrary, if a machine completes a task while the other machine is still busy, and both available tasks require that machine (i.e., \((i,h)\) is not a target node of \(G\)), with no loss of generality we can assume that the machine _will_ immediately start one of them, since otherwise the schedule might turn out non-active (there is no point in waiting for the other machine to complete its task). If \(t\) denotes the makespan of an INIS, the schedule after \(t\) is completely independent from the schedule before \(t\). In other words, the optimal solution from \(t\) onward is the optimal solution of a problem in which \(t\) is indeed time \(0\), and the two jobs are \(A\setminus A[i]\) and \(B\setminus B[h]\). Hence, to address the overall problem, the idea is to build another, higher-level graph in which the arcs specify portions of the overall schedule. Suppose that \((i,h)\) is a target node of graph \(G\), and consider the task sets \(A\setminus A[i]\) and \(B\setminus B[h]\). We can build a new _no-idle graph_ on these sets, and call it \(G(i,h)\). (Correspondingly, the graph previously denoted as \(G\) can be renamed \(G(0,0)\).) Suppose that \((r,q)\) is a target node in graph \(G(i,h)\). This means that the tasks of the set \(\{A_{i+1},A_{i+2},\ldots,A_{r}\}\cup\{B_{h+1},B_{h+2},\ldots,B_{q}\}\) form a NIS, that we denote by \([(i+1,h+1)\rightarrow(r,q)]\). It is convenient to extend the previous notation, letting \(A[i+1,r,M_{j}]\) denote the set of tasks of \(A[i+1,r]\) that require machine \(M_{j}\), and analogously we let \(B[h+1,q,M_{j}]\) be the set of tasks of \(B[h+1,q]\) that require \(M_{j}\). Their total processing times are denoted as \(P(A[i+1,r,M_{j}])\) and \(P(B[h+1,q,M_{j}])\). (The set previously denoted as \(A[i,M_{j}]\) should now be written \(A[0,i,M_{j}]\).) We next introduce the (weighted) graph \(\mathcal{G}\) as follows. As in \(G\), nodes denote task pairs \((i,h)\). There is an arc \([(i,h),(r,q)]\) if \((r,q)\) is a target node in the graph \(G(i,h)\); i.e., if the NIS \([(i+1,h+1)\rightarrow(r,q)]\) exists. Such an arc \([(i,h),(r,q)]\) is weighted by the length of the corresponding NIS; i.e.,  
\[\max\{P(A[i+1,r,M_{1}])+P(B[h+1,q,M_{1}]),P(A[i+1,r,M_{2}])+P(B[h+1,q,M_{2}])\}.\]  
Moreover, \(\mathcal{G}\) contains a (dummy) initial node \((0,0)\) while the final node is \((n_{A},n_{B})\). At this point the reader should have no difficulty in figuring out that the following theorem holds. Theorem 1: _Given an instance of \(J2|n=2,s-\mathit{prec}|C_{\max}\), the optimal schedule corresponds to the shortest path from \((0,0)\) to \((n_{A},n_{B})\) on \(\mathcal{G}\), and its weight gives the minimum makespan._  
Now, let us discuss complexity issues. The graph \(\mathcal{G}\) can indeed be generated starting from \((0,0)\), and moving schedules forward. From each node \((i,h)\) of \(\mathcal{G}\), we can generate the corresponding no-idlegraph \(G(i,h)\), and add to \(\mathcal{G}\) all target nodes of \(G(i,h)\). We then connect node \((i,h)\) in \(\mathcal{G}\) to each of these nodes, weighing the arc with the corresponding length of the NIS. If a target node was already present in \(\mathcal{G}\), we only add the corresponding new arc. Complexity analysis is, therefore, quite simple.