# Scheduling Multiprocessor Tasks with Equal Processing Times as a Mixed Graph Coloring Problem
## 1 Introduction
### Scheduling Multiprocessor Tasks with Unit Durations
Then, the desired general shop scheduling problem \(GcMPT|t_{i}=1,[r_{i}]|C_{\max}\) on the mixed graph \(G=(V,A,E)\) may be determined using the following Algorithm 1. ```
Input: A mixed graph \(G=(V,A,E)\) without circuits in the digraph \((V,A,\varnothing)\). Output: A general shop scheduling problem \(GcMPT|t_{i}=1,[r_{i}]|C_{\max}\) on the mixed graph \(G=(V,A,E)\), which is equivalent to finding an optimal coloring \(c(G)\) of the mixed graph \(G=(V,A,E)\). Step: Partition the graph \((V,\varnothing,E)\) into maximum 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,\varnothing)\), where the subgraph \((V_{k},\varnothing,E_{k})\) is a maximum (with respect to the inclusion) connected component of the graph \((V,\varnothing,E)\) for each index \(k\in\{1,\ldots,m\}\) such that \(|V_{k}|\geq 2\). Let the subgraph \((V_{j},\varnothing,\varnothing)\) determine an isolated vertex for each index \(j\in\{m+1,\ldots,m+r\}\). Denote this isolated vertex as: \(\left\{v_{j_{k}}\right\}=V_{j}\). Set \(M=\varnothing,k=1,i=0\), and \(l_{0}=0\). ```  
**Algorithm 1** Constructing the general shop scheduling problem \(GcMPT|t_{i}=1,[r_{i}]|C_{\max}\), which is equivalent to the optimal coloring \(c(G)\) \begin{table}
\begin{tabular}{c c} \hline
**Terms of Mixed Graph Coloring \(c(G)\)** & **Corresponding Terms of General Shop Scheduling Problem** \\ \multicolumn{2}{c}{**G\(cMPT|t_{i}=1\)\([r_{i}]|C_{\max}\)**} \\ \hline Vertex \(v_{i}\in V\backslash V^{0}\) & Unit-time task \(v_{i}\in V\backslash V^{0}\) (operation) \\ \hline Vertices on the path (chain) \((v_{k_{1}},v_{k_{2}},\ldots,v_{k_{|V^{(k)}_{i}|}})\) in the digraph \((V,A,\varnothing)\) (in the graph \((V,\varnothing,E)\)) & A set \(V^{(k)}=\left\{v_{k_{1}},v_{k_{2}},\ldots,v_{k_{|V^{(k)}_{i}|}}\right\}\) of the linearly ordered tasks \((v_{k_{1}},v_{k_{2}},\ldots,v_{k_{|V^{(k)}_{i}|}})\) of the job \(J_{k}\in J\) \\ \hline A path (chain) \((v_{k_{1}},\ldots,v_{k_{|V|}},v_{k_{1}})\) of the length \(r_{i}\) in the digraph \((V,\varnothing,E)\)) & A release time \(r_{i}\geq 0\) of the job \(J_{i}\in J\) \\ \hline A clique \(\left\{v_{i_{1}},v_{i_{2}},\ldots,v_{i_{|V|}}\right\}\) in the graph \((V,\varnothing,E)\) & Tasks \(V_{i}=\left\{v_{i_{1}},v_{i_{2}},\ldots,v_{i_{|V|}}\right\}\) processed by machine \(M_{i}\in M\) \\ \hline Arc \((v_{i}\),\(v_{j})\) in the digraph \((V,A,\varnothing)\) & A precedence constraint \(v_{i}\mapsto v_{j}\) determined between operations belonging to different jobs \\ \hline Arc \((v_{p},v_{q})\) in the digraph \((V,A,\varnothing)\) and edge \([v_{p},v_{q}]\) in the graph \((V,\varnothing,E)\) & A precedence constraint \(v_{p}\mapsto v_{q}\) determined between tasks (operations) belonging to different jobs \\ \hline A circuit \((v_{k_{1}},v_{k_{2}},\ldots,v_{k_{|V(k)|}},v_{k_{1}})\) in the digraph \((V,A,\varnothing)\), where \(A_{c}\subseteq A\) & Tasks \(V(k)=\left\{v_{k_{1}},v_{k_{2}},\ldots,v_{k_{|V(k)|}}\right\}\subseteq V\), which must be processed simultaneously \\ \hline A coloring \(c(G)\) of the mixed graph \(G=(V,A,E)\) & A schedule for the problem \(GcMPT|t_{i}=1,[r_{i}]|C_{\max}\) \\ \hline An optimal coloring \(c(G)\) of the mixed graph \(G=(V,A,E)\) & An optimal schedule for the problem \(GcMPT|t_{i}=1,[r_{i}]|C_{\max}\) \\ \hline An optimal coloring \(c(G)\) of the mixed graph \(G=(V,A,E)\) & An optimal schedule for the problem \(GcMPT|t_{i}=1,[r_{i}]|C_{\max}\) \\ \hline The chromatic number \(\chi(G)\) & The minimal value of makespan \(C_{\max}\) \\ \hline \end{tabular}
\end{table} 
Table 1: The correspondence of terms used in mixed graph coloring \(c(G)\) and those used in the general shop scheduling problem \(GcMPT|t_{i}=1,[r_{i}]|C_{\max}\) on the mixed graph \(G=(V,A,E)\).