## 6 Example 4 of General Scheduling Problem with Interruptible Operations
_Let the following release dates of the jobs \(J=\{I_{1},J_{2},J_{3},J_{4}\}\) be given as a part of the input data of Example 4: \(r_{1}=4,r_{2}=3,r_{3}=1,\,r_{4}=3\)._  
Release date \(r_{1}=4\) of the job \(J_{1}\in J\) is determined by the union of path \((v_{20},v_{21},v_{22},v_{23},v_{1})\) in the directed graph \((V,A,\varnothing)\) and chain \((v_{20},v_{21},v_{22},v_{23},v_{1})\) in the subgraph \((V,\varnothing,E)\) of the mixed graph \(G=(V,A,E)\). Release date \(r_{2}=3\) is presented by the union of path \((v_{24},v_{25},v_{26},v_{4})\) in the directed graph \((V,A,\varnothing)\) and chain \((v_{24},v_{25},v_{26},v_{4})\) in the subgraph \((V,\varnothing,E)\) of the desired mixed graph \(G=(V,A,E)\). Release date \(r_{3}=1\) of the job \(J_{3}\in J\) is presented by the union of arc \((v_{27},v_{10})\) in the directed graph \((V,A,\varnothing)\) and edge \([v_{27},v_{10}]\) in the subgraph \((V,\varnothing,E)\) of the desired mixed graph \(G=(V,A,E)\). Release date \(r_{4}=3\) of the job \(J_{4}\in J\) is presented by the union of path \((v_{28},v_{29},v_{30},v_{16})\) in the directed graph \((V,A,\varnothing)\) and chain \((v_{28},v_{29},v_{30},v_{16})\) in the subgraph \((V,\varnothing,E)\) of the desired mixed graph \(G=(V,A,E)\). Now, the desired mixed graph \(G\) is constructed. Figure 4 presents the constructed mixed graph \(G\) determining the whole input data for Example 4 of the problem \(G_{c}MPT[\left|r_{i}\right|],\left[t_{ij}\right],\)\(pmtn\left|C_{\max}\) with four jobs \(J=\{J_{1},J_{2},J_{3},J_{4}\}\) and seven dedicated processors \(M=\{M_{1},M_{2},\ldots,M_{7}\}\). Due to Theorem 4.1, a solvable problem \(G_{c}MPT[\left|r_{i}\right|],\left[t_{ij}\right],\)\(pmtn\left|C_{\max}\) (like Example 4) reduces to determining optimal colouring \(c(G)\). An existing semiaactive schedule for the scheduling problem with possible interruptions of the operations is determined by set (12) of completion times of the unit-time operations of set \(W\). The semiaactive schedule is determined by the colouring \(c(G)\) of the mixed graph \(G\), in which the equality \(c(v_{i})=C(v_{i})\) holds for the vertices \(v_{i}\in W\). The makespan-optimal semiaactive schedule that exists for Example 4 is determined by the optimal colouring \(c(G)\), where \(c(v_{1})=5\), \(c(v_{2})=10\), \(c(v_{3})=11\), \(c(v_{4})=4\), \(c(v_{5})=5\), \(c(v_{6})=6\), \(c(v_{7})=7\), \(c(v_{8})=8\), \(c(v_{9})=9\), \(c(v_{10})=2\), \(c(v_{11})=3\), \(c(v_{12})=4\), \(c(v_{13})=5\), \(c(v_{14})=6\), \(c(v_{15})=7\), \(c(v_{16})=7\), \(c(v_{17})=8\), \(c(v_{18})=9\), \(c(v_{19})=10\). To show that the colouring \(c(G)\) is optimal, we next prove the inequality \(\chi(G)\geq 11\). In the mixed graph \(G\) depicted in Figure 4, there is a path \((v_{24},v_{25},v_{26},v_{4},v_{5},v_{6},v_{7},v_{8},v_{9},v_{3})\) in the directed subgraph \((V,A,\varnothing)\) and a chain \((v_{24},v_{25},v_{26},v_{4},v_{5},v_{6},v_{7},v_{8},v_{9},v_{3})\) in the subgraph \((V,\varnothing,E)\). Therefore, a minimal colour of the vertex \(v_{9}\) is not less than \(9\), \(c(v_{9})\geq 9\) and the minimal colour of the vertex \(v_{3}\) is not less than \(10\); \(c(v_{3})\geq 10\). In mixed graph \(G=(V,A,E)\), there is a path \((v_{20},v_{21},v_{22},v_{23},v_{1},v_{2},v_{3})\) in the directed subgraph \((V,A,\varnothing)\) and a chain \((v_{20},v_{21},v_{22},v_{23},v_{1},v_{2},v_{3})\) in the subgraph \((V,\varnothing,E)\). Therefore, a minimal colour of the vertex \(v_{2}\) is not less than \(6\); \(c(v_{2})\geq 6\). However, we see that the minimal colour of the vertex \(v_{2}\) cannot be equal to \(6\), \(7\), \(8\) and \(9\), because the following four inclusions hold: \([v_{2},v_{6}]\in E\), \([v_{2},v_{7}]\in E\), \([v_{2},v_{8}]\in E\), \([v_{2},v_{9}]\in E\). There is a path \((v_{24},v_{25},v_{26},v_{4},v_{5},v_{6},v_{7},v_{8},v_{9},v_{3})\) in the directed subgraph \((V,A,\varnothing)\) and a chain \((v_{24},v_{25},v_{26},v_{4},v_{5},v_{6},v_{7},v_{8},v_{9},v_{3})\) in the subgraph \((V,\varnothing,E)\).