Strip packing

1. Background

The following instances of a 2D rectangular packing problem have been used in the paper entitled 
An Empirical Investigation of Meta-heuristic and Heuristic Algorithms for a 2D Packing Problem
 that has been accepted for publication by the European Journal of Operations Research in June 99.

E. Hopper and B. C. H. Turton
Cardiff University, School of Engineering, The Parade, PO Box 689, Cardiff CF2 3TF, UK
tel: 01222-875927
fax: 01222-874716
HopperE@cf.ac.uk, Turton@cf.ac.uk
Abstract 
In this paper we consider the two-dimensional rectangular packing problem, where a fixed set of items have to be allocated 
on a single object. Two heuristics, which belong to the class of packing procedures that preserve bottom-left stability, are 
hybridised with three meta-heuristic algorithms (genetic algorithms, simulated annealing, naïve evolution) and local search 
heuristic (hill-climbing). This study compares the hybrid algorithms in terms of solution quality and computation time on a 
number of packing problems of different size. In order to show the effectiveness of the design of the different algorithms 
their performance is compared to random search and heuristic packing routines.


2. Description the test problems

The test problems used in the paper have been constructed for a 2D packing problem with the following characteristics:

a set of items, which may contain identical items
one single object of fixed width and infinite height
all pieces are of rectangular shape
items can be rotated by 90°
non-guillotineable 

The packing tasks are classified by the problem size, i.e. the number of items. For each category three problems instances 
have been constructed. The dimensions of the items are given below. The problem instances have been constructed such 
that at least one optimum solution for each problem is known.

Seven categories of problems have been constructed ranging from 16 to 197 items. Three instances have been generated for 
each problem category. The problems have been constructed such that the optimal solution is known (see Table 1). 
Concerning the optimum solution some of the layouts are guillotineable and some are non-guillotineable. 

Table 1: Test problems

Concering the seven problem categories (C1 to C7) the following information is stated for each category.
Problem category C*
number of items
optimal height
object dimensions

C1
16 or 17
20
20x20

C2
25
15
40x15

C3
28 or 29
30
60x30

C4
49
60
60x60

C5
73
90
60x90

C6
97
120
80x120

C7
196 or 197
240
160x240



3. Data of the test problems

The first column indicates the height of the rectangle, the second one its width.

Category 1: 
16 or 17 items; optimum object: 20 x 20

Problem 1:
Number of rectangles: 16  

2	12
7	12
8	6
3	6
3	5
5	5
3	12
3	7
5	7
2	6
3	2
4	2
3	4
4	4
9	2
11	2

Problem 2:
Number of rectangles: 17  

4	1
4	5
9	4
3	5
3	9
1	4
5	3
4	1
5	5
7	2
9	3
3	13
2	8
15	4
5	4
10	6
7	2

Problem 3:
Number of rectangles: 16  
4	14
5	2
2	2
9	7
5	5
2	5
7	7
3	5
6	5
3	2
6	2
4	6
6	3
10	3
6	3
10	3


Category 2: 
25 items, object: 40 x 15

Problem 1:
Number of rectangles: 25

11	3
13	3
9	2
7	2
9	3
7	3
11	2
13	2
11	4
13	4
3	5
11	2
2	2
11	3
2	3
5	4
6	4
12	2
1	2
3	5
13	5
12	4
1	4
5	2
6	2

Problem 2:
Number of rectangles: 25

11	2
2	3
10	7
8	4
9	5
7	2
4	1
6	1
4	5
8	3
1	3
5	5
3	1
12	4
6	2
2	4
11	4
10	2
3	2
11	2
3	4
26	4
8	4
3	2
6	2

Problem 3:
Number of rectangles: 25

12	7
7	7
7	1
5	1
3	2
6	2
7	2
5	2
3	1
6	1
12	6
9	6
12	2
7	2
10	3
4	1
5	1
16	3
5	3
4	2
5	2
10	3
9	3
16	3
5	3

 
Category 3: 
28 or 29 items, object: 60 x 30

Problem 1:
Number of rectangles: 28  

7	5
14	5
14	8
4	8
21	13
7	11
14	11
14	5
4	5
18	3
21	3
17	11
4	11
7	4
5	4
6	7
18	5
3	5
7	3
5	3
18	4
3	4
12	2
6	2
18	5
21	5
17	3
4	3

Problem 2:
Number of rectangles: 29  

18	6
12	2
7	10
23	4
1	4
7	7
4	11
5	6
7	2
11	6
19	10
5	11
2	4
5	7
2	4
12	7
13	7
6	3
10	6
16	9
4	1
10	4
24	6
9	9
1	2
5	8
5	3
25	7
21	5

