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

Задача обслуживания частично упорядоченных единичных требований последовательными приборами формулируется как раскраска смешанного графа, т. е. как назначение целых чисел (цветов) ${1, 2, …, t}$ вершинам (требованиям) $V ={v_1, v_2, \ldots, v_n}$ смешанного графа $G = (V, A, E)$, при котором вершины $v_p$ и $v_q$, инцидентные ребру $[v_p, v_q] \in E$, имеют различные цвета. А при наличии дуги $(v_i, v_j) \in A$ цвет вершины $v_i$ не превосходит цвет вершины $v_j$. Доказано, что оптимальная раскраска смешанного графа $G = (V, A, E)$ эквивалентна задаче $GcMPT|p_i = 1|C_{max}$ поиска оптимального расписания обслуживания частично упорядоченных требований с единичными (одинаковыми) длительностями. В отличие от классических задач построения расписаний в рассматриваемой задаче $GcMPT|p_i = 1|C_{max}$ необходимо несколько различных приборов для обслуживания отдельного требования. Помимо отношений предшествования, заданных на множестве требований $V ={v_1, v_2, \ldots, v_n}$ должно выполняться некоторое подмножество требований одновременно. На основании доказанных в статье теорем утверждается, что множество аналитических результатов, полученных ранее для задач $GcMPT|p_i = 1|C_{max}$, имеют аналоги для оптимальных раскрасок смешанных графов $G = (V, A, E)$, и наоборот.