This article is cited in
3 papers
Discrete mathematics and Mathematical cybernetics
Mixed graph colouring as scheduling multi-processor tasks with equal processing times
Yu. N. Sotskov United Institute of Informatics Problems, National Academy of Sciences of Belarus, 6 Surhanava Street, Minsk 220012, Belarus
Abstract:
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.
Keywords:
optimisation; unit-time scheduling; makespan; mixed graph; vertex colouring.
UDC:
681.32
Language: English
DOI:
10.33581/2520-6508-2021-2-67-81