Problem 3:
Number of rectangles: 28  

24	9
8	9
11	9
17	9
24	4
8	4
6	1
5	1
17	4
6	3
5	3
5	12
13	12
14	14
14	2
2	2
3	8
9	8
14	12
2	12
3	6
9	6
5	2
13	2
18	3
14	3
16	3
12	3


Category 4: 
49 items; object: 60 x 60

Problem 1:
Number of rectangles:  49  
2	7
24	7
16	4
18	4
16	7
18	7
2	4
24	4
4	28
6	18
14	12
2	12
18	19
9	8
7	8
9	11
7	11
14	6
2	6
6	10
16	10
3	5
4	5
8	12
3	18
3	3
8	3
5	20
3	17
3	7
5	7
3	7
4	7
4	21
10	19
4	17
8	17
3	10
5	10
7	6
8	6
15	12
3	12
11	10
5	10
4	2
8	2
10	2
12	2

Problem 2:
Number of rectangles:  49  
10	14
3	13
28	5
5	8
14	9
12	14
13	10
3	17
1	5
4	1
18	4
1	1
2	6
4	14
3	18
4	14
8	17
11	5
9	12
4	7
25	8
7	5
24	9
9	14
12	19
2	4
2	7
3	4
5	30
5	3
10	26
6	5
4	9
1	4
9	2
4	17
5	2
4	4
6	2
4	10
2	4
3	12
6	5
3	9
7	18
6	6
18	7
13	9
25	7


Problem 3:
Number of rectangles: 49

10	4
12	4
13	5
3	5
7	22
6	22
9	23
10	19
3	15
5	13
2	10
2	10
13	18
3	18
2	3
2	3
5	2
4	2
3	4
9	4
7	1
6	1
2	4
20	4
4	7
12	7
9	4
4	4
9	9
2	5
20	5
9	5
4	5
4	2
12	2
3	15
21	11
11	3
3	3
11	23
11	23
11	8
3	8
21	4
14	4
3	13
35	13
11	5
11	5


Category 5: 
73 items; object: 60 x 90

Problem 1:
Number of rectangles: 73  
6	34
3	13
5	13
12	10
12	10
7	6
15	6
7	25
15	25
12	21
7	16
5	16
3	21
5	21
7	5
5	5
1	4
10	4
13	6
13	12
9	12
6	23
3	7
5	7
1	2
10	2
6	6
5	6
7	14
6	14
3	16
5	16
6	14
5	14
13	14
2	3
7	3
2	11
7	11
7	6
6	6
14	33
4	12
3	12
18	16
3	12
18	12
4	4
3	4
1	3
2	3
9	6
9	6
1	6
2	6
7	5
18	5
9	3
9	3
18	9
5	6
2	6
12	2
9	2
3	8
9	8
9	10
5	3
2	3
18	3
7	3
3	2
9	2

Problem 2:
Number of rectangles:  73  
3	5
14	3
9	27
6	24
21	7
7	10
1	2
13	19
4	17
4	13
17	3
24	10
5	4
2	2
6	1
11	9
4	26
2	1
4	7
7	38
3	2
3	1
4	2
4	6
2	1
1	2
5	1
1	1
3	3
5	20
6	23
7	2
11	21
8	7
6	15
2	1
13	14
3	14
5	26
9	14
10	3
4	13
1	3
14	11
7	10
14	12
18	3
7	4
2	7
7	28
30	10
14	19
4	26
3	3
5	23
5	20
15	4
10	6
6	3
5	2
4	2
3	1
2	3
14	3
9	2
7	8
32	6
6	2
26	5
1	2
6	5
13	3
10	3

Problem 3:
Number of rectangles: 73  
6	37
10	15
4	7
12	7
4	18
10	8
5	8
4	25
5	25
4	8
12	8
10	10
5	10
3	4
7	4
7	10
2	10
7	15
4	18
15	18
3	18
7	18
7	5
2	5
4	11
5	11
4	5
5	5
1	3
6	3
1	4
6	4
4	2
5	2
19	25
5	9
4	9
3	6
3	6
6	13
20	13
3	18
3	18
5	16
4	16
6	11
13	4
7	4
13	7
3	2
4	2
3	5
4	5
4	24
15	12
13	12
19	7
9	7
5	4
2	4
12	5
9	22
5	1
2	1
15	12
13	12
2	5
5	5
12	17
2	12
5	12
4	5
28	5


Category 6: 
97 items; object: 80 x 120

