A Heuristic Approach Based on Shape Similarity for 2D Irregular Cutting Stock Problem - Intelligent Computing for Sustainable Energy and Environment - page 282

Table 1. Results obtained for the 2CS

Name Solution LB Difference(%) Time(s)

FU 72 56 22.222 208.82

JACKOBS1 48 38 26.315 6706.62

JACKOBS2 45 30 50.000 6877.99

SHAPES0 53 30 76.666 26681.03

SHAPES1 54 32 68.750 59581.59

SHAPES2 61 50 22.000 9393.39

DIGHE1 59 32 84.375 232.29

DIGHE2 44 29 51.724 25.07

ALBANO 82 65 26.153 6730.06

DAGLI 56 43 30.232 9284.62

MAO 47 33 42.424 7053.12

MARQUES 51 44 15.909 8278.96

SHIRTS 43 37 16.216 1232468.21

SWIM 58 34 70.588 466799.09

TROUSERS 51 42 21.428 273121.59

5 Conclusion

Cutting and Packing problems exist almost everywhere in real world situation. In this
paper, a novel heuristic approach for two-dimensional irregular cutting stock problem
is presented, based on grid approximation and shape similarity. The approach is
mainly drawn on techniques from computer vision and artificial intelligence and has
shown its capability of finding high-quality solutions. Specifically, the advantages
include the following aspects: firstly, the placement approach based on grid
approximation provides the system designers with an easier way to detect whether
overlap occurs. Secondly, the two-stage placement strategy improves the quality of
packing pattern without compromising the computational effort. Thirdly, the packing
approach based on shape similarity gets higher occupancy rate and better performance
compared with conventional methods. The proposed method is assessed on 15
established benchmark problems and performs very well.

Acknowledgments. The work of this paper was supported by National Natural
Science Foundation of China, No.61074150 and No. 61203178.

References

1. Wäscher, G., Haußner, H., Schumann, H.: An improved typology of cutting and packing
problems. Eur. J. Oper. Res. 183(3), 1109-1130 (2007)
2. Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-
Completeness. W. H. Freeman and Company, New York (1979)
3. Jakobs, S.: On genetic algorithms for the packing of polygons. European Journal of
Operational Research 88(1), 165-181 (1996)