Using helical polyhedron for online irregular strip packing problem with free rotations

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.