Modelos lineares e não lineares inteiros para problemas da mochila bidimensional restrita a 2 estágios
Linear and nonlinear integer models for constrained two-stage two-dimensional knapsack problems
Yanasse, Horacio Hideki; Morabito, Reinaldo
http://dx.doi.org/10.1590/S0103-65132013005000023
Prod, vol.23, n4, p.887-901, 2013
Resumo
Neste trabalho revemos alguns modelos lineares e não lineares inteiros para gerar padrões de corte bidimensionais guilhotinados de 2 estágios, incluindo os casos exato e não exato e restrito e irrestrito. Esses problemas são casos particulares do problema da mochila bidimensional. Apresentamos também novos modelos para gerar esses padrões de corte, baseados em adaptações ou extensões de modelos para gerar padrões de corte bidimensionais restritos 1-grupo. Padrões 2 estágios aparecem em diferentes processos de corte, como, por exemplo, em indústrias de móveis e de chapas de madeira. Os modelos são úteis para a pesquisa e o desenvolvimento de métodos de solução mais eficientes, explorando estruturas particulares, a decomposição do modelo, relaxações do modelo etc. Eles também são úteis para a avaliação do desempenho de heurísticas, já que permitem (pelo menos para problemas de tamanho moderado) uma estimativa do gap de otimalidade de soluções obtidas por heurísticas. Para ilustrar a aplicação dos modelos, analisamos os resultados de alguns experimentos computacionais com exemplos da literatura e outros gerados aleatoriamente. Os resultados foram produzidos usando um software comercial conhecido e mostram que o esforço computacional necessário para resolver os modelos pode ser bastante diferente.
Palavras-chave
Problemas de corte e empacotamento. Mochila bidimensional. Corte guilhotinado-2 estágios. Modelos lineares e não lineares inteiros. Indústria de móveis
Abstract
In this work we review some linear and nonlinear integer models to generate two stage two-dimensional guillotine cutting patterns, including the constrained, non constrained, exact and non exact cases. These problems are particular cases of the two dimensional knapsack problems. We also present new models to generate these cutting patterns, based on adaptations and extensions of models that generate one-group constrained two dimensional cutting patterns. Two stage patterns arise in different cutting processes like, for instance, in the furniture industry and wooden hardboards. The models are useful for the research and development of more efficient methods, exploring particular structures, the model decomposition, model relaxations etc. They are also useful to evaluate the performance of heuristics, since they allow (at least for problems of moderate sizes) an estimative of the optimality gap of the solutions obtained by heuristics. To illustrate the application of the models we analyze the results of some computational experiments with instances of the literature and other generated randomly. The results were produced using a known commercial software and they show that the necessary computational effort to solve the models can be very different.
Keywords
Cutting and packing problems. Two-dimensional knapsack. Two-stage guillotine cut. Linear and nonlinear integer models. Furniture industry
References
ALEM, D. J.; MORABITO, R. Production planning in furniture settings via robust optimization. Computers & Operations Research, v. 39, n. 2, p. 139-150, 2012. http://dx.doi.org/10.1016/j.cor.2011.02.022
ARENALES, M.; MORABITO, R.; YANASSE, H. (Eds.). Special issue: Cutting and packing problems. Pesquisa Operacional, v. 19, n. 2, p. 107-299, 1999.
BEASLEY, J. Algorithms for unconstrained two-dimensional guillotine cutting. Journal of the Operational Research Society, v. 36, p. 297-306, 1985.
BELOV, G.; SCHEITHAUER, G. A branch-and-bound-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting. European Journal of Operational Research, v. 171, p. 85-106, 2006. http://dx.doi.org/10.1016/j.ejor.2004.08.036
BISCHOFF, E.; WAESCHER, G. (Eds.). Special issue: Cutting and packing. European Journal of Operational Research, v. 84, n. 3, 1995. http://dx.doi.org/10.1016/0377-2217(95)00018-L
CARNIERI, C.; GUILLERMO, A.; GAVINHO, L. Solution procedures for cutting lumber into furniture parts. European Journal of Operational Research, v. 73, p. 495-501, 1994. http://dx.doi.org/10.1016/0377-2217(94)90244-5
CHRISTOFIDES, N.; HADJICONSTANTINOU, E. An exact algorithm for orthogonal 2-D cutting problems using guillotine cuts. European Journal of Operational Research, v. 83, p. 21-38, 1995. http://dx.doi.org/10.1016/0377-2217(93)E0277-5
CHRISTOFIDES, N.; WHITLOCK, C. An algorithm for two-dimensional cutting problems. Operations Research, v. 25, n. 1, p. 30-44, 1977. http://dx.doi.org/10.1287/opre.25.1.30
CINTRA, G. F. et al. Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation. European Journal of Operational Research, v. 191, p. 61-85, 2008. http://dx.doi.org/10.1016/j.ejor.2007.08.007
CUI, Y. An exact algorithm for generating homogeneous T-shape cutting patterns. Computers & Operations Research, v. 32, p. 143-152, 2005. http://dx.doi.org/10.1016/S0305-0548(03)00208-9
DAZA, V. P.; ALVARENGA, A. G.; DIEGO, J. Exact solutions for constrained two-dimensional cutting problems. European Journal of Operational Research, v. 84, p. 633-644, 1995. http://dx.doi.org/10.1016/0377-2217(95)00028-O
DOWSLAND, K.; DOWSLAND, W. Packing problems. European Journal of Operational Research, v. 56, p. 2-14, 1992 http://dx.doi.org/10.1016/0377-2217(92)90288-K
DYCKHOFF, H. A new linear programming approach to the cutting stock problem. Operations Research, v. 29, n. 6, p. 1092-1104, 1981. http://dx.doi.org/10.1287/opre.29.6.1092
DYCKHOFF, H.; FINKE, U. Cutting and packing in production and distribution: Typology and bibliography. Heidelberg: Springler-Verlag Co., 1992. http://dx.doi.org/10.1007/978-3-642-58165-6
DYCKHOFF, H.; SCHEITHAUER, G.; TERNO, J. Cutting and packing. In: AMICO, M.; MAFFIOLI, F.; MARTELLO, S. (Eds.). Annotated bibliographies in combinatorial optimisation. New York: John Wiley & Sons, 1997. p. 393-414.
DYCKHOFF, H.; WAESCHER, G. (Eds.). Special issue: Cutting and packing. European Journal of Operational Research, v. 44, n. 2, 1990.
EURO SPECIAL INTEREST GROUP ON CUTTING AND PACKING - ESICUP. Apdio, 2011. Disponível em:
FARLEY, A. Practical adaptations of the Gilmore-Gomory approach to cutting stock problems. OR Spektrum, v. 10, p. 113-123, 1983. http://dx.doi.org/10.1007/BF01720210
FAYARD, D.; HIFI, M.; ZISSIMOPOULOS, V. An efficient approach for large-scale two-dimensional guillotine cutting stock problems. Journal of the Operational Research Society, v. 49, p. 1270-1277, 1998.
FORONDA, S.; CARINO, H. A heuristic approach to the lumber allocation and manufacturing in hardwood dimension and furniture manufacturing. European Journal of Operational Research, v. 54, p. 151-162, 1991. http://dx.doi.org/10.1016/0377-2217(91)90294-6
GILMORE, P.; GOMORY, R. Multistage cutting stock problems of two and more dimensions. Operations Research, v. 14, p. 94-120, 1965. http://dx.doi.org/10.1287/opre.13.1.94
GRAMANI, M.; FRANÇA, P. The combined cutting stock and lot-sizing problem in industrial processes. European Journal of Operational Research, v. 174, n. 1, p. 509-521, 2006. http://dx.doi.org/10.1016/j.ejor.2004.12.019
GRAMANI, M. C. N. ; FRANÇA, P. M.; ARENALES, M. N. A lagrangean relaxation approach to a coupled lot-sizing and cutting stock problem. International Journal of Production Economics, v. 119, p. 219-227, 2009. http://dx.doi.org/10.1016/j.ijpe.2009.02.011
HARJUNKOSKI, I. et al. Different strategies for solving bilinear integer non-linear programming problems with convex transformations. Computers & Chemical Engineering, v. 21, p. 487-492, 1997.
HIFI, M. The DH/KD algorithm: A hybrid approach for unconstrained two-dimensional cutting problems. European Journal of Operational Research, v. 97, n. 1, p. 41-52, 1997. http://dx.doi.org/10.1016/S0377-2217(96)00060-4
HIFI, M. (Ed.). Special issue on cutting and packing. Studia Informatica Universalis, v. 2, p. 1-161, 2002.
HIFI, M.; ROUCAIROL, C. Approximate and exact algorithms for constrained (un)weighted two-dimensional two-staged cutting stock problems. Journal of Combinatorial Optimization, v. 5, p. 465-494, 2001. http://dx.doi.org/10.1023/A:1011628809603
HINXMAN, A. The trim-loss and assortment problems: A survey. European Journal of Operational Research, v. 5, p. 8-18, 1980. http://dx.doi.org/10.1016/0377-2217(80)90068-5
JOHNSTON, R. E.; SADINLIJA, E. A new model for complete solutions to one-dimensional cutting stock problems. European Journal of Operational Research, v. 153, p. 176-183, 2004. http://dx.doi.org/10.1016/S0377-2217(02)00704-X
KENDALL, G.; DANIELS, K.; BURKE, E. K. Special issue: Cutting, packing, layout and space allocation. Annals of Operations Research, v. 179, n. 1, 2010.
LIROV, Y. (Ed.). Special issue: Cutting stock: Geometric resource allocation. Mathematical and Computer Modelling, v. 16, n. 1, 1992.
LODI, A.; MARTELLO, S.; MONACI, M. Two-dimensional packing problems: a survey. European Journal of Operational Research, v. 141, p. 241-252, 2002. http://dx.doi.org/10.1016/S0377-2217(02)00123-6
LODI, A.; MONACI, M. Integer programming models for 2-staged two-dimensional knapack problems. Mathematical Programming, v. 94, p. 257-278, 2003. http://dx.doi.org/10.1007/s10107-002-0319-9
MACEDO, R.; ALVES, C.; CARVALHO, J. M. V. Arc-flow model for two-dimensional guillotine cutting stock problem. Computers & Operations Research, v. 37, p. 991-1001, 2010. http://dx.doi.org/10.1016/j.cor.2009.08.005
MARTELLO, S. (Ed.). Special issue: Knapsack, packing and cutting, Part I: One-dimensional knapsack problems. INFOR, v. 32, n. 3, 1994a.
MARTELLO, S. (Ed.). Special issue: Knapsack, packing and cutting, Part II: Multidimensional knapsack and cutting stock problems. INFOR, v. 32, n. 4, 1994b.
MORABITO, R.; ARENALES, M. Staged and constrained two-dimensional guillotine cutting problems: An and/or-graph approach. European Journal of Operational Research, v. 94, p. 548-560, 1996. http://dx.doi.org/10.1016/0377-2217(95)00128-X
MORABITO, R.; ARENALES, M. Optimizing the cutting of stock plates in a furniture company. International Journal of Production Research, v. 38, n. 12, p. 2725-2742, 2000. http://dx.doi.org/10.1080/002075400411457
MORABITO, R.; BELLUZZO, L. Optimising the cutting of wood fibre plates in the hardboard industry. European Journal of Operational Research, v. 183, p. 1405-1420, 2007. http://dx.doi.org/10.1016/j.ejor.2005.11.066
MORABITO, R.; GARCIA, V. The cutting stock problem in a hardboard industry: A case study. Computers & Operations Research, v. 25, n. 6, p. 469-485, 1998. http://dx.doi.org/10.1016/S0305-0548(97)00087-7
MORABITO, R.; ARENALES, M. N.; YANASSE, H. H. (Eds.). Special issue on Cutting, packing and related problems. International Transactions in Operations Research, v. 16, n. 6, 2009. http://dx.doi.org/10.1111/j.1475-3995.2009.00739.x
MORABITO, R.; PUREZA, V. A heuristic approach based on dynamic programming and AND/OR-graph search for the constrained two-dimensional guillotine cutting problem. Annals of Operation Research, v. 179, p. 297-315, 2010. http://dx.doi.org/10.1007/s10479-008-0457-4
MUKHACHEVA, E. A. (Ed.). Decision making under conditions of uncertainty: cutting -packing problems. Ufa: The International Scientific Collection, 1997.
OLIVEIRA, J. F.; FERREIRA, J. S. An improved version of Wang's algorithm for two-dimensional cutting problems. European Journal of Operational Research, v. 44, p. 256-266, 1990. http://dx.doi.org/10.1016/0377-2217(90)90361-E
POLDI, K. C.; ARENALES, M. N. Heurísticas para o problema de corte de estoque unidimensional inteiro. Pesquisa Operacional, v. 26, p. 473-492, 2006. http://dx.doi.org/10.1590/S0101-74382006000300003
POLDI, K. C.; ARENALES, M. N. Heuristics for the one-dimensional cutting stock problem with limited multiple stock lengths. Computers & Operations Research, v. 36, p. 2074-2081, 2009. http://dx.doi.org/10.1016/j.cor.2008.07.001
RANGEL, S.; FIGUEIREDO, A. G.; ALTAMIRO, G. O problema de corte de estoque em indústrias de móveis de pequeno e médio portes. Pesquisa Operacional, v. 28, p. 451-472, 2008. http://dx.doi.org/10.1590/S0101-74382008000300004
RIEHME, J.; SCHEITHAUER, G.; TERNO, J. The solution of two-stage guillotine cutting stock problems having extremely varying order demands. European Journal of Operational Research, v. 91, p. 543-552, 1996. http://dx.doi.org/10.1016/0377-2217(95)00200-6
SANTOS, S. G.; ARAUJO, S. A.; RANGEL, M. S. Integrated cutting machine programming and lot sizing in furniture industry. Pesquisa Operacional para o Desenvolvimento, v. 3, p. 249-166, 2011.
SCHEITHAUER, G. On a two-dimensional guillotine cutting problem. In: INTERNATIONAL FEDERATION OF OPERATIONAL RESEARCH SOCIETIES - IFORS, 16., 2002, Edinburgh. Proceedings ... Edinburgh, 2002.
SILVA, E.; ALVELOS, F.; CARVALHO, J. M. V. An integer programming model for two- and three-stage two-dimensional cutting stock problems. European Journal of Operational Research, v. 205, p. 699-708, 2010. http://dx.doi.org/10.1016/j.ejor.2010.01.039
SWEENEY, P.; PATERNOSTER, E. Cutting and packing problems: A categorised, application-oriented research bibliography. Journal of the Operational Research Society, v. 43, p. 691-706, 1992.
VIANNA, A. C. G.; ARENALES, M. N.; GRAMANI, M. C. N. Two-stage and constrained two-dimensional guillotine cutting problems. São Carlos: USP, 2003. p. 1-28. (Notas - Série Computação, n. 69).
VISWANATHAN, K.; BAGCHI, A. Best-first search methods for constrained two-dimensional cutting stock problems. Operations Research, v. 41, n. 4, p. 768-776, 1993. http://dx.doi.org/10.1287/opre.41.4.768
YANASSE, H. H.; KATSURAYAMA, D. M. Checkerboard patterns: proposals for its generation. International Transactions in Operational Research, v. 12, p. 21-45, 2005. http://dx.doi.org/10.1111/j.1475-3995.2005.00488.x
YANASSE, H. H.; ZINOBER, A.; HARRIS, R. Two-dimensional cutting stock with multiple stock sizes. Journal of the Operational Research Society, v. 42, n. 8, p. 673-683. 1991.
YANASSE, H. H.; MORABITO, R. Linear models for one-group two-dimensional guillotine cutting problems. International Journal of Production Research, v. 44, n. 17, p. 3471-3491, 2006. http://dx.doi.org/10.1080/00207540500478603
YANASSE, H. H.; MORABITO, R. A note on linear models for two-group and three-group two-dimensional guillotine cutting problems. International Journal of Production Research, v. 46, n. 21, p. 6189-6206, 2008. http://dx.doi.org/10.1080/00207540601011543
WAESCHER, G.; GAU, T. Heuristics for the integer one-dimensional cutting stock problem: a computational study. OR Specktrum, v. 18, p. 131-144, 1996. http://dx.doi.org/10.1007/BF01539705
WAESCHER, G.; HAUSSNER, H.; SCHUMANN, H. An improved typology of cutting and packing problems. European Journal of Operational Research, v. 183, p. 1109-1130, 2007. http://dx.doi.org/10.1016/j.ejor.2005.12.047
WANG, P. Two algorithms for constrained two-dimensional cutting stock problems. Operations Research, v. 31, p. 573-586, 1983. http://dx.doi.org/10.1287/opre.31.3.573
WANG, P.; WAESCHER, G. (Eds.). Special issue on cutting and packing problems. European Journal of Operational Research, v. 141, p. 239-469, 2002. http://dx.doi.org/10.1016/S0377-2217(02)00122-4
Facebook
Google+
Twitter
LinkedIn
Mendeley
StumbleUpon
CiteULike
Reddit
Email