## 2 Related Works, Definitions, and Preliminaries
### Optimal Strict Colourings of Mixed Graphs and Equivalent Unit-Time Job-Shop Problems  
The paper [3] introducing Definition 1 was published in Russian. In 1997, another colouring of mixed graph \(c_{<}(G)\) was introduced in the paper [8], published in English. Definition 3 ([8]): The function \(c_{<}:V\to\{1,2,\ldots,t\}\) is a strict colouring \(c_{<}(G)\) of the mixed graph \(G=(V,A,E)\), if the inequalities \(c_{<}(v_{i})<c_{<}(v_{j})\) hold for all arcs \((v_{i},v_{j})\in A\) and the relations \(c_{<}(v_{p})\
eq c_{<}(v_{q})\) hold for all edges \([v_{p},v_{q}]\in E\). The strict colouring \(c_{<}(G)\) is optimal, if this colouring uses a minimum number of colours \(c_{<}(v_{i})\in\{1,2,\ldots,t\}\). We can use colouring \(c(G)\) instead of strict colouring \(c_{<}(G)\) of vertices of the mixed graph \(G=(V,A,E)\) provided that the following implication holds for every arc \((v_{i},v_{j})\in A:\)  
\[(v_{i},v_{j})\in A\Rightarrow\ [v_{i},v_{j}]\in E \tag{2}\]  
If the mixed graph \(G=(V,A,E)\) includes the arc \((v_{i},v_{j})\in A\) and the implication (2) does not hold, one can add an edge \([v_{i},v_{j}]\) to the mixed graph \(G\) for each such arc \((v_{i},v_{j})\in A\). A strict colouring \(c_{<}(G)\) of the mixed graph \(G\) can be represented as a colouring \(c(G)\) of the mixed graph obtained by including all such edges to the mixed graph \(G\). Thus, the following lemma is obtained. Lemma 1: _A strict colouring \(c_{<}(G)\) of the mixed graph \(G=(V,A,E)\) can be interpreted as a special case of the colouring \(c(G)\), if the inclusion \((v_{i},v_{j})\in A\) implies the inclusion \([v_{i},v_{j}]\in E\)._  
A criterion for the existence of a strict colouring of vertices of the mixed graph \(G=(V,A,E)\) is determined by Corollary 1 of Theorem 1. Corollary 1 ([1]): _A strict colouring \(c_{<}(G)\) exists if and only if the digraph \((V,A,\varnothing)\) does not contain a circuit._  
Theorem 2 was proven in [1]. Theorem 2 ([1]): _The unit-time scheduling problem \(\ \big{|}t_{ij}=1\big{|}C_{\max}\) is equivalent to the problem of finding the optimal strict colouring of vertices of the mixed graph \(G=(V,A,E)\) with \(V=Q\), provided that two conditions hold as follows: (a) \((Q,A,\varnothing)=\cup_{i=1}^{|I|}(Q_{i},A_{i},\varnothing)\), where each subgraph \((Q_{i},A_{i},\varnothing)\) is a path passing through the vertices \(Q_{i}\) and equality \(Q_{i}\cap Q_{j}=\varnothing\) holds for indexes \(i\
eq j\); (b) \((Q,\varnothing,E)=\cup_{k=1}^{|M|}(Q^{(k)},\varnothing,E^{(k)})\), where each subgraph \((Q^{(k)},\varnothing,E^{(k)})\) is a complete graph on the set \(Q_{i}\) and equality \(Q^{(k)}\cap Q^{(l)}=\varnothing\) holds for indexes \(k\
eq l\)._  
Due to Lemma 1 and Theorem 2, one can obtain the following corollary. Corollary 2 ([1]): _The unit-time scheduling problem \(\ \big{|}t_{ij}=1\big{|}C_{\max}\) is equivalent to the problem of determining the optimal colouring of the mixed graph \(G=(V,A,E)\), where the relations_  
\[\Big{\{}v_{1},v_{2},\ldots,v_{|V|}\Big{\}}=V=Q=\Big{\{}Q_{1,1},Q_{1,2},\ldots, Q_{1,|Q_{1}|},Q_{2,1},Q_{2,2},\ldots,Q_{2,|Q_{2}|},\ldots,Q_{|I|,1},Q_{|I|,2}, \ldots,Q_{|J|,|Q_{|I|}|}\Big{\}}\]  
_hold along with the above conditions (2), (a) and (b)._  
To illustrate Corollary 2, we consider Example 1 of the problem \(\ \big{|}t_{ij}=1\big{|}C_{\max}\), whose input data are determined by the corresponding mixed graph \(G\). Remark 1: _Since all operations \(\ Q_{ij}\in Q_{i}\) in the unit-time scheduling problem \(\ \big{|}t_{ij}=1\big{|}C_{\max}\) have unit processing times, we represent each operation as a vertex in the mixed graph \(G=(V,A,E)\) with indexing the vertices in the set \(V\) in the lexicographic order of the pairs \(\{i,j\}\) of the indexesof the corresponding operations \(Q_{ij}\in Q_{i}\), \(J_{i}\in J\). Thus, we obtain the following set \(V=\left\{v_{1},v_{2},\ldots,v_{|V|}\right\}\) of vertices, where the equality \(\left|V\right|=\sum\limits_{i=1}^{|J|}\left|Q^{(i)}\right|\) holds._  
**Example 1.