Задачи упаковки и раскроя: проблема рюкзака и метод генерации столбцов
В промышленном производстве — от металлургических заводов до целлюлозно-бумажных комбинатов и швейных фабрик — постоянно возникает одна и та же острая проблема. Имеется исходное сырье в виде стандартных рулонов, листов или стержней фиксированного размера. Поступает заказ на нарезку из этого сырья тысяч мелких деталей различной длины. Как расположить шаблоны деталей на исходном материале так, чтобы количество неиспользуемых обрезков (отходов) было сведено к абсолютному минимуму? В исследовании операций этот класс NP-трудных комбинаторных задач известен как задачи о раскрое и упаковке (Cutting Stock and Bin Packing Problems), и их эффективное решение экономит мировой промышленности миллиарды долларов ежегодно.