# Scheduling Multiprocessor Tasks with Equal Processing Times as a Mixed Graph Coloring Problem
## 1 Introduction
### Scheduling Multiprocessor Tasks with Unit Durations
The forbiddance to process operations from the set \(V_{9}\) simultaneously is determined by the edge \([v_{7},v_{12}]\). The machine \(M_{10}\) processes one operation \(V_{10}=\{v_{3}\}\). The precedence constraints between operations belonging to different jobs are given as follows: \(v_{3}\mapsto v_{6}\); \(v_{6}\mapsto v_{3}\); \(v_{4}\mapsto v_{8}\); \(v_{1}\to v_{12}\). In Figure 3, these precedence constraints are presented by four arcs \((v_{3},v_{6})\), \((v_{6},v_{3})\), \((v_{4},v_{8})\), \((v_{1},v_{12})\) and one edge \([v_{1},v_{12}]\) in the mixed graph \(G=(V,A,\,E)\). The release time \(r_{1}=3\) of the job \(J_{1}\in J\) is presented as a union of the path \((v_{15},v_{14},v_{13},v_{3})\) in the digraph \((V,A,\varnothing)\) and the chain \((v_{15},v_{14},v_{13},v_{3})\) in the graph \((V,\varnothing,E)\). The release time \(r_{2}=5\) of the job \(J_{2}\in J\) is presented as a union of the path \((v_{20},v_{19},v_{18},v_{17},v_{16},v_{6})\) in the digraph \((V,A,\varnothing)\) and the chain \((v_{20},v_{19},v_{18},v_{17},v_{16},v_{6})\) in the graph \((V,\varnothing,E)\). The release time \(r_{3}=3\) of the job \(J_{3}\in J\) is presented as a union of the path \((v_{23},v_{22},v_{21},v_{9})\) in the digraph \((V,A,\varnothing)\) and the chain \((v_{23},v_{22},v_{21},v_{9})\) in the graph \((V,\varnothing,E)\). The release time \(r_{4}=2\) of the job \(J_{4}\in J\) is presented as a union of the path \((v_{25},v_{24},v_{12})\) in the digraph \((V,A,\varnothing)\) and the chain \((v_{25},v_{24},v_{12})\) in the graph \((V,\varnothing,E)\). The digraph \((V,A,\varnothing)\) has one circuit \((v_{3},v_{6},v_{3})\), which 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 4 of the general shop scheduling problem \(\mathit{GcMPT}|t_{i}=1,[r_{i}]|C_{\max}\) on the mixed graph \(G=(V,A,\,E)\) (due to Theorem 4). Due to Theorem 6, an optimal schedule for Example 4 is determined by the following optimal coloring \(c(G)\) of the mixed graph \(G=(V,A,\,E)\) depicted in Figure 3: \(c(v_{1})=8\), \(c(v_{2})=7\), \(c(v_{3})=6\), \(c(v_{4})=9\), \(c(v_{5})=8\), \(c(v_{6})=6\), \(c(v_{7})=11\), \(c(v_{8})=10\), \(c(v_{9})=4\), \(c(v_{10})=11\), \(c(v_{11})=10\), \(c(v_{12})=9\), \(c(v_{13})=3\), \(c(v_{14})=2\), \(c(v_{15})=1\), \(c(v_{16})=5\), \(c(v_{17})=4\), \(c(v_{18})=3\), \(c(v_{19})=2\), \(c(v_{20})=1\), \(c(v_{21})=3\), \(c(v_{22})=2\), \(c(v_{23})=1\), \(c(v_{24})=2\), \(c(v_{25})=1\). The coloring \(c(G)\) with \(\chi(G)=11\) is optimal since the mixed graph \(G=(V,A,\,E)\) includes the path \((v_{20},v_{19},v_{18},v_{17},v_{16},v_{6},v_{3},v_{2},v_{1},v_{12},v_{11},v_{10})\) of the length \(11\). Thus, the non-strict inequality \(\chi(G)\geq 11\) must hold. Finding a Makespan Optimal Schedule with Integer Release Times Reduces to Finding a Schedule with a Smallest Maximal Lateness for Integer Due Dates  
We next prove the equivalence of the general shop scheduling problem \(\mathit{GcMPT}|t_{i}=1\), \([r_{i}]|C_{\max}\) with integer release times \(r_{i}\geq 0\), \(J_{i}\in J\), and the general shop scheduling problem \(\mathit{GcMPT}|t_{i}=1,[d_{i}]|L_{\max}\) to minimize the maximal lateness \(L_{\max}=\max\{C_{i}-d_{i}:J_{i}\in J\}\) with integer due dates \(d_{i}\geq 0\), \(J_{i}\in J\). To illustrate the proof of Theorem 7, we use Examples 4 of the general shop scheduling problem \(\mathit{GcMPT}|t_{i}=1,[r_{i}]|C_{\max}\) on the mixed graph \(G=(V,A,\,E)\) depicted in Figure 3.  
Theorem 7: _Any solvable general shop scheduling problem \(\mathit{GcMPT}|t_{i}=1,[r_{i}]|C_{\max}\) on the mixed graph \(G=(V,A,\,E)\) with integer release times \(r_{i}\geq 0\) is equivalent to a general shop scheduling problem \(\mathit{GcMPT}|t_{i}=1,[d_{i}]|L_{\max}\) with integer due dates \(d_{i}\geq 0\), and vice versa._  
Proof: The general shop scheduling problem \(\mathit{GcMPT}|t_{i}=1,[r_{i}]|C_{\max}\) under consideration is solvable.