## 3 Colouring Vertices of Mixed Graphs and Unit-Time Scheduling Problems
### Minimising Makespan for Unit-Time Tasks as Optimal Mixed Graph Colouring  
In the problem \(G_{c}MPT|[r_{i}],t_{ij}=1|C_{\max}\), the multi-processor task \(v_{i}\in V\) is considered as a job \(J_{i}\). A job consisting of a single operation is referred to as a simple job in Theorem 6 which follows. Note that the first part of this theorem has been proven in [12] by generating a mixed graph \(G\), which determines the problem \(G_{c}MPT|t_{ij}=1|C_{\max}\) to the mixed graph \(G=(V,A,E)\) determining the input data for the problem \(G_{c}MPT|[r_{i}],t_{ij}=1|C_{\max}\). Due to the demonstrated correspondence of the terms used in optimal coloring \(c(G)\) and those used in solving a unit-time problem \(G_{c}MPT|[r_{i}],t_{ij}=1|C_{\max}\), the following first part of Theorem 6 was proven in [12]: _Any solvable unit-time problem \(G_{c}MPT|[r_{i}],t_{ij}=1|C_{\max}\) on the mixed graph \(G=(V,A,E)\) is equivalent to the problem of finding an optimal colouring of the mixed graph \(G=(V,A,E)\)._  
Theorem 4.3: _Any solvable unit-time problem \(G_{c}MPT|[r_{i}],t_{ij}=1|C_{\max}\) on the mixed graph \(G\) is equivalent to the problem of finding an optimal colouring of the mixed graph \(G\). Conversely, for any colourable mixed graph \(G\), there exists a unit-time problem \(G_{c}MPT|[r_{i}],t_{ij}=1|C_{\max}\) on the mixed graph \(G\), which is equivalent to the problem of finding optimal colouring \(c(G)\)._  
Proof of the second part of Theorem 6.3.: We next prove the claim as follows: _for any colorable mixed graph \(G=(V,A,E)\), there exists a unit-time problem \(G_{c}MPT|[r_{i}],t_{ij}=1|C_{\max}\) on the mixed graph \(G\), which is equivalent to the problem of finding optimal colouring \(c(G)\)_. Let set \(\Omega\) denote a set of all circuits existing in the digraph \((V,A,\varnothing)\). We will treat two possible cases, I and II. Case I. Let set \(\Omega\) be empty; \(\Omega=\varnothing\). The unit-time scheduling problem \(G_{c}MPT|[r_{i}],t_{ij}=1|C_{\max}\) on the mixed graph \(G=(V,A,E)\) may be constructed based on Algorithm 1, which follows. Case II. Let set \(\Omega\) be not empty; \(\Omega\
eq\varnothing\). The mixed graph \(G=(V,A,E)\) is colourable. So, due to Theorem 1, each circuit \((v_{k_{1}},v_{k_{2}},\ldots,v_{k_{|V(k)|}},v_{k_{1}})\) in set \(\Omega\) has no vertices that are adjacent in the graph \((V,\varnothing,E)\). Therefore, all tasks of the set \(\left\{v_{k_{1}},v_{k_{2}},\ldots,v_{k_{|V(k)|}}\right\}=V(k)\) must be processed simultaneously in the unit-time problem \(G_{\text{c}}MPT\big{|}[r_{i}],t_{ij}=1\big{|}C_{\max}\) on the mixed graph \(G=(V,A,E)\) with the circuit \((v_{k_{1}},v_{k_{2}},\ldots,v_{k_{|V(k)|}},v_{k_{1}})\) existing in the directed subgraph \((V,A,\varnothing)\). Assume that \(\Omega=\mathop{\cup}\limits_{k=1}^{w}V(k)=\mathop{\cup}\limits_{k=1}^{w} \Big{\{}(v_{k_{1}},v_{k_{2}},v_{k_{3}},\ldots,v_{k_{|V(k)|}-1},v_{k_{|V(k)|}},v _{k_{1}})\Big{\}}\). We delete arcs \(A_{c}\) determined in (4) from the mixed graph \(G=(V,A,E)\) and apply Algorithm 1 to the constructed mixed graph \(G^{0}=(V,A\backslash A_{c},E)\). Thus, we construct the unit-time problem \(G_{\text{c}}MPT\big{|}[r_{i}],t_{ij}=1\big{|}C_{\max}\) on the mixed graph \(G^{0}=(V,A\backslash A_{c},E)\), which is equivalent to the problem of finding the optimal coloring \(c(G^{0})\). This unit-time problem \(G_{\text{c}}MPT\big{|}[r_{i}],t_{ij}=1\big{|}C_{\max}\) on the mixed graph \(G=(V,A,E)\) is equivalent to the problem of finding the optimal colouring \(c(G)\) of the mixed graph \(G\). ```
Input: A mixed graph \(G=(V,A,E)\) with a circuit-free digraph \((V,A,\varnothing)\). Output: The unit-time problem \(G_{\text{c}}MPT\big{|}[r_{i}],t_{ij}=1\big{|}C_{\max}\) on the mixed graph \(G=(V,A,E)\) that is equivalent to the problem of finding the optimal colouring \(c(G)\).