## 5 An Optimal Schedule of Interruptible Operations with Integer Processing Times
### Relationships between Scheduling Problems and Optimal Mixed Graph Colourings
Therefore, the set of weak precedence constraints \(R_{\rightarrow}\) determined in (11) must contain the following subset:  
\[\cup_{g=1}^{l}\big{\{}v_{g_{1}}\to v_{g_{2}},v_{g_{2}} \to v_{g_{3}},\ldots,v_{g_{|g|}-1}\to v_{g_{|g|}},v_{g_{|g|}} \to v_{g_{1}}\big{\}}\]  
It is clear that the above constructed set \(A_{|J|+2}\) of the arcs must contain the following set of the arcs: \(A_{|J|+3}=\cup_{g=1}^{l}\big{\{}(v_{g_{1}},v_{g_{2}}),(v_{g_{2}},v_{g_{3}}), \ldots,(v_{g_{|g|}-1},v_{g_{|g|}}),(v_{g_{|g|}},v_{g_{1}})\big{\}}\); see Definition 1. We have constructed the arc set \(A^{o}=\big{\{}\cup_{i=1}^{|J|}A_{i}\big{\}}\cup A_{|J|+1}\cup A_{|J|+2}\cup A _{|J|+3}\big{\}}\), the edge set \(E^{o}=\big{\{}\cup_{i=1}^{|J|}E_{i}\big{\}}\cup E_{|J|+1}\) and the vertex set \(W=\big{\{}v_{1},v_{2},\ldots,v_{|W|}\big{\}}=\cup_{i=1}^{|J|}W_{i}\), where each vertex determines the unit-time operation (task) generated by the operation from the set \(Q\) with integer durations. Thus, we have constructed the mixed graph \((W,A^{o},E^{o})\), which is a subgraph of the desired mixed graph \(G\). The input data for the considered solvable problem \(G_{c}MPT\big{|}[r_{i}],[t_{ij}],pmtn\big{|}C_{\max}\) include also the non-negative integer release dates \(r_{1},r_{2},\ldots,r_{|J|}\) of the jobs \(J_{1},J_{2},\ldots J_{|J|}\), respectively. Therefore, for every job \(J_{i}\in J\), the set \(W(r_{i})=\big{\{}v_{g_{i}},v_{g_{i}},\ldots,v_{g_{i-1}}^{o}\big{\}}\) of the vertices and the path \((v_{\frac{\theta_{i}}{l}},v_{\frac{\theta_{i}}{l}},\ldots,v_{\frac{\theta_{i}}{l _{i-1}}})\), whose length is equal to \(r_{i}\geq 0\), are determined. We add all these vertices and arcs of the following paths: \((v_{\frac{\theta_{i}}{l}},v_{\frac{\theta_{i}}{l}},\ldots,v_{\frac{\theta_{i}}{l _{i-1}}})\) to subgraph \((W,A^{o},\varnothing)\) of mixed graph \((W,A^{o},E^{o})\). We also add the edges of the following chains \((v_{\frac{\theta_{i}}{l}},v_{\frac{\theta_{i}}{l}},\ldots,v_{\frac{\theta_{i}}{l _{i-1}}})\) to subgraph \((W,\varnothing,E^{o})\) of mixed graph \((W,A^{o},E^{o})\). Let \(G=\{V,A,E\}\) be a mixed graph generated by the mixed graph \((W,A^{o},E^{o})\) after adding all the vertices \(\bigcup_{i=1}^{|J|}W(r_{i})\), all the arcs of paths \((v_{\frac{\theta_{i}}{l}},v_{\frac{\theta_{i}}{l}},\ldots,v_{\frac{\theta_{i-1}}{l _{i-1}}})\) and all the edges of chains \((v_{\frac{\theta_{i}}{l}},v_{\frac{\theta_{i}}{2}},\ldots,v_{\frac{\theta_{i}}{l _{i-1}}})\). Thus, we have constructed the desired mixed graph \(G=(V,A,E)\). For the constructed mixed graph, the following equality \(V=W+\bigcup_{i=1}^{|J|}W(r_{i})\) holds. Due to the above construction of the mixed graph, the precedence constraints defined on the set of tasks for the problem \(G_{c}MPT\big{|}[r_{i}],[t_{ij}],pmtn\big{|}C_{\max}\) are determined by graph \((W,A^{o},E^{o})\). The prohibition of simultaneously fulfilling every pair of unit-time tasks of the set \(V^{(k)}\) in any semiactive schedule is determined by the complete \(\left|J^{(k)}\right|\)-partite graph \((V^{(k)},\varnothing,E^{(k)})\) with the vertex set \(\left\{V_{k}^{1},V_{k}^{2},\ldots,V_{k}^{|J^{(k)}|}\right\}\). The given release dates \(r_{1},r_{2},\ldots,r_{|J|}\) of the given jobs \(J_{1},J_{2},\ldots,J_{|J|}\) are defined by a subgraph \((\bigcup\limits_{i=1}^{|J|}W(r_{i}),A\setminus A^{o},E\setminus E^{o})\) of the constructed mixed graph \(G=(V,A,E)\). As can be easily verified, the constructed mixed graph \(G=(V,A,E)\) completely defines the input data of the considered scheduling problem \(G_{c}MPT[r_{i}],[t_{ij}],\)\(pmtn\big{|}C_{\max}\). Hence, for the solvable general scheduling problem \(G_{c}MPT[|r_{i}],[t_{ij}],pmtn\big{|}C_{\max}\) determined on mixed graph \(G=(V,A,E)\), there exists a semiactive schedule  
\[S=(C(v_{1}),C(v_{2}),\ldots,C(Q_{|W|}) \tag{12}\]  
which defines the colouring \(c(G)\) of the constructed mixed graph \(G=(V,A,E)\) as follows: the equality \(c(v_{i})=C(v_{i})\) holds for every vertex \(v_{i}\in V\).