Scheduling inspired models for two-dimensional packing problems

We propose two exact algorithms for two-dimensional orthogonal packing problems whose main components are simple mixed-integer linear programming models. Based on the different forms of time representation in scheduling formulations, we extend the concept of multiple time grids into a second dimension and propose a hybrid discrete/continuous-space formulation. By relying on events to continuously locate the rectangles along the strip height, we aim to reduce the size of the resulting mathematical problem when compared to a pure discrete-space model, with hopes of achieving a better computational performance. Through the solution of a set of 29 test instances from the literature, we show that this was mostly accomplished, primarily because the associated search strategy can quickly find good feasible solutions prior to the optimum, which may be very important in real industrial environments. We also provide a comprehensive comparison to seven other conceptually different approaches that have solved the same strip packing problems.

► 1-D concepts for time representation are combined for 2-D packing problems. ► Two MILP models are proposed. ► Hybrid discrete/continuous-space model better than its discrete-space counterpart. ► Both need search algorithms for efficiently finding the global optimum. ► Iterative procedure for hybrid model is over the number of events of the y-axis grid.