# Scheduling Multiprocessor Tasks with Equal Processing Times as a Mixed Graph Coloring Problem
## 1 Introduction
### A Unit-Time Minimum-Length Job-Shop Scheduling Problem  
We first consider the following job-shop scheduling problem \(J|t_{i}=1|C_{\max}\) with unit processing times of the given operations and the objective criterion \(C_{\max}\) to minimize the makespan. In the job-shop scheduling problem \(J|t_{i}=1|C_{\max}\), a set of the jobs \(J=\left\{I_{1},I_{2},\ldots,J_{|J|}\right\}\) must be optimally processed on the different (dedicated) machines \(M=\left\{M_{1},M_{2},\ldots,M_{|M|}\right\}\). A job \(J_{k}\in J\) consists of the set \(V^{(k)}=\left\{v_{k_{1}},v_{k_{2}},\ldots,v_{k_{|V^{(k)}|}}\right\}\) of the linearly ordered operations: \((v_{k_{1}},v_{k_{2}},\ldots,v_{k_{|V^{(k)}|}})\). A specified machine from the set \(M\) is required to process (without preemptions) the operation \(v_{i}\) from the set \(V=\cup_{k=1}^{|J|}V^{(k)}\). The processing time \(t_{i}\) of each operation \(v_{i}\) in the set \(V\) is equal to \(1\). Let the set \(V_{i}=\left\{v_{i_{1}},v_{i_{2}},\ldots,v_{|v_{|v_{i}|}}\right\}\subseteq V\) denote a set of all operations processed by machine \(M_{i}\in M\). Any pair of the operations processed by the same machine cannot be processed simultaneously in any feasible schedule. In order to solve the job-shop scheduling problem \(J|t_{i}=1|C_{\max}\), it is necessary to find a non-preemptive schedule (each operation must be processed without preemptions), whose length \(C_{\max}=\max\left\{C_{1},C_{2},\ldots,C_{|J|}\right\}\) (the makespan) is minimum among lengths of all feasible schedules, where the completion time \(C_{k_{|V^{(k)}|}}\) of the last operation \(v_{k_{|V^{(k)}|}}\) of the job \(J_{k}\in J\). In articles [4; 5; 8; 9], it is shown that the job-shop scheduling problem \(J|t_{i}=1|C_{\max}\) may be represented as an optimal coloring \(c(G)\) of the specified mixed graph \(G=(V,A,\,E)\). Based on Definition 1, one can represent every job \(J_{k}\in J\) as a union of the path \((v_{k_{1}},v_{k_{2}},\ldots,v_{k_{\gamma_{k}}})\) in the directed subgraph \((V,A,\varnothing)\) of the mixed graph \(G=(V,A,\,E)\) and the chain \((v_{k_{1}},v_{k_{2}},\ldots,v_{k_{\gamma_{k}}})\) in the subgraph \((V,\varnothing,E)\). As a result, we determine the vertex set \(V=\cup_{k=1}^{|J|}V^{(k)}\) of the mixed graph \(G=(V,A,\,E)\), the set of the arcs \(A=\cup_{k=1}^{|J|}\left\{(v_{k_{1}},v_{k_{2}}),(v_{k_{2}},v_{k_{3}}),\ldots,( v_{k_{\gamma_{k}}-1},v_{k_{\gamma_{k}}})\right\}\), and the subset \(E^{*}\) of the edge set \(E\), which are defined based on the following implications:  
\[(v_{p},v_{q})\in A\Rightarrow[v_{p},v_{q}]\in E^{*} \tag{1}\]  
Due to Definition 1, the remaining subset \(E\setminus E^{*}\) of the edges in the subgraph \((V,\varnothing,\,E\setminus E^{*})\) of the mixed graph \(G=(V,A,\,E)\) is determined by \(|M|\) cliques \(\left\{v_{i_{1}},v_{i_{2}},\ldots,v_{i_{|v_{i}|}}\right\}\), where the set \(V_{i}=\left\{v_{i_{1}},v_{i_{2}},\ldots,v_{i_{|v_{i}|}}\right\}\) consists of all operations processed by machine \(M_{i}\in M\). Due to this, any pair of operations from the set \(V_{i}\subseteq V\) cannot be processed simultaneously. It is clear that the constructed mixed graph \(G=(V,A,\,E)\) determines the complete input date for the job-shop scheduling problem \(J|t_{i}=1|C_{\max}\); see articles [4; 5] for details. Thus, one can call such a scheduling problem as a job-shop scheduling problem \(J|t_{i}=1|C_{\max}\) on the mixed graph \(G=(V,A,\,E)\). Article [4] shows that if the mixed graph \(G=(V,A,\,E)\) determines the input date for the job-shop scheduling problem \(J|t_{i}=1|C_{\max}\), then this mixed graph \(G=(V,A,\,E)\) must possess the following mandatory properties. **Property 1. ** The following partition: \((V,A,\varnothing)=(V^{(1)},A^{(1)},\varnothing)\cup(V^{(2)},A^{(2)},\varnothing)\cup\dots \cup(V^{(r)},A^{(r)},\varnothing)\) holds, where each directed subgraph \((V^{(k)},A^{(k)},\varnothing)\) of the mixed graph \(G=(V,A,\,E)\) is a path \((v_{k_{1}},v_{k_{2}},\,\dots,v_{k_{r_{k}}})\) for each index \(k\in\{1,2,\dots,r\}\). **Property 2.