Mixed integer programming models for the planning of one-dimensional metallic pipe cutting in the aeronautics industry

Abstract

This study aims to optimize the one-dimensional cutting process planning of structural metallic tubes used to build agricultural light aircrafts. Two mixed integer linear programming models are presented to minimize the waste of material cut and considering the possibility of generating surpluses with sizes sufficiently large for reuse (leftovers). The models are solved using a commercial modeling language and an optimization solver. For the validation of the models, two computational experiments were performed with actual data from the portfolio of a light aircraft designed for agricultural purposes, the Ipanema, produced by the Brazilian company Neiva/Embraer. The solutions of the models are compared with the solutions of a constructive heuristic of the literature and the solutions used by the company. The results show that the models are useful for being used in the planning of this cutting process.
Keywords: Planning of pipe cutting process. Mixed integer programming. Aeronautics industry. One-dimensional cutting and packing problems.

Referncia bibliogrficas

ABUABARA, A. Otimizao no corte de tubos estruturais: aplicao na indstria aeronutica agrcola. So Carlos, 2006. Dissertao (Mestrado em Engenharia de Produo), Departamento de Engenharia de Produo, Universidade Federal de So Carlos UFSCar. ALVIM, A. C. F.; RIBEIRO, C. C.; GLOVER, F.; ALOISE, D. J. A hybrid improvement heuristic for the one-dimensional bin
packing problem. Journal of Heuristics, v. 10, n. 2, p.205-229, 2004. ARENALES, M. N.; MORABITO R.; YANASSE, H. H. Cutting and packing problems. Pesquisa Operacional, v. 19, n. 2, p.107-299, 1999. ARMBRUSTER, M. A solution procedure for a pattern sequencing problem as part of a one-dimensional cutting stock problem
in the steel industry. European Journal of Operational Research, v. 141, n. 2, p. 328-340, 2002. BROOKE, A.; KENDRIK, D.; MEERAUS A.; ROSENTHAL R. GAMS: A Users Guide. Washington: GAMS Development Co, 1998. CHERRI, A. C. O problema de corte de estoque com reaproveitamento das sobras de material. So Carlos, 2006. Dissertao (Mestrado em Cincias da Computao e Matemtica Aplicada), Instituto de Cincias e Matemtica Computacional, EESC/USP. CHERRI, A. C.; ARENALES, M. N.; YANASSE, H. H. The one dimensional cutting stock problems with usable leftover: A heuristic approach. European Journal of Operational Research 2008 (doi10.1016/j.ejor.2008.04.039). DYCKHOFF, H. A new linear programming approach to the cutting stock problem. Operations Research, v. 29, n. 6, p.10921104, 1981. ______. A Typology of Cutting and Packing Problems. European Journal of Operational Research, v. 44, n.2, p. 145-159, 1990. DYCKHOFF, H.; ABEL, D.; GAL, T. Trim-loss and related problems. Omega, v.13, p. 59-72, 1985. DYCKHOFF, H.; FINKE U. Cutting and Packing in Production and Distribution: Typology and Bibliography. Heidelberg: Springer-Verlag Co., 1992. GAREY, M.; JOHNSON, D. Computers and Intractability - A Guide to the Theory of NP-Completeness. Nova York: W.H. Freeman and Co.,1979. GILMORE, P.; GOMORY, R. A Linear Programming Approach to the Cutting Stock Problem. Operations Research, v. 9, n. 6, p.849-859, 1961. GILMORE, P.; GOMORY, R. A Linear Programming Approach to the Cutting Stock Problem, part II. Operations Research, v.11, n. 6, p. 94-120, 1963. GRADISAR, M.; JESENKO; J.; RESINOVIC; C. Optimization of roll cutting in clothing industry. Computers & Operational Research, v. 24, n. 10, p. 945-953, 1997. GRADISAR, M.; KLJAJIC, M.; RESINOVIC, C.; JESENKO, J. A sequential heuristic procedure for one-dimentional cutting. European Journal of Journal of Operational Research, v.114, n. 3, p. 557-568, 1999a. GRADISAR, M.; RESINOVIC, C.; KLJAJIC, M. A hybrid approach for optimization of one dimentional cutting. European