# Scheduling Multiprocessor Tasks with Equal Processing Times as a Mixed Graph Coloring Problem
## 1 Introduction
### Scheduling Multiprocessor Tasks with Unit Durations
The forbidance to process the operations from the set \(V_{9}\) simultaneously is determined by the edge \([v_{7},v_{12}]\). Machine \(M_{10}\) processes one operation \(V_{10}=\{v_{3}\}\). The machines, which are used to process the task \(v_{i}\in V\), are presented near the vertex \(v_{i}\) in Figure 2.  
The precedence relations between operations belonging to different jobs are given as follows: \(v_{3}\mapsto v_{6},\,\,v_{6}\mapsto v_{3},\,\,v_{8}\mapsto v_{4}\); and \(v_{12}\mapsto v_{1}\). These precedence constraints are presented by arcs \(\{(v_{3},v_{6}),\,\,(v_{6},v_{3}),\,(v_{8},v_{4}),\,(v_{12},v_{1})\}\subset A\) and edge \([v_{1},v_{12}]\in E\). The digraph \((V,A,\varnothing)\) has only one circuit \((v_{3},v_{6},v_{3})\) and this circuit has no adjacent vertices in the graph \((V,\varnothing,\,\,E)\) Since the digraph \((V,A,\varnothing)\) has no circuit containing adjacent vertices in the graph \((V,\varnothing,\,\,E)\), there exists a feasible schedule for Example 3 of the problem \(GcMPT|t_{i}=1|C_{\max}\) on the mixed graph \(G=(V,A,\,E)\); see Theorem 4. Due to Theorem 5, an optimal schedule for Example 3 is determined by the following optimal coloring \(c(G)\) of the mixed graph \(G=(V,A,\,E)\): \(c(v_{1})=4\), \(c(v_{2})=5\), \(c(v_{3})=6\), \(c(v_{4})=2\), \(c(v_{5})=3\), \(c(v_{6})=6\), \(c(v_{7})=1\), \(c(v_{8})=2\), \(c(v_{9})=3\), \(c(v_{10})=1\), \(c(v_{11})=2\), \(c(v_{12})=3\). The coloring \(c(G)\) is optimal; \(\chi(G)=6\). The optimality of the schedule determined by the coloring \(c(G)\) follows from the fact that the mixed graph \(G=(V,A,\,E)\) includes the path \((v_{10},v_{11},v_{12},v_{1},v_{2},v_{3})\), whose length is equal to \(6\). Therefore, the non-strict inequality \(\chi(G)\geq 6\) must hold. Two Equivalent Problems of Scheduling Unit-Time Multiprocessing Tasks as Optimal Colorings of the Mixed Graphs  
We next prove that any general shop scheduling problem \(GcMPT|t_{i}=1,[r_{i}]|C_{\max}\) with non-negative integer release times \(r_{i}\geq 0\) of the jobs \(J_{i}\in J\) is equivalent to an optimal coloring \(c(G)\) of the mixed graph \(G=(V,A,\,E)\). Since all release times \(r_{i}\) are non-negative integer numbers, the input data for the general shop scheduling problem \(GcMPT|t_{i}=1,[r_{i}]|C_{\max}\) may be represented by the mixed graph \(G=(V,A,\,E)\). Thus, Theorem 4 is correct for this scheduling problem as well. Figure 2: Mixed graph \(G=(V,A,\,E)\) determining Example 3 of the general shop scheduling problem \(GcMPT|t_{i}=1|C_{\max}\) with 4 jobs and 10 machines, optimal mixed graph coloring \(c(G)\) being equivalent to Example 3. Scheduling Unit-Time Multiprocessing Tasks to Minimize the Makespan as an Optimal Mixed Graph Coloring Problem  
In the general shop scheduling problem \(\,\mathit{GcMPT}|t_{i}=1,[r_{i}]|C_{\max}\,\), a multiprocessor task \(v_{i}\in V\) may be regarded as a job \(j_{i}\). The job \(j_{i}\) may include ether one task (operation) \(v_{i}\in V\) or more than one task (several operations). Let a simple job be a job consisting of a single task (operation). Theorem 3.1: _Any solvable general shop scheduling problem \(\,\mathit{GcMPT}|t_{i}=1,[r_{i}]|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 \(\,\mathit{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)\)._  
Proof: Every solvable general shop scheduling problem \(\,\mathit{GcMPT}|t_{i}=1|C_{\max}\,\) defines a mixed graph \(G^{\prime}=(V^{\prime},A^{\prime},\,E^{\prime})\) presenting the input data for this problem. Using this mixed graph \(G^{\prime}=(V^{\prime},A^{\prime},\,E^{\prime})\), we construct a mixed graph \(G=(V,A,\,E)\) determining the input data for the general shop scheduling problem \(\,\mathit{GcMPT}|t_{i}=1,[r_{i}]|C_{\max}\,\).