УПРАВЛЕНИЕ И ПРИНЯТИЕ РЕШЕНИЙ

Кусочно-непрерывные пути в задачах построения и оптимизации расписаний

А. М. Магомедов

ФГБОУ высшего образования «Дагестанский государственный университет» (ДГУ), г. Махачкала

Аннотация: Исходные данные к расписанию заданы в виде двудольного графа, где вершинам двух долей графа соотнесены специализированные процессоры и задания соответственно, ребрам – предписанные операции единичной длительности по обработке заданий процессорами. Расписание рассматривается как отображение множества ребер графа в множество положительных целых чисел – «цветов» ребер (множество дискретных временны х промежутков единичной длительности, назначенных для выполнения той или иной операции). В качестве теоретико-графовой модели расписания для мультипроцессорной системы без простоев процессоров и прерываний заданий рассматривается реберная интервальная раскраска двудольного графа. Определены необходимые для анализа конструкции графа, с их использованием установлен ряд свойств интервальной раскраски. На основе понятия кусочно-непрерывного пути разработан эвристический алгоритм интервальной раскраски, эффективный для случаев, представляющих интерес как для теории, так и для прикладных задач оптимизации расписаний. Обсуждаются результаты применения программного обеспечения, разработанного на основе эвристического алгоритма, и перспективы работы.

Ключевые слова: расписание, граф, алгоритм, раскраска, сложность.

Реферативные базы данных:

•