## 3 Colouring Vertices of Mixed Graphs and Unit-Time Scheduling Problems
### Minimising Makespan for Unit-Time Tasks as Optimal Mixed Graph Colouring
Step 1: Partition graph \((V,\varnothing,E)\) into maximal number of the connected components: \((V,\varnothing,E)=(V_{1},\varnothing,E_{1})\cup\ldots\cup V_{m},\varnothing,E _{m})\cup(V_{m+1},\varnothing,\varnothing)\ldots\cup(V_{m+r},\varnothing,E_{k})\), where subgraphs \((V_{k},\varnothing,E_{k})\) are connected components of the graph \((V,\varnothing,E)\) for \(k\in\{1,2,\ldots,m\}\), \(|V_{k}|\geq 2\), and each subgraph \((V_{j},\varnothing,\varnothing)\) determines an isolated vertex for index \(j\in\{m+1,m+2,\ldots,m+r\}\). Denote isolated vertices as follows: \(\left\{v_{j_{k}}\right\}=V_{j}\). Set \(M=\varnothing\), \(k=1\), \(i=0\), and \(l_{0}=0\). Step 2: IF \(k=m+1\)GOTO step 5 ELSE find all maximum complete vertex-induced subgraphs \((V_{1}^{1},\varnothing,E_{1}^{1}),\ldots,(V_{k}^{l_{1}},\varnothing,E_{k}^{l_{1}})\) of the graph \((V_{k},\varnothing,E_{k})\). Set \(r=1\), \(i:=i+l_{k-1}+1\). Step 3: FOR every index \(i\), add the new processor \(M_{i}\) to the already constructed set: \(M:=M\cup\{M_{i}\}\). State that all tasks of the clique \(V_{k}^{r}\) of the graph \((V_{k},\varnothing,E_{k})\) will be processed on the processor \(M_{i}\); \(V_{k}^{r}=V_{i}=\left\{v_{i_{1}},v_{i_{2}},\ldots,v_{i_{|V_{k}|}}\right\}\), where all tasks \(\left\{v_{i_{1}},v_{i_{2}},\ldots,v_{i_{|V_{i}|}}\right\}\) will be processed on the processor \(M_{i}\). Set \(i:=i+1\). Step 4: IF \(i=\sum_{k=0}^{k}l_{k}\)THEN\(k:=k+1\)GOTO step 2 ELSE\(r:=r+1\)GOTO step 3. Step 5: FOR every index \(j\in\{m+1,\ldots,m+r\}\), add the new processor \(M_{i+j-m}\) to the already constructed set \(M\); \(M:=M\cup\left\{M_{i+j-m}\right\}\). State that task \(v_{j_{k}}\), \(V_{j}=\left\{v_{j_{k}}\right\}\), which is isolated in the graph \((V,\varnothing,E)\), will be processed on processor \(M_{i+j-m}\). Processor \(M_{i+j}\) will process only task \(v_{j_{k}}\). Set \(M:=M\cup\{M_{i+1},\ldots,M_{i+r}\}\). Step 6: FOR every arc \((v_{p},v_{q})\in A\), for which the implication (2) does not hold, determine the weak precedence constraint \(v_{p}\to v_{q}\). Step 7: FOR every arc \((v_{p},v_{q})\in A\), for which the implication (2) holds, determine the precedence constraint \(v_{p}\Rightarrow v_{q}\). Step 8: 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)\) is constructed, where the precedence constraints on the set \(V\) are defined at steps 6 and 7. The set \(M\) of the processors is defined at steps 3 and 5. STOP. ```  
**Algorithm 1** Determining the unit-time problem \(G_{\text{c}}MPT\big{|}[r_{i}],t_{ij}=1\big{|}C_{\max}\), which is equivalent to the problem of finding an optimal colouring \(c(G)\). The above Algorithm 1 shows us how to construct 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)\), which is equivalent to the problem of finding an optimal coloring \(c(G)\) of the mixed graph \(G=(V,A,E)\), all jobs in the set \(J\) being simple. To illustrate Theorem 6, we solve Example 2 of 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)\) depicted in Figure 2.  
**Example 2**. : _This example is similar to Example A2 with the input data shown in Figure A2; see Appendix B. The only difference is that the input data for Example 2 include the following release dates for the jobs \(\{I_{1},I_{2},\ldots,I_{5}\}=\)\(I\): \(r_{1}=4\), \(r_{2}=2\), \(r_{3}=0\), \(r_{4}=1\), \(r_{5}=3\). We determine the input data for Example 2 based on a mixed graph \(G^{**}=(V^{**},A^{**},E^{**})\) that includes the subgraph \(G=(V,A,E)\) presented in Figure 2. The release date \(r_{1}=4\) of the job \(J_{1}\in J\) is represented by the union of path \((v_{13},v_{14},v_{15},v_{16},v_{1})\) in the directed graph \((V^{**},A^{**},\varnothing)\) and chain \((v_{13},v_{14},v_{15},v_{16},v_{1})\) in the graph \((V^{**},\varnothing,E^{**})\).