A makespan-optimal schedule for processing jobs with possible operation preemptions as an optimal mixed graph coloring

This paper establishes a relationship between optimal scheduling problems with the minimum schedule length and the problems of finding optimal (strict) colorings of mixed graph vertices, i.e., assigning a minimal set of ordered colors to the vertices $V=\{v_1,\dots,v_{|V|}\}$ of a mixed graph $G = (V, A, E)$ so that the vertices $v_i$ and $v_j$ incident to an edge $[v_i, v_j] \in E$ will have different colors and the color of the vertex $v_k$ in an $\mathrm{arc} (v_k, vl_) \in A$ will be not greater (smaller) than that of the vertex $v_l$. As shown below, any optimal coloring problem for the vertices of a mixed graph $G$ can be represented as the problem $G_cMP T |[p_{ij}]$, $pmtn|C_{\max}$ of constructing a makespan-optimal schedule for processing a partially ordered set of jobs with integer durations $p_{ij }$ of their operations with possible preemptions. In contrast to classical scheduling problems, executing an operation in the problem $G_cMP T |[p_{ij}]$, $pmtn|C_{\max}$ may require several machines and, besides the two types of precedence relations defined on the set of operations, unit-time operations of a given subset must be executed simultaneously. The problem $G_cMP T |[p_{ij}]$, $pmtn|C_{\max}$ is pseudopolynomially reduced to the problem of finding an optimal coloring of the vertices of a mixed graph $G$ (the input data of the scheduling problem). Due to the assertions proved, the results obtained for the problem $G_cMP T |[p_{ij}]$, $pmtn|C_{\max}$ have analogs for the corresponding optimal coloring problems for the vertices of a mixed graph $G$, and vice versa.