Иcпользование метрических пространств в оптимальном календарном планировании

Решение оптимальной задачи календарного планирования с $n$ деталями и $m$ станками представляет собой оптимальное расписание запуска деталей на станки. Последнее в свою очередь определяется оптимальным набором $m$ перестановок из $n$ объектов, т.е. вектор-перестановкой $\pi=(\pi_{1},\dots,\pi_{m})$, где каждая перестановка $\pi_{i}$ $(1\leq i\leq m)$ указывает последовательность обработки всех деталей на $i$-м станке. При этом каждому допустимому календарному расписанию должна быть поставлена в соответствие целочисленная точка из $m$-мерного эвклидова пространства перестановок (либо, что практически то же самое, перестановка из чисел $\{1,2,\dots,mn\}$). В целях поиска оптимального календарного расписания иcпользуется понятие метрического пространства в множестве допустимых расписаний и обоснованная методология поиска оптимального расписания. Описываются и анализируются несколько метрических пространств и исследуется их сравнительная эффективность для решения разномаршрутной задачи календарного планирования.

Статья представлена к публикации членом редколлегии: В. А. Лотоцкий