Обновленная нижняя граница для задачи упаковки прямоугольников в полубесконечную полосу

V. M. Kartak

Обновленная нижняя граница для задачи упаковки прямоугольников в полубесконечную полосу

Authors

V. M. Kartak

Keywords:

Метод ветвей и границ; раскрой-упаковка; нижняя граница

Abstract

Рассматривается задача упаковки прямоугольников в полубесконечную полосу (two-dimensional strip packing problem, 2DSPP), которая имеет широкое применение в промышленности. Она является NP-трудной. Рассматриваются алгоритмы расчета нижней границы, базирующиеся на ее матричном представлении и линейном программировании.