Конечный метод поиска глобального минимума задачи размещения прямоугольных объектов

Abstract

Проведено дослідження оптимізаційної задачі розміщення прямокутних об'єктів у смузі, виділено нові властивості математичної моделі задачі та запропоновано модифікацію точного методу розв'язання задачі, заснованого на методі гілок та меж, що дозволяє поліпшити теоретичну та емпіричну оцінки обчислювальної складності алгоритму.We study the optimization rectangular packing problem for a strip. The new properties of a mathematical model of the problem are considered. On this base, a modification of the exact solution method based on the branch-and-bound method, which allows one to improve the theoretical and empirical estimations of the algorithm computing complexity, has been proposed.