Методы решения задач ортогонального раскроя-упаковки, Оксана Корчевская

В один из классов задач комбинаторной оптимизации, достаточно часто встречающийся в реальных производственных условиях, выделены задачи раскроя и упаковки. Их объединяет необходимость установления определенного соответствия между двумя группами, как правило, больших и малых объектов.Эти задачи представляют собой проблему как теоретического, так и практического плана, т.к. относятся к классу NP-трудных задач. Это означает, что не существует алгоритмов полиномиальной сложности для поиска оптимального решения. Из-за значительных затрат вычислительного времени и необходимости учета технологических ограничений для решения подобного класса задач, как правило, используют приближенные методы и эвристики. В работе приведен краткий обзор методов решения задач линейного, прямоугольного и параллелепипедного раскроя-упаковки, описан новый метод решения - метод плоскостей и применен аппарат искусственных нейронных сетей к решению задач раскроя-упаковки.