Оптимальное по быстродействию расписание обслуживания требований с прерываниями операций как оптимальная раскраска смешанного графа

Установлена взаимосвязь задач теории расписаний с критерием минимизации длины расписания и задач поиска оптимальных (строгих) раскрасок вершин смешанного графа, т.е. назначений минимального множества упорядоченных цветов вершинам ${V=\{v_1, \ldots, v_{|V|}\}}$ смешанного графа ${G=(V,A,E)}$, для которых вершинам $v_i$ и $v_j$, инцидентным ребру ${[v_i, v_j] \in E}$, назначаются разные цвета, а для дуги ${(v_k, v_l) \in A}$ цвет вершины $v_k$ не больше (меньше) цвета вершины $v_l$. Показано, что любая задача поиска оптимальной раскраски вершин смешанного графа $G$ может быть представлена как задача $G_cMPT|[p_{ij}],pmtn|C_{\max}$ построения оптимального по быстродействию расписания обслуживания частично упорядоченного множества требований с целочисленными длительностями $p_{ij}$ операций при допустимости прерываний их выполнения. В отличие от классических задач теории расписаний, в задаче $G_cMPT|[p_{ij}],pmtn|C_{\max}$ для выполнения операции может требоваться несколько приборов и помимо двух типов отношений предшествования, заданных на множестве операций, необходимо, чтобы единичные операции заданного подмножества выполнялись одновременно. Задача $G_cMPT|[p_{ij}],pmtn|C_{\max}$ псевдополиномиально сводится к задаче поиска оптимальной раскраски вершин смешанного графа $G$, который определяет исходные данные задачи. В силу доказанных утверждений для результатов, полученных для задачи $G_cMPT|[p_{ij}],pmtn|C_{\max}$, имеются аналоги для соответствующих задач оптимальных раскрасок вершин смешанных графов $G$, и наоборот.