O'Reilly logo

Optimization Techniques for Solving Complex Problems by Juan Antonio Gomez, Coromoto Leon, Pedro Asasi, Christian Blum, Enrique Alba

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

images 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 wi and a height hi (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, ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required