## 3 Colouring Vertices of Mixed Graphs and Unit-Time Scheduling Problems  
In contrast to shop scheduling problems \(J\big{|}t_{ij}=1\big{|}C_{\max}\), \(G_{c}\big{|}t_{ij}=1\big{|}C_{\max}\) and other scheduling problems [5], where one machine performs each operation (task), in the multi-stage system, with multi-processor tasks [5; 10; 11], the task may require one processor or several dedicated processors during the entire time of processing this task. The tasks that require a common processor cannot be processed simultaneously.  
Chapter 10 of the monograph [5] is devoted to unit-time scheduling problems \(GMPT\big{|}t_{ij}=1\big{|}C_{\max}\) with multi-processor tasks. In [9], the more general unit-time scheduling problem \(G_{c}MPT\big{|}t_{ij}=1\big{|}C_{\max}\) was introduced including the unit-time scheduling problem \(GMPT\big{|}t_{ij}=1\big{|}C_{\max}\). In the unit-time scheduling problem \(G_{c}MPT\big{|}t_{ij}=1\big{|}C_{\max}\), two types of the precedence relations \(v_{k_{p}}\to v_{l_{q}}\) and \(v_{k_{q}}\Rightarrow v_{l_{g}}\) can be given in the input data. It may also be required that a set \(V(k)=\Big{\{}v_{k_{1}},v_{k_{2}},\ldots,v_{k_{|V(k)|}}\Big{\}}\subseteq V\) of multi-processor tasks has to be performed simultaneously in each schedule. To present this condition, the circuit \((v_{k_{1}},v_{k_{2}},\ldots,v_{k_{|V(k)|}},v_{k_{1}})\) must be included in the digraph \((V,A,\varnothing)\) such that the following is true:  
\[A^{\prime}_{c}=\Big{\{}(v_{k_{1}},v_{k_{2}}),(v_{k_{2}},v_{k_{3}}),\ldots,(v_{ k_{|V(k)|}-1},v_{k_{|V(k)|}}),(v_{k_{|V(k)|}},v_{k_{1}})\Big{\}}\subseteq A.\]  
We assume that the input data of the considered unit-time scheduling problem \(G_{c}MPT\big{|}t_{ij}=1|C_{\max}\) includes \(w\) subsets \(V(1),V(2),\ldots,V(w)\) of the given set \(V=\{v_{1},v_{2},\ldots,v_{n}\}\) such that all tasks of the subset \(V(k)\) must be performed simultaneously; \(k\in\{1,2,\ldots,w\}\). Since all unit-time tasks of the set \(V(k)=\left\{v_{k_{1}},v_{k_{2}},\ldots,v_{k_{|V(k)|}}\right\}\) must be fulfilled simultaneously, we obtain the following set of arcs:  
\[A_{c}=\mathop{\cup}\limits_{k=1}^{w}\left\{(v_{k_{1}},v_{k_{2}}),(v_{k_{2}},v_{ k_{3}}),\ldots,(v_{k_{|V(k)|}-1},v_{k_{|V(k)|}}),(v_{k_{|V(k)|}},v_{k_{1}}) \right\}\subseteq A \tag{4}\]  
The example of the unit-time problem \(G_{c}MPT|t_{ij}=1|C_{\max}\) defines the mixed graph \(G=(V,A,E)\) with arc set \(A\supseteq A_{c}\). Theorems 4 and 5 are proven in [9].  
Theorem 4.1 ([9]): _The unit-time problem \(G_{c}MPT|t_{ij}=1|C_{\max}\) on the mixed graph \(G=(V,A,E)\) is solvable if and only if the directed subgraph \((V,A,\varnothing)\) has no circuit containing adjacent vertices in the subgraph \((V,\varnothing,E)\)._  
Theorem 4.2 ([9]): _Every solvable unit-time problem \(G_{c}MPT|t_{ij}=1|C_{\max}\) on the mixed graph \(G=(V,A,E)\) is equivalent to the problem of finding an optimal colouring \(c(G)\) of the mixed graph \(G\). For every colourable mixed graph \(G=(V,A,E)\) there exists a unit-time problem \(G_{c}MPT|t_{ij}=1|C_{\max}\) determined by the same mixed graph \(G\), which is equivalent to finding an optimal colouring \(c(G)\) of the mixed graph \(G\)._  
Theorems 4.3 and 5 are illustrated by solving Example A2 of the problem \(G_{c}MPT|t_{ij}=1|C_{\max}\) on the mixed graph \(G\) depicted in Figure A2; see Appendix B.  
4 Minimising Maximal Lateness and Equivalent Minimising Makespan for Jobs with Integer Release Dates  
The unit-time problem \(G_{c}MPT|[r_{i}],t_{ij}=1|C_{\max}\) with integer release dates \(r_{i}\geq 0\) of the jobs \(J_{i}\in J\) has been studied in [12]. Since release dates \(r_{i}\) are non-negative integers and operations have unit durations, the input data of the problem \(G_{c}MPT|[r_{i}],t_{ij}=1|C_{\max}\) can be determined by the mixed graph \(G\); see Sections 2 and 3.