## 5 An Optimal Schedule of Interruptible Operations with Integer Processing Times
### Relationships between Scheduling Problems and Optimal Mixed Graph Colourings
The sets of arcs \(A_{i}\) and edges \(E_{i}\) will determine the linear order for the execution of the unit-time tasks from set \(W_{i}\) when implementing any semiactive schedule for the problem \(G_{c}MPT[\left.\left[r_{i}\right],\left[r_{i}\right],\left[r_{i}\right],\left[r _{min}\right]\right.\); see Remark 2. Thus, we constructed a subgraph \((W,\cup_{i=1}^{|J|}A_{i},\cup_{i=1}^{|J|}E_{i})\) of the desired mixed graph \(G=(V,A,E)\) where inclusion \(W\subset V\) holds. For every processor \(M_{k}\in M\), set \(Q_{k}\) of all integer-time tasks fulfilled by the processor \(M_{k}\) defines set \(V_{k}\) of unit-time tasks fulfilled by the processor \(M_{k}\). The cardinality of set \(V_{k}\) is equal to the total processing time of the integer-time tasks for fulfilling all jobs in the set \(J^{(k)}=:\left\{I_{k_{1}},I_{k_{2}},\ldots,J_{|J^{(k)}|}\right\}\). So, the following equality holds:  
\[\left|V_{k}\right|=\sum_{l_{1}\in J^{(k)}}t_{k} \tag{8}\]  
Set \(V_{k}\) is partitioned into \(\left|J^{(k)}\right|\) subsets \(V_{k}^{j}\) of the tasks with unit durations for fulfilling jobs \(J_{k_{j}}\in J^{(k)}\), i.e., the equality \(V_{k}=V_{k}^{1}\cup V_{k}^{2}\cup\ldots\cup V_{k}^{|J^{(k)}|}\) holds, where \(V_{k}^{j}\
eq\varnothing\) and \(V_{k}^{j}\cap V_{k}^{h}=\varnothing\) for each indices \(j\
eq h\). As can be easily verified, the forbidance to simultaneously execute every pair of the unit-time tasks of the set \(V_{k}\) in a semiactive schedule is determined by the complete \(\left|J^{(k)}\right|\)-partite subgraph \((V_{k},\varnothing,E_{k})\) of the mixed graph \(G=(V,A,E)\) with the following set \(\left\{V_{k}^{1},V_{k}^{2},\ldots,V_{k}^{|J^{(k)}|}\right\}\) of vertices and the following edge set \(E_{k}\) with the cardinality determined as follows:  
\[\left|E_{k}\right|=\sum_{i=1}^{|J^{(k)}|-1}\sum_{j=i+1}^{|J^{(k)}|}\left\{ \left|V_{k}^{i}\right|\times\left|V_{k}^{j}\right|\right\} \tag{9}\]Together with the precedence constraints determined above between tasks belonging to the same job \(J_{i}\in J\), the input data for the problem \(G_{c}MPT\big{|}[r_{i}],[t_{ij}],pmtn\big{|}C_{\max}\) may include the precedence constraints defined on the set of tasks, which belong to different jobs of the set \(J\). Let these precedence constraints be determined as follows:  
\[R_{\Rightarrow}=\big{\{}v_{k_{1}}\Rightarrow v_{k_{2}},\;\;v_{k_{3}} \Rightarrow v_{k_{4}},\ldots,v_{k_{|i|-1}}\Rightarrow v_{k_{|i|}}\big{\}} \tag{10}\]  
Moreover, the following weak precedence constraints on the set of tasks, which belong to different jobs of the set \(J\), may also be determined:  
\[R_{\rightarrow}=\big{\{}v_{k_{1}}\to v_{k_{2}},\;v_{k_{3}} \to v_{k_{4}},\ldots,v_{h_{|i|-1}}\to v_{h_{|i|}}\big{\}} \tag{11}\]  
According to Definition 1, we introduce the precedence constraints (10) by adding the set \(A_{|J|+1}=\big{\{}(v_{k_{1}},v_{k_{2}}),(v_{k_{2}},v_{k_{3}}),\ldots,(v_{k_{|i |-1}},v_{k_{|i|}})\big{\}}\) of the arcs and the set \(E_{|J|+1}=\big{\{}[v_{k_{1}},v_{k_{2}}],[v_{k_{2}},v_{k_{3}}],\ldots,[v_{k_{|i |-1}},v_{k_{|i|}}]\big{\}}\) of the edges in the mixed graph \(G=(V,A,E)\). To determine the weak precedence constraints (11), it is sufficient to add the following set \(A_{|J|+2}=\big{\{}(v_{k_{1}},v_{k_{2}}),(v_{k_{2}},v_{k_{3}}),\ldots,(v_{h_{|i| -1}},v_{h_{|i|}})\big{\}}\) of the arcs in the desired mixed graph \(G=(V,A,E)\). Let the input data for the scheduling problem \(G_{c}MPT\big{|}[r_{i}],[t_{ij}],pmtn\big{|}C_{\max}\) include the subsets \(V(1),V(2),\ldots,V(I)\) of the unit-time operations from the set \(Q\) such that operations of the subset \(V(g)=\big{\{}v_{g_{1}},v_{g_{2}},\ldots,v_{g_{|V(g)|}}\big{\}}\subset Q\) must be executed simultaneously in any schedule, where \(g\in\{1,2,\ldots,l\}\).