# Scheduling Multiprocessor Tasks with Equal Processing Times as a Mixed Graph Coloring Problem
## 1 Introduction  
The world of manufacturing includes the following two main groups: custom manufacturing and mass production. In custom manufacturing, the quantity of the produced items may be small. Such production is highly flexible to enable a customization to the specific needs of the clients. Consequently, humans mostly perform custom manufacturing. Conversely, high automation characterizes scenarios of mass production, which consists of a fixed order of operations, uniform (equal) operation durations, a lack of the process flexibility, and an absorption of costs derived from the defective production units [1]. In our article, we focus on the above mass production, which presupposes the scheduling problems with unit processing times of the jobs to minimize either makespan \(C_{\max}\) (the schedule length) or maximal lateness \(L_{\max}\). Scheduling models with equal (unit) processing times of the jobs are an approximation for coping with the mass-industrial productions and manufactures of similar items, particularly for job-shop manufacturing that allows a manager to personalize an individual item [2]. Unit-time shop-scheduling problems to minimize the makespan are equivalent to an optimal graph coloring problem that consists of assigning a minimal number of colors to the vertices of a graph such that no two adjacent vertices have the same color. If a unit-time, shop-scheduling problem requires both precedence and incompatibility constraints; a mixed graph coloring [3] allows modeling such a shop-scheduling problem. Since publishing article [3], many studies on the unit-time shop-scheduling problems with minimizing the makespan are based on mixed graph colorings. Let \(G=(V,A,\,E)\) denote a mixed graph with the set \(V=\{v_{1},v_{2},\,\ldots,v_{n}\}\
eq\varnothing\) of the vertices placed at the first position in parenthesis, the set \(A\) of the arcs at the second position, and the set \(E\) of the edges at the third position. The arc \((v_{i},v_{j})\in A\) is an ordered pair of vertices \(v_{i}\) and \(v_{j}\), while the edge \([v_{p},v_{q}]\in E\) is an unordered pair of vertices \(v_{p}\) and \(v_{q}\). If the equality \(A=\varnothing\) holds, one has a graph \(G=(V,\varnothing,\,E)\). If the equality \(E=\varnothing\) holds, one has a digraph \(G=(V,A,\varnothing)\). A mixed graph \(G=(V,A,\,E)\) under consideration contains no multiple arcs, no multiple edges, and no loops. Article [3] introduces an optimal mixed graph coloring problem as follows. Definition 1 ([3]): An integer-valued function \(c:V\to\{1,2,\,\ldots,t\}\) is called a coloring \(c(G)\) of the mixed graph \(G=(V,A,\,E)\) if the non-strict inequality \(c(v_{i})\leq c(v_{j})\) holds for each arc \((v_{i},v_{j})\in A\) and the relation \(c(v_{p})\
eq c(v_{q})\) holds for each edge \([v_{p},v_{q}]\in E\). A mixed graph coloring \(c(G)\) is optimal if it uses a minimal number \(\chi(G)\) of different colors \(c(v_{i})\in\{1,2,\,\ldots,t\}\); such a minimal number \(\chi(G)\) of the used colors being called a chromatic number of the mixed graph \(G=(V,A,\,E)\). If the equality \(A=\varnothing\) holds, the coloring \(c(G)\) is a usual coloring of the vertices of the graph \(G=(V,\varnothing,\,E)\). Contrary to coloring of the vertices of the graph \(G=(V,\varnothing,\,E)\) that exists for any graph \(G=(V,\varnothing,\,E)\), a mixed graph \(G=(V,A,\,E)\) may be un-colorable; see the following criterion proved in [3]. Theorem 1 ([3]): A coloring \(c(G)\) of the mixed graph \(G=(V,A,\,E)\) exists if and only if the digraph \((V,A,\varnothing)\) has no circuit containing adjacent vertices in the graph \((V,\varnothing,\,E)\). The mixed graph \(G=(V,A,\,E)\) is colorable if there exists a coloring \(c(G)\) of the mixed graph \(G=(V,A,\,E)\); otherwise, the mixed graph \(G=(V,A,\,E)\) is un-colorable. In articles [4; 5], it is shown that a job-shop scheduling problem with unit processing times of the operations and the minimization of the makespan may be represented as an optimal coloring \(c(G)\) of the specified mixed graph \(G=(V,A,\,E)\).