Mixed graph colouring as scheduling multi-processor tasks with equal processing times

Yu. N. Sotskov

Journal of the Belarusian State University. Mathematics and Informatics, Tome 2 (2021), pp. 67-81

Résumé

A problem of scheduling partially ordered unit-time tasks processed on dedicated machines is formulated as a mixed graph colouring problem, i. e., as an assignment of integers (colours) ${1, 2, …, t}$ to the vertices (tasks) $V ={v_1, v_2, \ldots, v_n}$ of the mixed graph $G = (V, A, E)$ such that if vertices $v_p$ and $v_q$ are joined by an edge $[v_p, v_q] \in E$, their colours have to be different. Further, if two vertices $v_i$ and $v_j$ are joined by an arc $(v_i, v_j) \in A$ the colour of vertex $v_i$ has to be no greater than the colour of vertex $v_j$. We prove that an optimal colouring of a mixed graph $G = (V, A, E)$ is equivalent to the scheduling problem $GcMPT|p_i = 1|C_{max}$ of finding an optimal schedule for partially ordered multi-processor tasks with unit (equal) processing times. Contrary to classical shop-scheduling problems, several dedicated machines are required to process an individual task in the scheduling problem $GcMPT|p_i = 1|C_{max}$. Moreover, along with precedence constraints given on the set $V ={v_1, v_2, \ldots, v_n}$, it is required that a subset of tasks must be processed simultaneously. Due to the theorems proved in this article, most analytical results that have been proved for the scheduling problems $GcMPT|p_i = 1|C_{max}$ so far, have analogous results for optimal colourings of the mixed graphs $G = (V, A, E)$, and vice versa.

Détail

Keywords: optimisation; unit-time scheduling; makespan; mixed graph; vertex colouring.