Problem 1:
Number of rectangles: 97
30	19
8	5
13	5
15	23
9	4
3	4
2	11
9	7
3	7
8	14
11	6
2	6
11	8
2	8
12	12
2	12
30	10
21	10
15	6
14	6
2	9
22	9
6	16
5	2
5	2
11	6
9	30
10	8
10	8
5	4
5	4
4	14
2	14
4	22
8	14
3	14
10	22
4	20
6	20
2	7
13	2
9	2
13	5
9	5
17	11
7	11
6	18
4	8
2	8
5	7
3	7
3	14
17	7
7	7
5	7
3	7
6	6
4	6
4	2
6	2
9	61
6	8
5	8
5	2
4	2
5	28
4	28
6	29
3	20
21	20
10	39
4	13
7	13
6	22
5	22
4	26
7	26
3	9
21	9
11	31
9	31
6	28
3	19
18	8
3	8
18	11
3	11
10	18
2	6
9	6
2	12
9	12
3	9
12	2
9	2
12	7
9	7

Problem 2:
Number of rectangles: 97
7	39
8	33
7	6
5	3
3	5
39	6
11	13
3	4
2	2
5	2
5	30
2	1
26	11
4	5
9	2
10	29
4	3
5	5
8	2
24	4
22	7
2	9
2	2
5	1
9	15
10	33
1	1
4	4
3	3
4	4
3	6
16	7
6	4
6	2
15	3
30	5
1	1
10	4
2	6
6	23
29	8
26	5
9	17
7	3
19	9
36	6
28	6
6	20
20	7
11	2
6	5
5	13
4	14
16	8
23	9
26	8
1	6
15	26
4	25
8	45
11	50
19	5
12	55
5	20
4	13
15	5
2	6
4	26
12	6
3	1
2	3
3	2
1	1
2	3
3	2
5	2
4	4
8	2
9	11
3	2
5	11
7	9
24	30
2	11
10	8
9	2
10	2
3	11
4	22
6	9
3	3
7	18
5	15
9	13
2	10
6	5
17	5

Problem 3:
Number of rectangles: 97
6	35
1	6
6	6
34	13
10	7
23	7
1	7
6	7
10	62
10	33
13	33
7	22
4	15
6	8
24	8
6	7
24	7
4	7
30	7
6	34
8	17
10	17
8	16
15	16
5	6
5	6
9	21
4	21
5	23
5	23
8	6
15	6
8	5
10	5
5	4
7	2
6	2
6	4
17	4
7	2
6	2
5	8
4	4
9	4
6	8
17	8
4	6
5	6
4	8
4	4
9	4
4	2
5	2
4	25
6	25
6	6
2	6
18	10
11	24
9	4
17	4
7	9
9	5
17	5
6	4
2	4
6	8
20	8
7	42
8	14
18	14
6	34
5	9
8	7
7	7
26	20
5	7
3	7
3	15
8	2
7	2
4	19
6	19
5	25
8	13
7	13
5	8
3	8
8	5
3	5
6	8
2	8
7	12
10	7
37	7
6	4
2	4


Category 7: 
196 or 197 items; object: 160 x 240

Problem 1:
Number of rectangles: 196
19	21
6	21
6	18
41	18
22	14
13	14
8	13
14	13
31	20
8	7
14	7
22	54
13	54
6	23
8	13
33	13
6	22
5	22
11	28
19	56
12	56
16	11
3	11
6	20
8	10
33	10
16	9
3	9
8	4
17	4
20	9
19	9
8	15
6	6
5	6
3	6
5	6
17	23
5	28
6	28
11	53
20	6
19	6
3	17
5	17
39	12
8	12
31	8
41	8
23	23
12	23
9	9
16	9
6	18
20	13
21	13
5	25
6	25
19	25
7	16
5	16
9	9
16	9
20	12
21	12
23	10
12	10
7	9
5	9
25	7
6	7
16	47
16	14
8	14
21	16
2	4
4	4
11	11
29	11
10	54
13	54
13	70
7	13
3	13
7	25
2	12
4	12
11	32
22	9
7	9
7	12
3	12
16	33
8	33
14	21
7	21
6	27
6	10
16	10
7	23
10	45
7	45
2	10
4	10
16	13
14	6
7	6
2	3
4	3
13	13
14	13
7	8
33	8
16	34
12	28
12	28
7	30
4	19
29	19
10	51
13	51
13	25
4	21
10	21
4	11
29	11
9	26
4	26
17	35
12	6
12	6
4	4
10	4
8	10
13	2
6	2
10	12
3	12
22	16
18	16
7	20
17	16
3	16
13	8
6	8
8	10
19	10
10	8
3	8
9	9
4	9
22	14
9	7
9	7
17	4
3	4
19	17
8	17
8	11
5	11
7	10
20	10
9	7
9	7
19	20
4	20
4	10
26	10
19	11
21	11
3	3
6	3
18	13
8	27
5	27
3	10
6	10
4	24
5	21
21	21
19	21
8	21
19	17
21	17
9	15
5	6
13	6
19	14
4	14
5	9
4	7
9	7
5	3
21	3
4	2
9	2

