Résumé
In this paper we study the Multiple Strip Packing (MSP) problem, a generalization of the well-known Strip Packing problem. For a given set of rectangles, r1, ..., rn, with heights and widths <= 1, the goal is to find a. non-overlapping orthogonal packing without rotations into k is an element of N strips [0,1] x [0, infinity), minimizing the maximum of the heights. We present an approximation algorithm with absolute ratio 2, which is the best possible, unless P = NP, and an improvement of the previous best result with ratio 2+epsilon. Furthermore we present simple shelf-based algorithms with short running-time and an AFPTAS for MSP. Since MSP is strongly NP-hard, an FPTAS is ruled out and an AFPTAS is also the best possible result in the sense of approximation theory.