Исследование алгоритмов планирования DAG в распределенных системах

Воркфлоу представляет из себя ориентированный ациклический граф вычислительных задач, связанных между собой зависимостями по данным. Такие структуры часто возникают при автоматизации сложных вычислений и обработки больших данных. Задача планирования воркфлоу заключается в составлении оптимального в некотором смысле расписания для запуска задач при заданной конфигурации системы. Под оптимальным расписанием обычно подразумевается либо самое дешёвое, либо самое быстрое корректное расписание. Такая задача хоть и является вычислительной сложной, но хорошо изучена для систем с ограниченным числом вычислительных узлов. Облачные вычисления предоставляют гибкий менеджмент вычислительной конфигурации системы благодаря возможности включать/отключать новые виртуальные машины. Целью данной работы является разработка алгоритма планирования. В работе обозреваются уже известные методы решения и предлагается новый подход к решению данной задачи. Ключевые слова: облачные вычисления, составление расписания, распределенные системы, граф вычислений, эвристические алгоритмы.