Optimization Techniques for Solving Complex Problems

CHAPTER 22

Greedy Seeding and Problem-Specific Operators for GAs Solution of Strip Packing Problems

C. SALTO

Universidad Nacional de La Pampa, Argentina

J. M. MOLINA and E. ALBA

Universidad de Málaga, Spain

22.1 INTRODUCTION

The two-dimensional strip packing problem (2SPP) is present in many real-world applications in the glass, paper, textile, and other industries, with some variations on its basic formulation. Typically, the 2SPP consists of a set of M rectangular pieces, each defined by a width w_i and a height h_i (i = 1, …, M), which have to be packed in a larger rectangle, the strip, with a fixed width W and unlimited length. The objective is to find a layout of all the pieces in the strip that minimizes the required strip length, taking into account that the pieces have to be packed with their sides parallel to the sides of the strip, without overlapping. This problem is NP-hard [11].

In the present study some additional constrains are imposed: pieces must not be rotated and they have to be packed into three-stage level packing patterns. In these patterns, pieces are packed by horizontal levels (parallel to the bottom of the strip). Inside each level, pieces are packed bottom-left-justified, and when there is enough room in the level, pieces with the same width are stacked one above the other. Three-stage level patterns are used in many real applications in the glass, wood, ...