Математическая формулировка (базовая)
- Пусть экзамены — вершины невзвешенного графа $G=(V,E)$, где ребро $(u,v)\in E$ означает, что есть хотя бы один студент, сдающий и $u$, и $v$ (конфликт). Временные слоты — цвета $1,\dots ,k$.
- Задача раскраски: найти отображение $f:V\to \{1,\dots ,k\}$ такое, что
$$\forall (u,v)\in E:f(u)\ne f(v).$$ Частные постановки: проверка существования $k$-раскраски (решение да/нет) или минимизация числа слотов (минимизация хроматического числа $\chi (G)$).
ILP-формулировка (базовая)
- Переменные $x_{v,t}\in \{0,1\}$ — 1 если экзамен $v$ назначен в слот $t$.
- Ограничения:
$$\forall v:\sum _{t=1}^k{x}_{v,t}=1,$$ $$\forall (u,v)\in E,\forall t:x_{u,t}+x_{v,t}\le 1.$$
Сложность
- Проблема существования $k$-раскраски NP-полна. Минимизация числа слотов (минимизация $\chi (G)$) NP‑трудна и плохо аппроксимируема (сильно NP‑трудна; аппроксимация в общем случае невозможна с полиномиальным множителем $n^{1-\epsilon }$ при общих предположениях).
Эвристические методы
- Однофазные greedy-подходы:
- Порядки: влиятельность по степени (largest degree first), DSATUR (жадная с учётом насыщенности).
- First-fit/Best-fit по порядку вершин.
- Локальный поиск и метаэвристики:
- Kempe‑цепи (перекраски), tabu‑search, simulated annealing, iterated local search, genetic algorithms, ant colony.
- Перемещения: репламинг цвета, обмены пар вершин, слияние/разбиение классов.
- Алгоритмы кластеризации/разделения:
- Разбиение графа на компоненты/клики, раскраска по блокам, сопоставление с задачей разбиения.
- Двухфазные схемы (практичные):
- Сначала получить раскраску по слотам (игнорируя аудитории), затем упаковать экзамены в аудитории по каждому слоту как задачу bin‑packing (first‑fit decreasing и т.п.).
Точные методы
- Полный перебор с branch-and-bound для раскраски (использует нижние оценки: максимальная клика и жадную раскраску).
- ILP/SAT/CP: формулировки в виде целочисленного программирования или булевой SAT, решаемые CPLEX/Gurobi/OR‑Tools/ SAT‑solvers.
- CSP/CP‑SAT (OR‑Tools) — гибко добавляет побочные ограничения и штрафы.
- Для умеренных размеров (до нескольких сотен экзаменов при хорошей структуре) точные решатели иногда применимы.
Учет дополнительных реальных ограничений
1) Ограниченные аудитории
- Модель с назначением экзамена в конкретную аудиторию:
- Переменные $z_{v,t,r}\in \{0,1\}$ — 1 если экзамен $v$ в слоте $t$ в аудитории $r$.
- Ограничения:
$$\forall v:\sum _{t,r}{z}_{v,t,r}=1,$$ $$\forall r,t:\sum _v{z}_{v,t,r}\le 1(\text{в одной аудитории в один слот не более одного экзамена}),$$ $$\forall v,t,r:z_{v,t,r}=0\text{если}{\text{cap}}_r<siz{e}_v.$$ - Альтернатива (менее детально): сначала раскраска по слотам ($x_{v,t}$), затем для каждого слота решить упаковку экзаменов в аудитории (bin‑packing), или в ILP добавить
$$\forall t:\sum _{v}siz{e}_v\cdot x_{v,t}\le \sum _{r}ca{p}_r.$$ — однако это даёт только суммарную вместимость, не распределение по аудиториям.
2) Временные окна и предопределённые запреты
- Ограничение допустимых слотов: если для экзамена $v$ разрешён набор слотов $W_v$, то
$$\forall t\notin W_v:x_{v,t}=0.$$
3) Предпочтения студентов и мягкие ограничения
- Вводим штрафы/веса и минимизируем суммарную стоимость:
- Переменные штрафа для размещения $p_{v,t}$ (нежелательные слоты) и штрафы за плохие последовательности для студентов, например для студента сдающего $u,v$:
$${\text{penalty}}_{u,v}(t_u,t_v)=w_{u,v}\cdot g(|t_u-t_v|),$$ где $g$ задаёт функцию неудобства (например высокий штраф за подряд или одновременно). При линейной/кусочно‑линейной форме можно линearизовать и добавить в объектив:
$$\min \sum _{v,t}{p}_{v,t}{x}_{v,t}+\sum _{(u,v)}\sum _{t,t^{\prime }}{w}_{u,v,t,t^{\prime }}{y}_{u,v,t,t^{\prime }},$$ где $y_{u,v,t,t^{\prime }}$ — бинарная переменная, равная 1 если $x_{u,t}=x_{v,t^{\prime }}=1$ (линеаризация через стандартные связки).
- Мягкие ограничения даются как штрафы, либо как приоритеты в многоцелевой оптимизации.
Практические рекомендации
- Начинать с двухфазной схемы: жадная/DSATUR раскраска → упаковка по аудиториям → локальный поиск для устранения конфликтов и уменьшения штрафов.
- Для строгих требований к оптимальности применять ILP/CP‑SAT с аккуратной линейризацией и отсечениями (использовать нижние оценки: размер максимальной клики, краевой раскраски).
- Использовать эвристики для больших инстансов: DSATUR + Kempe + tabu/SA + бин‑пак для аудиторий; гибридные подходы обычно дают лучшую практическую производительность.
- Для учета предпочтений и временных окон предпочтительнее CP‑моделирование (легко задавать домены и мягкие ограничения).
Ключевые замечания
- Любое введение реальных ограничений (аудитории, окна, предпочтения) сохраняет NP‑трудность; часто практикуют приближённые и гибридные методы.
- Для оценки качества использовать нижние оценки ($\omega (G)$ — размер максимальной клики) и метрики удобства студентов (число подряд экзаменов, суммарные штрафы).
Если нужно, могу привести конкретную ILP/CP‑формулировку для заданного набора данных (число экзаменов, размеров, аудиторий, временных слотов).