# Scheduling Multiprocessor Tasks with Equal Processing Times as a Mixed Graph Coloring Problem
## 1 Introduction
### A General Shop Unit-Time Scheduling Problem to Minimize the Makespan  
The general shop scheduling problem \(G|t_{i}=1|C_{\max}\) is a generalization of the job-shop scheduling problem \(J|t_{i}=1|C_{\max}\) considered in Section 2.1. In the former problem \(G|t_{i}=1|C_{\max}\), along with the linear orders given on the sets \(V^{(k)}\), \(J_{k}\in J\), there are also given the precedence constraints between operations belonging to different jobs in the set \(J\). We next consider two types of the precedence constraints provided that the problem \(G|t_{i}=1|C_{\max}\) be modeled as a coloring \(c(G)\) of the mixed graph \(G=(V,A,E)\). If the completion time \(c_{k_{p}}\) of the operation \(v_{k_{p}}\) of the job \(J_{k}\in J\) has to precede the start time \(s_{t_{q}}\) of the operation \(v_{l_{q}}\) of the job \(J_{l}\in J\), where \(k\
eq l\), then the mixed graph \(G=(V,A,E)\) must contain both arc \((v_{k_{p}},v_{l_{q}})\in A\) and edge \([v_{k_{p}},v_{l_{q}}]\in E\). In what follows, we denote this type of the precedence constraints as: \(v_{k_{p}}\to v_{l_{q}}\). Hence, if the precedence constraint \(v_{p}\to v_{q}\) holds for the general shop scheduling problem \(G|t_{i}=1|C_{\max}\), then the implication (1) must hold for the arc \((v_{p},v_{q})\in A\), i.e., \((v_{p},v_{q})\in A\Rightarrow[v_{p},v_{q}]\in E^{*}\), where \(E^{*}\subseteq E\). If the start time \(s_{k_{p}}\) of the operation \(v_{k_{p}}\) of the job \(J_{k}\in J\) has to precede the start time \(s_{l_{q}}\) of the operation \(v_{l_{q}}\) of the job \(J_{l}\in J\), where \(k\
eq l\), then the mixed graph \(G=(V,A,E)\) must contain only arc \((v_{k_{p}},v_{l_{q}})\in A\) as an addition. In what follows, we denote this type of the precedence constraints as: \(v_{k_{p}}\mapsto v_{l_{q}}\). Hence, if the precedence constraint \(v_{p}\mapsto v_{q}\) holds for the general shop scheduling problem \(G|t_{i}=1|C_{\max}\), then the implication (1) does not hold for the arc \((v_{p},v_{q})\in A\). Article [23] contains the proof of Theorem 3 on the connection between the mixed graph coloring problem and the general shop scheduling problem \(G|t_{i}=1|C_{\max}\). Theorem 3 ([23]): _Any general shop scheduling problem \(G|t_{i}=1|C_{\max}\) on the mixed graph \(G=(V,A,E)\) is represented as an optimal coloring \(c(G)\) of the mixed graph \(G=(V,A,E)\)._  
Note that the inverse claim to Theorem 3 is not correct, i.e., there exists a problem of optimal coloring of the mixed graph, which cannot be represented as a general shop scheduling problem \(G|t_{i}=1|C_{\max}\). We next consider Example 2 of the general shop scheduling problem \(G|t_{i}=1|C_{\max}\) on the mixed graph \(G^{*}=(V,A^{*},\,E^{*})\), which defers from the mixed graph \(G=(V,A,E)\) depicted in Figure 1 by three arcs and one edge. **Example 2. ** The general shop scheduling problem \(G|t_{i}=1|C_{\max}\) on the mixed graph \(G^{*}=(V,A^{*},\,E^{*})\) is the same as Example 1 of the problem \(J|t_{i}=1|C_{\max}\) with only exception that there are precedence constraints between operations belonging to different jobs \(I_{k}\) from the set \(J\). These additional precedence constraints are given as follows: \(v_{7}\mapsto v_{1}\); \(v_{12}\mapsto v_{5}\); and \(v_{14}\mapsto v_{9}\). Thus, for the mixed graph \(G^{*}=(V,A^{*},\,E^{*})\), the following equalities hold: \(A^{*}=A\cup\{(v_{7},v_{1}),(v_{12},v_{5}),(v_{14},v_{9})\}\); \(E^{*}=E\cup\{[v_{9},v_{14}]\}\). An optimal schedule for Example 2 is determined by the following optimal coloring \(c(G^{*})\) of the mixed graph \(G^{*}=(V,A^{*},\,E^{*})\): \(c(v_{1})=8\), \(c(v_{2})=9\), \(c(v_{3})=10\), \(c(v_{4})=1\), \(c(v_{5})=6\), \(c(v_{6})=7\), \(c(v_{7})=8\), \(c(v_{8})=9\), \(c(v_{9})=3\), \(c(v_{10})=4\), \(c(v_{11})=5\), \(c(v_{12})=6\), \(c(v_{13})=1,c(v_{14})=2,c(v_{15})=4\). This coloring \(c(G^{*})\) is optimal; \(\chi(G^{*})=10\).