Алгоритмы и методы решения задач составления расписаний и других экстремальных задач на графах больших размерностей

Рассматривается ориентированный граф $G=(V,E)$ большой размерности, на рёбрах которого задан набор характеристик. В графе выделено подмножество вершин $V'\subset V$, на которые наложены дополнительные условия. В работе приведён алгоритм сведения задачи оптимизации на графе $G$ к задаче оптимизации на графе $G'=(V',E')$ меньшей размерности. Приведены основные этапы решения и методы построения приближённого решения задачи на преобразованном графе $G'$.