# Scheduling Multiprocessor Tasks with Equal Processing Times as a Mixed Graph Coloring Problem
## 1 Introduction
### Scheduling Multiprocessor Tasks with Unit Durations  
Contrary to the above classical problems \(J|t_{i}=1|C_{\max}\) and \(G|t_{i}=1|C_{\max}\), where a single machine (processor) fulfills an operation, in the processing system with multiprocessor tasks [28], a task (operation) requires either one machine or several machines during the fulfillment of the multiprocessor task (MPT for short). As usual, two tasks requiring at least one common machine cannot be processed simultaneously. Chapter 10 of the book [28] (pp. 264-283) presents the complexity results for the general shop minimum-length scheduling problem \(GMPT|t_{i}=1|C_{\max}\) with multiprocessor tasks. To solve the scheduling problem \(GMPT|t_{i}=1|C_{\max}\) means to construct an optimal schedule for processing the partially ordered multiprocessor tasks (operations) \(V=\{v_{1},v_{2},\,\ldots,v_{n}\}\) by the machines \(M=\left\{M_{1},M_{2},\ldots,M_{|M|}\right\}\). There has been increasing interest in multiprocessor scheduling, i.e., in scheduling models, where tasks require several processors simultaneously. Many scheduling problems fit in this model and a large amount of research has been carried on theoretical multiprocessor scheduling. Due to a wide practical importance scheduling problems with multiprocessor tasks have attracted considerable attention from researchers; see [30; 31; 32; 33; 34; 35; 36; 37; 38; 39; 40; 41]. The main part of article [34] is a presentation of the results in multiprocessor tasks scheduling both for parallel and for dedicated processors. The problems \(GMPT|t_{i}=1|\gamma\). with unit processing times have been considered in articles [30; 31; 32; 33; 34]. The general shop scheduling problem \(G|t_{i}=1|C_{\max}\) is a special case of the scheduling problem \(GMPT|t_{i}=1|C_{\max}\). Article [23] studies more general shop problem \(GcMPT|t_{i}=1|C_{\max}\) including the problem \(GMPT|t_{i}=1|C_{\max}\) as a special case. Let two types of the precedence constraints \(v_{k_{p}}\to v_{l_{q}}\) and \(v_{k_{p}}\mapsto v_{l_{q}}\) be given in the problem \(GcMPT|t_{i}=1|C_{\max}\). Furthermore, it is required that a subset \(V(k)=\left\{v_{k_{1}},v_{k_{2}},\,\ldots,v_{k_{|V(k)|}}\right\}\) of the tasks \(V=\{v_{1},v_{2},\,\ldots,v_{n}\}\supseteq V(k)\) must be processed simultaneously. In order to present the latter requirement, a circuit \((v_{k_{1}},v_{k_{2}},\,\ldots,v_{k_{|V(k)|}},v_{k_{1}})\) is included to the directed subgraph \((V,A,\varnothing)\) of the mixed graph \(G=(V,A,E)\), where the following relations hold: \(A^{\prime}_{c}=\left\{(v_{k_{1}},v_{k_{2}}),(v_{k_{2}},v_{k_{3}}),\,\ldots,(v_{k _{|V(k)|}}),v_{k_{|V(k)|}}),(v_{k_{|V(k)|}},v_{k_{1}})\right\}\subseteq A\). Let the input data of the general shop problem \(GcMPT|t_{i}=1|C_{\max}\) include \(w\) subsets \(V(1),V(2),\ldots,V(w)\) of the set \(V=\{v_{1},v_{2},\,\ldots,v_{n}\}\) such that all tasks in the set \(\left\{v_{k_{1}},v_{k_{2}},\,\ldots,v_{k_{|V(k)|}}\right\}=V(k)\subseteq V\), must be processed simultaneously in any feasible schedule. We obtain the following \(A_{c}\) subset of the set \(A\) of arcs:  
\[A_{c}=\mathop{\cup}\limits_{k=1}^{w}\left\{(v_{k_{1}},v_{k_{2}}),(v_{k_{2}},v_{ k_{3}}),\,\ldots,(v_{k_{|V(k)|}-1},v_{k_{|V(k)|}}),(v_{k_{|V(k)|}},v_{k_{1}})\right\}\subseteq A \tag{2}\]  
Every example of the general shop scheduling problem \(\,GcMPT|t_{i}=1|C_{\max}\) uniquely determines a mixed graph \(G=(V,A,\,E)\) with \(A_{c}\subseteq A\), which presents the input data for this example. Thus, to determine an example of the general shop scheduling problem \(\,GcMPT|t_{i}=1|C_{\max}\,\), it is sufficient to determine the mixed graph \(G=(V,A,\,E)\) for this example. Such an example is called a problem \(\,GcMPT|t_{i}=1|C_{\max}\,\) on the mixed graph \(G=(V,A,\,E)\). Article [23] contains the proofs of the following two theorems. **Theorem 4** ([23]).