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

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