# Scheduling Multiprocessor Tasks with Equal Processing Times as a Mixed Graph Coloring Problem
## 1 Introduction
### Scheduling Multiprocessor Tasks with Unit Durations
_Step 2_: **IF**\(k=m+1\)**GOTO** step 5 **ELSE** find all maximum (with respect to the inclusion) complete vertex-induced subgraphs \((V_{k}^{1},\varnothing,E_{k}^{1})\),..., \((V_{k}^{l_{k}},\varnothing,E_{k}^{l_{k}})\) of the graph \((V_{k},\varnothing,E_{k})\). Set \(r=1\) and \(i=i+k_{k-1}+1\). _Step 3_: **FOR** index \(i\), supplement machine \(M_{i}\) to the already constructed machine set; \(M:=M\cup\{M_{i}\}\). Establish that all tasks in the clique \(V_{k}^{r}\) of the connected graph \((V_{k},\varnothing,E_{k})\) must be processed by machine \(M_{i}\) ; \(V_{k}^{r}=V_{i}=\left\{v_{i_{1}},v_{i_{2}},\ldots,v_{i_{|V_{i}|}}\right\}\), where all tasks  
\(\left\{v_{i_{1}},v_{i_{2}},\ldots,v_{i_{|V_{i}|}}\right\}\) must be processed by machine \(M_{i}\) in any feasible schedule. Set \(i:=i+1\). _Step 4_: **IF**\(i=\sum_{k=0}^{k}l_{k}\)**THEN** set \(k:=k+1\)**GOTO** step 2 **ELSE** set \(r:=r+1\)**GOTO** step 3. _Step 5_: **FOR** each index \(j\in\{m+1,\ldots,m+r\}\), supplement machine \(M_{i+j-m}\) to the already constructed machine set \(M\); \(M:=M\cup\left\{M_{i+j-m}\right\}\). Establish that task \(v_{i_{1}}\), \(V_{j}=\left\{v_{i_{k}}\right\}\), which is isolated in the graph \((V,\varnothing,E)\), must be processed by machine \(M_{i+j-m}\). Establish that machine \(M_{i+j}\) must process only task \(v_{i_{1}}\). Set \(M:=M\cup\{M_{i+1},\ldots,M_{i+r}\}\). _Step 6_: **FOR** each arc \((v_{p},v_{q})\in A\) such that the implication (1) holds and \(E^{*}\subseteq E\), determine the precedence constraint \(v_{p}\mapsto v_{q}\), which means that processing the task \(v_{p}\) must be completed before starting the task \(v_{p}\) in any feasible schedule. _Step 7_: **FOR** each arc \((v_{p},v_{q})\in A\) such that the implication (1) does not hold, determine the precedence constraint \(v_{p}\mapsto v_{q}\), which means that processing the task \(v_{p}\) must be started before the start time of the task \(v_{p}\) in any feasible schedule. _Step 8_: The desired general shop scheduling problem \(\mathit{GcMPT}|t_{i}=1,[r_{i}]|C_{\max}\) on the mixed graph \(G=(V,A,E)\) is constructed, where the precedence constraints on the task set \(V\) are determined at step 6 and step 7. Further, the set \(M\) of the machines is determined at step 3 and step 5 **STOP**. **Case II. ** Let the set \(\Omega\) be not empty; \(\Omega\
eq\varnothing\). Since the mixed graph \(G=(V,A,\ E)\) is colorable, each circuit \((v_{k_{1}},v_{k_{2}},\ldots,v_{k_{|V(k)|}},v_{k_{1}})\) in the set \(\Omega\) has no adjacent vertices in the graph \((V,\varnothing,E)\) (due to Theorem 1). Thus, all tasks \(\left\{v_{k_{1}},v_{k_{2}},\ldots,v_{k_{|V(k)|}}\right\}=V(k)\) must be processed simultaneously in any feasible schedule existing for the general shop scheduling problem \(\mathit{GcMPT}|t_{i}=1,[r_{i}]|C_{\max}\) on the mixed graph \(G=(V,A,E)\), where the circuit \((v_{k_{1}},v_{k_{2}},\ldots,v_{k_{|V(k)|}},v_{k_{1}})\) exists in the directed subgraph \((V,A,\varnothing)\). Let \(\Omega=\bigcup\limits_{k=1}^{w}V(k)=\bigcup\limits_{k=1}^{w}\left\{(v_{k_{1}}, v_{k_{2}},v_{k_{3}},\ldots,v_{k_{|V(k)|}-1},v_{k_{|V(k)|}},v_{k_{1}})\right\}\). We delete all arcs \(A_{c}\) determined in (2) from the mixed graph \(G=(V,A,E)\) and apply Algorithm 1 to the obtained circuit-free mixed graph \(G^{0}=(V,A)A_{c},\ E)\). As a result, we obtain the general shop scheduling problem \(\mathit{GcMPT}|t_{i}=1,[r_{i}]|C_{\max}\) on the mixed graph \(G^{0}=(V,A\setminus A_{c}\ E)\), which is equivalent to finding an optimal coloring \(c(G^{0})\) of the mixed graph \(G^{0}=(V,A\setminus A_{c}\ E)\). Thus, 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)\).