Теория расписаний: минимизация максимального запаздывания и алгоритм Мура-Ходжсона

Математическая формализация задачи вводит для каждого задания (работы) два ключевых параметра: время обработки (Processing Time) и директивный срок завершения (Due Date). Когда расписание составлено, для каждого задания можно вычислить фактическое время его завершения (Completion Time). Разность между фактическим временем завершения и директивным сроком называется опозданием (Lateness). Оно может быть как положительным (заказ сорван), так и отрицательным (заказ выполнен досрочно). Однако в контрактах за досрочное выполнение премий обычно не платят, поэтому математики ввели функцию запаздывания (Tardiness), которая равна нулю, если заказ выполнен вовремя или раньше, и равна опозданию, если сроки сорваны. Основными критериями оптимизации выступают: минимизация максимального запаздывания и минимизация общего количества сорванных заказов.

Для минимизации максимального запаздывания (Maximum Lateness) на одной машине существует тривиальное, но невероятно мощное решение — правило EDD (Earliest Due Date), открытое Джексоном. Правило гласит: чтобы минимизировать максимальную просрочку по всему пулу заказов, необходимо просто отсортировать все работы в порядке возрастания их директивных сроков. Какими бы длинными или короткими ни были операции, слепое выполнение работ в порядке их дедлайнов гарантированно дает глобально оптимальный результат по этому критерию. Строгое алгебраическое доказательство этого факта опирается на метод обмена смежных пар (Pairwise Interchange): если в расписании есть инверсия (работа с поздним дедлайном стоит перед работой с ранним), их обмен местами никогда не увеличит максимальное запаздывание.

Однако правило EDD не минимизирует количество сорванных заказов. Если у нас есть один гигантский заказ с ранним сроком, бросив на него все силы, мы можем провалить сроки для десятков мелких последующих заказов. Для минимизации числа запаздывающих работ (Number of Tardy Jobs) в 1968 году был разработан гениальный алгоритм Мура-Ходжсона. Этот жадный алгоритм начинает работу с сортировки всех заданий по правилу EDD. Затем он начинает последовательно добавлять работы в расписание. После добавления каждой работы алгоритм проверяет, не сорван ли ее дедлайн. Если дедлайн нарушен, алгоритм просматривает все уже включенные в расписание работы (включая только что добавленную) и безжалостно выбрасывает из расписания ту работу, которая имеет самое большое время обработки.

Выброшенные работы помещаются в отдельный список аутсайдеров и будут выполнены в самом конце, когда их задержка уже не будет иметь значения. Идея алгоритма Мура-Ходжсона заключается в том, что пожертвовав одной, самой длинной и ресурсоемкой работой, мы освобождаем максимальное количество машинного времени, что позволяет спасти от срыва сроков сразу множество других, более мелких заказов. Этот алгоритм работает за время пропорциональное N*log(N) и является абсолютным шедевром исследования операций, доказывая, что в условиях жесткого дефицита ресурсов спасение максимального числа клиентов требует хладнокровного математического отсечения самых тяжелых задач.