Problem 2:
Number of rectangles: 197
15	75
12	80
27	6
3	13
10	3
9	21
8	11
6	13
2	9
51	10
6	6
11	12
2	10
8	12
13	47
14	37
3	11
3	6
1	4
1	6
27	5
14	3
10	4
5	20
3	11
14	5
5	2
7	2
12	9
2	1
12	8
5	28
8	6
35	7
7	14
10	45
4	19
13	17
62	9
36	11
38	18
4	2
9	5
8	3
30	20
6	7
36	10
27	7
17	3
6	4
11	10
5	25
7	26
10	44
19	4
8	31
33	6
11	73
8	27
6	2
2	9
25	9
9	39
9	17
12	7
21	101
3	10
3	7
4	10
8	22
5	3
2	1
1	2
22	59
1	2
1	1
2	1
11	56
10	39
5	5
3	20
2	1
2	7
7	6
13	12
17	34
16	46
1	1
6	13
3	12
6	10
9	15
6	24
1	1
5	7
4	1
2	13
11	9
1	6
3	16
7	11
8	15
6	10
6	21
3	9
1	4
10	7
3	3
5	15
2	4
33	8
16	5
9	12
10	11
6	3
10	11
39	8
17	113
13	36
28	8
17	7
42	9
22	57
2	1
15	9
30	8
26	7
16	32
71	25
12	25
22	20
9	55
13	27
65	16
1	3
5	2
16	57
2	1
3	3
3	2
25	11
11	8
6	4
10	9
25	8
10	6
12	15
6	19
2	4
4	7
4	2
6	7
13	3
29	5
2	2
8	15
5	28
8	42
4	27
3	2
18	4
17	5
2	8
2	11
1	2
3	18
17	10
7	5
3	10
5	31
19	9
7	8
10	3
11	37
1	4
6	32
1	5
12	5
7	33
2	8
6	11
9	9
4	27
10	11
38	9
5	7
6	2
3	6
6	2
32	5
12	4
16	3
72	15
14	14
2	6
3	9
12	3

Problem 3:
Number of rectangles: 196  
19	15
4	15
8	5
26	5
21	10
5	24
3	7
32	7
26	92
16	92
8	5
26	5
3	17
32	17
10	5
24	5
2	8
19	8
3	7
3	7
13	10
4	27
10	14
24	14
2	11
19	11
3	3
3	3
5	5
35	5
6	17
13	17
24	8
31	8
5	8
35	8
24	5
31	5
5	5
35	5
11	44
12	44
38	17
57	17
13	5
17	5
8	17
36	20
21	20
13	12
17	12
5	15
10	6
15	6
8	50
30	16
6	16
15	10
6	10
10	9
15	9
6	8
5	8
12	40
9	33
6	33
6	37
5	35
21	13
4	13
4	17
22	17
16	34
6	32
5	32
14	23
16	23
6	31
21	22
4	22
4	17
22	17
14	8
16	8
9	4
6	4
20	4
22	4
5	29
38	7
33	7
7	32
5	32
30	49
5	22
9	22
6	37
6	31
16	31
2	7
25	7
11	12
33	22
2	5
25	5
27	10
11	10
5	15
9	15
5	30
11	13
30	13
30	21
7	17
5	17
6	24
6	22
10	22
3	2
3	2
8	10
6	18
11	8
30	8
3	8
3	8
12	65
5	5
16	5
6	9
3	9
41	9
17	3
13	3
6	8
8	8
17	6
13	6
5	11
16	11
6	2
10	2
6	7
3	7
8	10
14	3
12	3
3	3
5	3
10	26
4	10
47	10
3	11
12	11
14	7
12	7
3	18
5	18
12	10
9	10
9	49
5	7
3	7
26	11
4	8
47	8
3	7
12	7
12	39
9	39
5	4
3	4
51	8
15	8
7	4
2	4
25	11
8	34
7	7
2	7
10	29
2	10
5	10
59	19
9	23
22	15
3	15
2	9
4	7
1	7
4	2
1	2
7	10
59	10
22	8
3	8