# Scheduling Multiprocessor Tasks with Equal Processing Times as a Mixed Graph Coloring Problem
## 1 Introduction
### A Unit-Time Minimum-Length Job-Shop Scheduling Problem
** Edge \([v_{i},v_{j}]\) belongs to the set \(E^{*}\) if and only if the implication (1) holds. **Property 3. ** The following partition: \((V,\varnothing,E\backslash E^{*})=(V_{1},\varnothing,E_{1})\cup(V_{2}, \varnothing,E_{2})\cup\dots\cup(V_{m},\varnothing,E_{m})\) holds, where each subgraph \((V_{k},\varnothing,E_{k})\) of the mixed graph \(G=(V,A,\,E)\) is a complete graph for each index \(k\in\{1,2,\dots,m\}\). Article [4] contains the proof of the following theorem. **Theorem 2 ([4]). **_Any job-shop scheduling problem \(J|t_{i}=1|C_{\max}\) on mixed graph \(G=(V,A,E)\) is equivalent to optimal coloring \(c(G)\) of the mixed graph \(G=(V,A,E)\). Conversely, any optimal coloring \(c(G)\) of mixed graph \(G=(V,A,E)\) possessing properties 1-3 is equivalent to a job-shop scheduling problem \(J|t_{i}=1|C_{\max}\) on the mixed graph \(G=(V,A,E)\)_  
To illustrate Theorem 2, we consider the following Example 1 of the job-shop scheduling problem \(J|t_{i}=1|C_{\max}\) with four jobs and five machines; see Figure 1.  
**Example 1. ** The machine set \(\{M_{1},M_{2},\dots,M_{5}\}=M\) have to process the job set \(\{J_{1},J_{2},J_{3},J_{4}\}=J\), where 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})\). The job \(J_{1}\in J\) is represented 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},v_{7},v_{8}\}\) of the linearly ordered operations: \((v_{4},v_{5},v_{6},v_{7},v_{8})\). The job \(J_{2}\in J\) is represented by a union of the path \((v_{4},v_{5},v_{6},v_{7},v_{8})\) in the digraph \((V,A,\varnothing)\) and the chain \((v_{4},v_{5},v_{6},v_{7},v_{8})\) in the graph \((V,\varnothing,E)\). The job \(J_{3}\in J\) includes the set \(V^{(3)}=\{v_{9},v_{10},v_{11},v_{12}\}\) of the linearly ordered operations: \((v_{9},v_{10},v_{11},v_{12})\). The job \(J_{3}\in J\)  
Figure 1: Mixed graph \(G=(V,A,E)\) determining the input date for Example 1 of the job-shop scheduling problem \(J|t_{i}=1|C_{\max}\), optimal mixed graph coloring \(c(G)\) being equivalent to Example 1.  
is represented by a union of the path \((v_{9},v_{10},v_{11},v_{12})\) in the digraph \((V,A,\varnothing)\) and the chain \((v_{9},v_{10},v_{11},v_{12})\) in the graph \((V,\varnothing,E)\). The job \(J_{4}\in J\) includes the set \(V^{(4)}=(v_{13},v_{14},v_{15})\) of the linearly ordered operations: \((v_{13},v_{14},v_{15})\). The job \(J_{4}\in J\) is represented by a union of the path \((v_{13},v_{14},v_{15})\) in the digraph \((V,A,\varnothing)\) and the chain \((v_{13},v_{14},v_{15})\) in the graph \((V,\varnothing,E)\). The set \(V_{1}=\{v_{1},v_{4}\}\) is a set of operations processed by machine \(M_{1}\). In Figure 1, the forbiddance to process the operations from the set \(V_{1}\) simultaneously is determined by the clique \(\{v_{1},v_{4}\}\) in the graph \((V,\varnothing,E)\). Machine \(M_{2}\) processes the operations \(V_{2}=\{v_{2},v_{5},v_{10}\}\). The forbiddance to process a pair of operations from the set \(V_{2}\) simultaneously is determined by the clique \(\{v_{2},v_{5},v_{10}\}\). Machine \(M_{3}\) processes the operations \(V_{3}=\{v_{3},v_{7},v_{12},v_{13}\}\). The forbiddance to process operations from the set \(V_{2}\) simultaneously is determined by the clique \(\{v_{3},v_{7},v_{12},v_{13}\}\). Machine \(M_{4}\) processes the operations \(V_{3}=\{v_{9},v_{11},v_{15}\}\). The forbiddance to process a pair of operations from the set \(V_{2}\) simultaneously is determined by the clique \(\{v_{9},v_{11},v_{15}\}\). Machine \(M_{5}\) processes the operations \(V_{5}=\{v_{6},v_{8},v_{14}\}\). The forbiddance to process a pair of operations from the set \(V_{2}\) simultaneously is determined by the clique \(\{v_{6},v_{8},v_{14}\}\).