# Scheduling Multiprocessor Tasks with Equal Processing Times as a Mixed Graph Coloring Problem
## 1 Introduction
### Scheduling Multiprocessor Tasks with Unit Durations
: _A feasible schedule for the general shop scheduling problem \(\,GcMPT|t_{i}=1|C_{\max}\,\) on the mixed graph \(G=(V,A,\,E)\) exits if and only if the digraph \((V,A,\varnothing)\) has no circuit containing adjacent vertices in the graph \((V,\varnothing,\,E)\)._  
**Theorem 5** ([23]). : _Any solvable general shop scheduling problem \(\,GcMPT|t_{i}=1|C_{\max}\,\) on the mixed graph \(G=(V,A,\,E)\) is equivalent to finding an optimal coloring \(c(G)\) of the mixed graph \(G=(V,A,\,E)\). Conversely, for any colorable mixed graph \(G=(V,A,\,E)\), there exists a general shop scheduling problem \(\,GcMPT|t_{i}=1|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)\)._  
To illustrate Theorems 4 and 5, we consider Example 3 of the problem \(\,GcMPT|t_{i}=1|C_{\max}\,\) on the mixed graph \(G=(V,A,\,E)\) presented in Figure 2. The job \(J_{1}\in J\) includes the set \(V^{(1)}=\{v_{1},v_{2},v_{3}\}\) of the linearly ordered operations: \((v_{1},v_{2},v_{3})\). In Figure 2, the job \(J_{1}\in J\) is presented by a union of the path \((v_{1},v_{2},v_{3})\) in the digraph \((V,A,\varnothing)\) and the chain \((v_{1},v_{2},v_{3})\) in the graph \((V,\varnothing,E)\). The job \(J_{2}\in J\) includes the set \(V^{(2)}=\{v_{4},v_{5},v_{6}\}\) of the linearly ordered operations: \((v_{4},v_{5},v_{6})\). The job \(J_{2}\in J\) is presented by a union of the path \((v_{4},v_{5},v_{6})\) in the digraph \((V,A,\varnothing)\) and the chain \((v_{4},v_{5},v_{6})\) in the graph \((V,\varnothing,E)\). The job \(J_{3}\in J\) includes the set \(V^{(3)}=\{v_{7},v_{8},v_{9}\}\) of the linearly ordered operations: \((v_{7},v_{8},v_{9})\). The job \(J_{3}\in J\) is presented by a union of the path \((v_{7},v_{8},v_{9})\) in the digraph \((V,A,\varnothing)\) and the chain \((v_{7},v_{8},v_{9})\) in the graph \((V,\varnothing,E)\). The job \(J_{4}\in J\) includes the set \(V^{(4)}=\{v_{10},v_{11},v_{12}\}\) of the linearly ordered operations: \((v_{10},v_{11},v_{12})\). The job \(J_{4}\in J\) is presented by a union of the path \((v_{10},v_{11},v_{12})\) in the digraph \((V,A,\varnothing)\) and the chain \((v_{10},v_{11},v_{12})\) in the graph \((V,\varnothing,E)\). Machine \(M_{1}\) processes the operations \(V_{1}=\{v_{1},v_{4}\}\). In Figure 2, the forbiddance to process the operations from the set \(V_{1}\) simultaneously is determined by the edge \([v_{1},v_{4}]\) in the graph \((V,\varnothing,E)\). Machine \(M_{2}\) processes the operations \(V_{2}=\{v_{2},v_{5}\}\). The forbidance to process the operations from the set \(V_{2}\) simultaneously is determined by the edge \([v_{2},v_{5}]\). Machine \(M_{3}\) processes the operations \(V_{3}=\{v_{2},v_{4}\}\). The forbidance to process any pair of operations from the set \(V_{3}\) simultaneously is determined by the edge \([v_{2},v_{4}]\). Machine \(M_{4}\) processes the operations \(V_{4}=\{v_{5},v_{8},v_{10}\}\). The forbidance to process any pair of operations from the set \(V_{4}\) simultaneously is determined by the clique \(\{v_{5},v_{8},v_{10}\}\) in the graph \((V,\varnothing,E)\). Machine \(M_{5}\) processes the operations \(V_{5}=\{v_{6},v_{9},v_{11}\}\). The forbidance to process any pair of operations from the set \(V_{5}\) simultaneously is determined by the clique \(\{v_{6},v_{9},v_{11}\}\). Machine \(M_{6}\) processes the operations \(V_{6}=\{v_{7},v_{9}\}\). The forbidance to process the operations from the set \(V_{6}\) simultaneously is determined by the edge \([v_{7},v_{9}]\). Machine \(M_{7}\) processes the operations \(V_{7}=\{v_{2},v_{8}\}\). The forbidance to process the operations from the set \(V_{7}\) simultaneously is determined by the edge \([v_{2},v_{8}]\). Machine \(M_{8}\) processes the operations \(V_{8}=\{v_{9},v_{10}\}\). The forbidance to process the operations from the set \(V_{8}\) simultaneously is determined by the edge \([v_{9},v_{10}]\). Machine \(M_{9}\) processes the operations \(V_{9}=\{v_{7},v_{12}\}\).