Обзор алгоритмов планировщиков параллельных задач: эволюция, классификация и современные подходы

Планирование параллельных задач является одной из фундаментальных проблем в области высокопроизводительных вычислений, распределённых систем и облачных технологий. Данная задача относится к классу NP-трудных, что исключает возможность получения точного оптимального решения для больших входных данных за полиномиальное время. Поэтому особое внимание исследователей привлекают приближённые, эвристические и метаэвристические методы, которые обеспечивают приемлемое качество решений в разумные сроки. В статье представлен обзор существующих подходов к планированию: от классических эвристических алгоритмов (HEFT, CPOP, PEFT, DSC) и метаэвристик (генетические алгоритмы, муравьиные колонии, роевой интеллект) до динамических методов (work-stealing, gang scheduling), промышленных планировщиков (Borg, Omega, Mesos, Kubernetes) и новейших решений на основе машинного обучения и обучения с подкреплением (Decima, RL-подходы). Рассматриваются вопросы оркестрации — управления жизненным циклом приложений и контейнеров в облачных средах. Подчёркивается связь теоретических моделей с реальными промышленными системами, такими как Google Borg, Apache Mesos и Kubernetes, которые стали индустриальными стандартами. Уделено внимание тестовым бенчмаркам, следам из реальных дата-центров (Google Borg, Microsoft Azure), а также открытым проблемам и перспективам дальнейших исследований.