Теория расписаний: задача с параллельными машинами (Parallel Machine Scheduling)

Математические модели параллельных машин классифицируются по трем типам архитектуры. Идентичные параллельные машины (Identical, обозначаемые как Pm) — все станки абсолютно одинаковы, и время выполнения работы на них идентично (например, кластер из одинаковых CPU). Однородные параллельные машины (Uniform, Qm) — станки выполняют одни и те же функции, но имеют разную базовую производительность (например, старые и новые процессоры в одном сервере; время выполнения работы делится на коэффициент скорости процессора). Несвязанные параллельные машины (Unrelated, Rm) — самый сложный класс, где время выполнения работы полностью зависит от комбинации конкретной работы и конкретной машины (станок А быстро режет сталь, но медленно алюминий, а станок Б — наоборот). Целевой функцией чаще всего выступает минимизация общего времени завершения всех работ (Makespan, C_max).

Для самой простой архитектуры — идентичных машин без прерываний с целью минимизации Makespan — задача является NP-трудной даже для двух станков. Эта задача математически изоморфна задаче о разбиении множества (Number Partitioning Problem): как разделить набор чисел на две группы так, чтобы их суммы были максимально близки друг к другу. Однако для нее существует невероятно мощная жадная эвристика — правило LPT (Longest Processing Time). Алгоритм LPT сортирует все работы по убыванию их длительности. Затем он берет самую длинную работу из списка и назначает ее на ту машину, которая в данный момент освободится раньше всех. Математически доказано (теорема Грэма), что для m идентичных машин эвристика LPT выдаст расписание, длина которого никогда не превысит абсолютный оптимум более чем на (4/3 - 1/(3m)) раз (худший случай — 33% погрешности).

Если архитектура усложняется (однородные или несвязанные машины), жадные правила терпят крах, и исследование операций применяет методы целочисленного линейного программирования (MILP). Для несвязанных параллельных машин задача формализуется с помощью бинарных переменных (1, если работа i назначена на машину j; 0 — иначе). Если целевой функцией является минимизация суммарного времени завершения (а не Makespan), задача внезапно становится полиномиально разрешимой! Она виртуозно сводится к классической Задаче о назначениях на двудольном графе (Bipartite Matching), где стоимости ребер зависят от позиции работы в очереди на станке. Эта задача легко решается Венгерским алгоритмом (или алгоритмами минимального потока стоимости) за миллисекунды для тысяч работ.

Современным вызовом теории расписаний стала интеграция ограничений на энергопотребление (Energy-Aware Scheduling). В дата-центрах Google и Amazon затраты на охлаждение серверов превышают стоимость самих серверов. Математические модели расширяются за счет функции Dynamic Voltage and Frequency Scaling (DVFS). Алгоритм должен не только распределить задачи по ядрам процессора, но и рассчитать оптимальную частоту и напряжение для каждого ядра в каждую секунду. Снижение частоты экономит энергию (кубическая зависимость), но замедляет выполнение задачи. Многокритериальная оптимизация с использованием метаэвристик (NSGA-II) выстраивает фронт Парето, позволяя облачным операторам балансировать между скоростью обслуживания клиентов и миллионными счетами за электричество, доказывая, что теория расписаний является краеугольным камнем зеленой энергетики.