A two-stage intelligent search algorithm for the two-dimensional strip packing problem

Publication year: 2011
Source: European Journal of Operational Research, In Press, Accepted Manuscript, Available online 13 June 2011

Stephen C.H., Leung , Defu, Zhang , Kwang Mong, Sim

This paper presents a two-stage intelligent search algorithm for a two-dimensional strip packing problem without guillotine constraint. In the first stage, a heuristic algorithm is proposed, which is based on a simple scoring rule that selects one rectangle from all rectangles to be packed, for a given space. In the second stage, a local search and a simulated annealing algorithm are combined to improve solutions of the problem. In particular, a multi-start strategy is designed to enhance the search capability of the simulated annealing algorithm. Extensive computational experiments on a wide range of benchmark problems from zero-waste to non-zero-waste instances…

 Highlights: ► This paper presents a two-stage intelligent search algorithm for a two-dimensional strip packing problem without guillotine constraint. ► a heuristic algorithm based on a simple scoring rule is proposed. ► a local search and a simulated annealing algorithm are combined to improve solutions of the problem. ► a multi-start strategy is designed to enhance the search.