В 1852 году английский математик Фрэнсис Гутри сформулировал знаменитую Проблему четырех красок: можно ли раскрасить любую географическую карту так, чтобы никакие две соседние страны не имели одинакового цвета, используя не более четырех карандашей? Эта абстрактная топологическая загадка, решенная лишь век спустя с помощью суперкомпьютеров, заложила основы колоссального раздела исследования операций — Задачи раскраски графов (Graph Coloring Problem, GCP). Сегодня математический аппарат хроматических полиномов управляет распределением радиочастот в мобильных сетях, составляет расписания экзаменов в университетах и оптимизирует выделение регистров внутри микропроцессоров Intel и AMD.

Когда на заводе имеется лишь один станок, задача упорядочивания деталей (Single Machine Scheduling) сводится к поиску оптимальной перестановки в рамках одной очереди. Однако в современных облачных дата-центрах, распределяющих вычислительные задачи между тысячами серверов, или на крупных конвейерах, имеющих дублирующее оборудование, возникает задача планирования на параллельных машинах (Parallel Machine Scheduling). Эта математическая модель добавляет к классической задаче новое измерение: прежде чем упорядочить задачи во времени, алгоритм должен принять жесткое решение о том, на какой конкретный процессор (или станок) направить каждую конкретную работу. Сложность задачи радикально возрастает, переходя из разряда перестановок в класс NP-трудных задач комбинаторной оптимизации и упаковки в контейнеры.

Классический алгоритм Дейкстры идеально строит кратчайший путь, когда время проезда по каждой улице является абсолютно детерминированной константой. Но если мы проектируем навигатор для утреннего часа пик в мегаполисе или маршрутизируем пакеты в нестабильной беспроводной сети (Ad-hoc), время прохождения каждого ребра графа становится стохастической (случайной) величиной. Если просто заменить все случайные времена их средними математическими ожиданиями и запустить Дейкстру, полученный путь может оказаться катастрофически ненадежным (например, иметь огромную дисперсию задержек из-за вероятности аварий). Для решения этой проблемы исследование операций применяет аппарат Стохастических задач о кратчайшем пути (Stochastic Shortest Path, SSP).