The packing of irregular pieces is widely applied across various industries including metalworking, woodworking, clothing manufacturing, and leather goods production. Allowing rotation during packing, particularly in scenarios where materials are homogeneous, can yield superior outcomes by reducing material wastage, thus contributing to cost-saving and environmental preservation. This study investigates the online irregular strip packing problem allowing free rotation, inspired by a leather handicraft workshop, where orders arrive infrequently and vary widely in content. The objective is to minimize the sheet length utilized. Most existing literature models irregular strip packing problem with rotation as a nonlinear programming problem, making it challenging to obtain the optimal position and orientation of every single input piece despite advancements in optimization solvers. In this paper, a novel approach is proposed to solve online irregular strip packing problem with rotation. We rotate the input polygon while simultaneously translating it along the z-axis, forming a helix. Thus, the problem of selecting the rotation angle is transformed into determining the z-coordinate of the helix’s cross-section. Subsequently, meshing the helix into a polyhedron allows us to propose a mixed integer linear formulation based on its Minkowski sum with other polygons. To ensure guaranteed optimality, we introduce a branch-and-bound algorithm tailored to the problem. Extensive numerical experiments indicate the effectiveness and competitiveness of our algorithm over state-of-the-art nonlinear formulations for irregular strip packing problem with rotation.

中文翻译：

---

使用螺旋多面体解决自由旋转的在线不规则带材保压问题

不规则件的包装广泛应用于各个行业，包括金属加工、木工、服装制造和皮革制品生产。在包装过程中允许旋转，特别是在材料均匀的情况下，可以通过减少材料浪费来产生卓越的结果，从而有助于节省成本和保护环境。本研究调查了在线不规则条状包装问题，允许自由轮换，灵感来自一个皮革手工艺作坊，那里的订单很少到达，内容差异很大。目标是最大限度地减少使用的板材长度。现有的大多数文献将不规则条带填充问题与旋转建模为非线性规划问题，尽管优化求解器取得了进步，但要获得每个输入件的最佳位置和方向仍然具有挑战性。该文提出了一种解决在线不规则带材旋转保压问题的新方法。我们旋转输入多边形，同时沿 z 轴平移它，形成一个螺旋线。因此，选择旋转角度的问题转变为确定螺旋横截面的 z 坐标。随后，将螺旋线网格划分为多面体，使我们能够根据其与其他多边形的 Minkowski 和提出一个混合整数线性公式。为了确保保证最优性，我们引入了针对该问题量身定制的 branch-and-bound 算法。广泛的数值实验表明，对于旋转的不规则带材保压问题，我们的算法相对于最先进的非线性公式的有效性和竞争力。