Optimal'noe po bystrodeystviyu raspisanie obsluzhivaniya trebovaniy s preryvaniyami operatsiy kak optimal'naya raskraska smeshannogo grafa

Установлена взаимосвязь задач теории расписаний с критерием минимизации длины расписания и задач поиска оптимальных (строгих) раскрасок вершин смешанного графа, т.е. назначений минимального множества упорядоченных цветов вершинам V = {v1, . . . , v|V |} смешанного графа G = (V,A,E), для которых вершинам vi и vj , инцидентным ребру [vi, vj ] ∈ E, назначаются разные цвета, а для дуги (vk, vl) ∈ A цвет вершины vk не больше (меньше) цвета вершины vl. Показано, что любая задача поиска оптимальной раскраски вершин смешанного графа G может быть представлена как задача GcMPT |[pij], pmtn|Cmax построения оптимального по быстродействию расписания обслуживания частично упорядоченного множества требований с целочисленными длительностями pij операций при допустимости прерываний их выполнения. В отличие от классических задач теории расписаний, в задаче GcMPT |[pij], pmtn|Cmax для выполнения операции может требоваться несколько приборов и помимо двух типов отношений предшествования, заданных на множестве операций, необходимо, чтобы единичные операции заданного подмножества выполнялись одновременно. Задача GcMPT |[pij], pmtn|Cmax псевдополиномиально сводится к задаче поиска оптимальной раскраски вершин смешанного графа G, который определяет исходные данные задачи. В силу доказанных утверждений для результатов, полученных для задачи GcMPT |[pij], pmtn|Cmax, имеются аналоги для соответствующих задач оптимальных раскрасок вершин смешанных графов G, и наоборот.

расписание, прерывание, быстродействие, смешанный граф, оптимальная раскраска