# Scheduling Multiprocessor Tasks with Equal Processing Times as a Mixed Graph Coloring Problem
## 1 Introduction
### Scheduling Multiprocessor Tasks with Unit Durations
To this end, for each job \(j_{i}\in J\), we add vertices \(v_{i_{\beta}},\,\ldots,v_{i_{\beta-1}}\) to the set \(V^{\prime}\) and path \((v_{i_{\beta}},\,\ldots,v_{i_{\beta-1}},v_{i_{1}})\), whose length is equal to \(r_{i}\), to the directed subgraph \((V^{\prime},A^{\prime},\varnothing)\) of the mixed graph \(G^{\prime}\). We also add the chain \((v_{i_{\beta}},\,\ldots,v_{i_{\beta-1}},v_{i_{1}})\), whose length is equal to \(r_{i}\), to the subgraph \((V^{\prime},\varnothing,E^{\prime})\) of the mixed graph \(G^{\prime}\). Let \(G=(V,A,\,E)\) denote a mixed graph obtained from the mixed graph \(G^{\prime}=(V^{\prime},A^{\prime},\,E^{\prime})\), where \(V=V^{\prime}\cup\bigcup\limits_{i=1}^{M}\left\{v_{i_{1}},\ldots,v_{i_{\beta-1 }}\right\}\right\}=:V^{\prime}\cup V^{0}\). It is easy to see that the constructed mixed graph \(G=(V,A,\,E)\) determines the input data for the general shop scheduling problem \(\,\mathit{GcMPT}|t_{i}=1,[r_{i}]|C_{\max}\,\). Since there is a feasible schedule for the general shop scheduling problem \(\,\mathit{GcMPT}|t_{i}=1,[r_{i}]|C_{\max}\,\), the directed subgraph \((V,A,\varnothing)\) of the mixed graph \(G=(V,A,\,E)\) has no circuit containing the adjacent vertices in the graph \((V,\varnothing,\,E)\) (due to Theorems 3.1 and 3.1). \(\square\)  
Any solvable example of the 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)\) due to the correspondence of the terms used in the optimal coloring \(c(G)\) of the mixed graph \(G=(V,A,E)\) and those used in the optimal schedule existing for this example of the general shop scheduling problem \(\,\mathit{GcMPT}|t_{i}=1,[r_{i}]|C_{\max}\,\). Table 1 presents the correspondence of these terms. Due to the existence of the clique \(\left\{v_{i_{1}},v_{i_{2}},\ldots,v_{i_{|j_{i}|}}\right\}\) in the graph \((V,\varnothing,E)\), each machine \(M_{i}\in M\) in the general shop scheduling problem \(\,\mathit{GcMPT}|t_{i}=1,[r_{i}]|C_{\max}\,\) on the mixed graph \(G=(V,A,\,E)\) can process at most one task within a unit-time semi-interval from the following set:  
\[\{[0,1],(1,2],(2,3],\ldots,(t-1,t]\} \tag{3}\]  
Furthermore, it is easy to see that an optimal coloring \(c:V\rightarrow\{1,2,\,\ldots,\chi(G)\}\) of the mixed graph \(G=(V,A,\,E)\) determines the optimal assignment of the tasks \(V\) to the following minimal number of the unit-time semi-intervals:  
\[\{[0,1],(1,2],(2,3],\ldots,(\chi(G)-1,\chi(G)]\} \tag{4}\]  
Such an assignment of the tasks (operations) \(V\) to the minimal number of the unit-time semi-intervals (4) is optimal since it determines a feasible schedule for processing the tasks (operations) \(V\), whose length is equal to the chromatic number \(\chi(G)\) of the mixed graph \(G=(V,A,\,E)\) that determines the input data for the general shop scheduling problem \(\,\mathit{GcMPT}|t_{i}=1,[r_{i}]|C_{\max}\,\). Due to the correspondence of terms used in the coloring \(c(G)\) of the mixed graph \(G=(V,A,\,E)\) and those used in the general shop scheduling problem on the mixed graph \(G=(V,A,E)\) (see Table 1), one can conclude that _any solvable example of the general shop scheduling problem_\(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)\)_._  
Next, we prove the following converse claim: _for any colorable mixed graph \(G=(V,A,E)\), there exists a general shop scheduling problem_\(GcMPT|t_{i}=1,[r_{i}]|C_{\max}\) _on the mixed graph graph \(G\), which is equivalent to finding an optimal coloring \(c(G)\) of the mixed graph \(G=(V,A,E)\). To this end, we detect a set \(\Omega\) of all circuits existing in the directed subgraph \((V,A,\varnothing)\) of the mixed graph \(G=(V,A,E)\) and consider two possible cases. **Case I. ** Let the set \(\Omega\) be empty; \(\Omega=\varnothing\).