## 5 An Optimal Schedule of Interruptible Operations with Integer Processing Times
### Relationships between Scheduling Problems and Optimal Mixed Graph Colourings  
We next prove Theorem 8, which generalizes Theorem 5 to the problem \(G_{c}MPT[\left|r_{i}\right|],\left|t_{ij}\right|,pmtn\left|C_{\max}\) of constructing an optimal schedule for fulfilling jobs \(J_{i}\in J\) with integer release dates \(r_{i}\geq 0\) and positive durations \(t_{ij}>0\) of the operations \(Q_{ij}\in Q^{(i)}\subseteq Q\) with allowed interruptions. Theorem 8: _Every solvable scheduling problem \(G_{c}MPT[\left|r_{i}\right|],\left[t_{ij}\right],pmtn\left|C_{\max}\) pseudo-polynomially reduces to a problem of constructing an optimal colouring of vertices of the mixed graph \(G=(V,A,E)\). For every colourable mixed graph \(G\), there exists a scheduling problem \(G_{c}MPT[\left|r_{i}\right|],\left[t_{ij}\right],pmtn\left|C_{\max}\) on the mixed graph \(G\), which is equivalent to the problem of finding the optimal colouring \(c(G)\) of vertices of the same mixed graph \(G\)._  
Proof: We consider arbitrary solvable scheduling problem \(G_{c}MPT[\left|r_{i}\right|],\left[t_{ij}\right],pmtn\left|C_{\max}\) of constructing a makespan-optimal schedule for fulfilling jobs \(J=\left\{I_{1},J_{2},\ldots,J_{|J|}\right\}\) by the available dedicated processors \(M=\left\{J_{1},J_{2},\ldots,J_{|M}\right\}\). We show how to construct the mixed graph \(G=(V,A,E)\) such that optimal colouring \(c(G)\) defines a solution to the problem \(G_{c}MPT[\left|r_{i}\right|],\left[t_{ij}\right],pmtn\left|C_{\max}\). Due to Lemma 2, there exists an optimal semiactive schedule such that interruptions in the operations (if any) occur only at the integer time moments. Thus, to construct the mixed graph \(G=(V,A,E)\), we will determine a set of unit-time operations  
\[W=\left\{v_{1},v_{2},\ldots,v_{|W|}\right\}=\cup_{i=1}^{|J|}W_{i}\]  
generated by the above partitioning of the integer-time operations belonging to jobs \(J_{i}\in J=\left\{I_{1},J_{2},\ldots,J_{|J|}\right\}\) into the unit-time tasks sequentially, as shown in Section 5.1. The Formula (5) determines the set \(W_{1}\) of the unit-time tasks generated by integer-time tasks \(Q^{(1)}\) belonging to a job \(J_{1}\). The Formula (6) determines the set \(W_{2}\) of the unit-time tasks generated by the integer-time tasks \(Q^{(2)}\) belonging to the job \(J_{2}\). Similar formulas for sets \(Q^{(3)},Q^{(4)},\ldots,Q^{(|J|-1)}\) of the integer-time tasks sequentially determine sets \(W_{3},W_{4},\ldots,W_{|J|-1}\), respectively, of the generated unit-time tasks. Finally, the Formula (7) determines the set \(W_{|J|}\) of the unit-time tasks generated by the integer-time tasks \(Q^{(|J|)}\) belonging to the last job \(J_{|J|}\in J\). The above partitioning(see Section 5.1) of the integer-time tasks \(Q=\bigcup_{i=1}^{|J|}Q^{(i)}\) into the unit-time tasks determines a subgraph \((W,\varnothing,\varnothing)\) with an empty set of arcs and an empty set of edges in the indicated mixed graph \(G=(V,A,E)\), where \(W\subset V\). Based on Remark 2, every job \(J_{i}\in J\) consisting of the ordered set of the integer-time tasks \(Q^{(i)}\) is partitioned into the linearly ordered set of the unit-time tasks of the following form: \(W_{i}=\left\{v_{|W_{i-1}|+1},v_{|W_{i-1}|+2},\ldots,v_{|W_{i}|}\right\}\). In any semiactive schedule, the unit-time tasks \(W_{i}\) have to be executed in ascending order of indexes of the unit-time tasks \(v_{k}\in W_{i}\); see Remark 2. By Definition 1, the desired mixed graph \(G=(V,A,E)\) must contain the set of arcs \(A_{i}=\left\{(v_{|W_{i-1}|+1},v_{|W_{i-1}|+2}),\right.\)\((v_{|W_{i-1}|+2},v_{|W_{i-1}|+3}),\ldots,(v_{|W_{i}|-1},v_{|W_{i}|})\}\) and the following set of edges: \(E_{i}=\left\{[v_{|W_{i-1}|+1},v_{|W_{i-1}|+2}],[v_{|W_{i-1}|+2},v_{|W_{i-1}|+3} ],\ldots,[v_{|W_{i}|-1},v_{|W_{i}|}]\right\}\).