A One-Pass Heuristic for Nesting Problems

• Autorzy: Igor Kierkosz , Maciej Łuczak
• Języki publikacji: EN

Abstrakty

EN

A two-dimensional cutting (packing) problem with items of irregular shape and rectangular sheets is studied. Three types of problems are considered: single-sheet problems without restrictions on the number of elements, single-sheet problems with restrictions on the number of elements, and cutting stock problems (restricted number of items and unrestricted number of sheets). The aim of the optimization is to maximize the total area of the elements cut from a single plate or to minimize the number of sheets used in cutting. A one-pass algorithm is proposed which uses the popular concept of a no-fit polygon (NFP). The decision on whether an item is cut from a sheet in a given step depends on the value of a fitting function. The fitting function depends on the change in the NFP of individual items. We test eight different criteria for the evaluation of partial solutions. On the basis of numerical experiments, the algorithm that generates the best solution for each of the considered problem types is selected. The calculation results for these algorithms are compared with results obtained by other authors. (original abstract)

Słowa kluczowe

EN

Algorithms

PL

Algorytmy

• Czasopismo: Operations Research and Decisions
• Rocznik: 2019
• Tom: 29
• Numer: nr 1
• Strony: 37--60

Twórcy

autor

Igor Kierkosz

• Koszalin University of Technology, Koszalin, Poland

autor

Maciej Łuczak

• Koszalin University of Technology, Koszalin, Poland

Bibliografia

• [1] ABEYSOORIYA R.P., BENNELL J.A., MARTINEZ-SYKORA A., Jostle heuristics for the 2D-irregular shapes bin packing problems with free rotation, Int. J. Prod. Econ., 2018, 195, 12-26.
• [2] ADAMOWICZ M., ALBANO A., Nesting two-dimensional shapes in rectangular modules, Comp. Aid. Des., 1976, 8 (1), 27-33.
• [3] ALVAREZ-VALDES R., PARREÑO F., TAMARIT J.M., A Tabu Search algorithm for two-dimensional nonguillotine cutting problems, Eur. J. Oper. Res., 2007, 183, 1167-1182.
• [4] ALVAREZ-VALDES R., MARTINEZ A., TAMARIT J.M., A branch and bound algorithm for cutting and packing irregularly shaped pieces, Int. J. Prod. Econ., 2013, 145 (2), 463-477.
• [5] ART Jr. R.C., An approach to the two-dimensional irregular cutting stock problem, Technical Report 36.Y08, 1966, IBM Cambridge Centre.
• [6] BEASLEY J.E., An exact two-dimensional non-guillotine cutting tree search procedure, Oper. Res., 1985, 33, 49-64.
• [7] BENNELL J.A., DOWSLAND K.A., A tabu thresholding implementation for the irregular stock cutting problem, Int. J. Prod. Res., 1999, 37 (18), 4259-4275.
• [8] BENNELL J.A., DOWSLAND K.A., Hybridising tabu search with optimisation techniques for irregular stock cutting, Manage. Sci., 2001, 47 (8), 1160-1172.
• [9] BENNELL J.A., OLIVEIRA J.F., The geometry of nesting problems. A tutorial, Eur. J. Oper. Res., 2008, 184, 397-415.
• [10] BENNELL J.A., SONG X., A comprehensive and robust procedure for obtaining the nofit polygon using Minkowski sums, Comput. Oper. Res., 2008, 35, 267-281.
• [11] BENNELL J.A., SCHEITHAUER G., STOYAN Y., ROMANOVA T., Tools of mathematical modeling of arbitrary object packing problems, Ann. Oper. Res., 2010, 179, 343-368.
• [12] BŁAŻEWICZ J., HAWRYLUK P., WALKOWIAK R., Using a tabu search approach for solving the twodimensional irregular cutting problem, Ann. Oper. Res., 1993, 41, 313-325.
• [13] BURKE E.K., HELLIER R.S.R., KENDALL G., WHITWELL G., Complete and robust no-fit polygon generation for the irregular stock cutting problem, Eur. J. Oper. Res., 2007, 179, 27-49.
• [14] CAPRARA A., MONACI M., On the two-dimensional knapsack problem, Oper. Res. Lett., 2004, 32, 5-14.
• [15] CHERRI L.H., MUNDIM L.R., ANDRETTA M., TOLEDO F.M.B., OLIVEIRA J.F., CARRAVILLA M.A., Robust mixed-integer linear programming models for the irregular strip packing problem, Eur. J. Oper. Res., 2016, 253 (3), 570-583.
• [16] CLAUTIAUX F., CARLIER J., MOUKRIM A., A new exact method for the two-dimensional orthogonal packing problem, Eur. J. Oper. Res., 2007, 183 (3), 1196-1211.
• [17] DALALAH D., KHRAIS S., BATAINEH K., Waste minimization in irregular stock cutting, J. Manuf. Syst., 2014, 33, 27-40.
• [18] DEL VALLE A.M., DE QUEIROZ T.A., MIYAZAWA F.K., XAVIER E.C., Heuristics for two-dimensional knapsack and cutting stock problems with items of irregular shape, Expert Syst. Appl., 2012, 39 (16), 12589-12598.
• [19] ELKERAN A., A new approach for sheet nesting problem using guided cuckoo search and pairwise clustering, Eur. J. Oper. Res., 2013, 231, 757-769.
• [20] FEKETE S.P., SCHEPERS J., A new exact algorithm for general orthogonal d-dimensional knapsack problems, Lect. Notes Comput. Sci., 1997, 1284, 144-156.
• [21] FERREIRA J.C., ALVES J.C., ALBUQUERQUE C., OLIVEIRA J.F., FERREIRA J.S., MATOS J.S., A flexible custom computing machine for nesting problems, Proc. 13th DCIS, Madrid, Spain, 1998.
• [22] FISCHETTI M., LUZZI I., Mixed-integer programming models for nesting problems, J. Heur., 2009, 15, 201-226.
• [23] GILMORE P.C., GOMORY R.E., The theory and computation of knapsack functions, Oper. Res., 1966, 14 (6), 1045-1074.
• [24] GOMES A.M., OLIVEIRA J.F., A 2-exchange heuristic for nesting problems, Eur. J. Oper. Res., 2002, 141 (2), 359-370.
• [25] GOMES A.M., OLIVEIRA J.F., Solving irregular strip packing problems by hybridising simulated annealing and linear programming, Eur. J. Oper. Res., 2006, 171 (3), 811-829.
• [26] GONÇALVES J.F., A hybrid genetic algorithm-heuristic for a two-dimensional orthogonal packing problem, Eur. J. Oper. Res., 2007, 183, 1212-1229.
• [27] HADJICONSTANTINOU E., CHRISTOFIDES N., An exact algorithm for general, orthogonal, two-dimensional knapsack problems, Eur. J. Oper. Res., 1995, 83, 39-56.
• [28] HADJICONSTANTINOU E., IORI M., A hybrid genetic algorithm for the two-dimensional single large object placement problem, Eur. J. Oper. Res., 2007, 183, 1150-1166.
• [29] JONES D.R., A fully general, exact algorithm for nesting irregular shapes, J. Global Optim., 2014, 59, 367-404.
• [30] KIERKOSZ I., ŁUCZAK M., A hybrid evolutionary algorithm for the two-dimensional packing problem, Cent. Eur. J. Oper. Res., 2014, 22 (4), 729-753.
• [31] LEAO A.A.S., TOLEDO F.M.B., OLIVEIRA J.F., CARRAVILLA M.A., A semi-continuous MIP model for the irregular strip packing problem, Int. J. Prod. Res., 2016, 54 (3), 712-721.
• [32] LEUNG T.W., CHAN C.K., TROUTT M.D., Application of a mixed simulated annealing-genetic algorithm heuristic for the two-dimensional orthogonal packing problem, Eur. J. Oper. Res., 2003, 145 (3), 530-542.
• [33] LÓPEZ-CAMACHO E., OCHOA G., TERASHIMA-MARIN H., BURKE E.K., An effective heuristic for the two-dimensional irregular bin packing problem, Ann. Oper. Res., 2013, 206, 241-264.
• [34] LÓPEZ-CAMACHO E., TERASHIMA-MARIN H., ROSS P., OCHOA G., A unified hyper-heuristic framework for solving packing problems, Expert Syst. Appl., 2014, 41 (15), 6876-6889.
• [35] MARTINEZ-SYKORA A., ALVAREZ-VALDES R., BENNELL J.A., RUIZ R., TAMARIT J.M., Matheuristics for the irregular bin packing problem with free rotations, Eur. J. Oper. Res., 2017, 258 (2), 440-455.
• [36] MARTINS T.C., TSUZUKI M.S.G., Simulated annealing applied to the irregular rotational placement of shapes over containers with fixed dimensions, Exp. Syst. Appl., 2010, 37 (3), 1955-1972.
• [37] MUNDIM L.R., ANDRETTA M., CARRAVILLA M.A., OLIVEIRA J.F., A general heuristic for two-dimensional nesting problems with limited-size containers, Int. J. Prod. Res., 2018, 56 (1-2), 709-732.
• [38] OLIVEIRA J., FERREIRA J., Algorithms for nesting problems. Applied simulated annealing, [in:] R. Vidal (Ed.), Lecture Notes in Economics and Maths Systems, Vol. 396, Springer-Verlag, 1993, 255-274.
• [39] OLIVEIRA J.F., GOMES A.M., FERREIRA J.S., TOPOS. A new constructive algorithm for nesting problems, OR Spektrum, Vol. 22, Springer-Verlag, 2000, 263-284.
• [40] PREPARATA F.P., SHAMOS M.I., Computational geometry. An introduction, Springer-Verlag, 1985.
• [41] RAMESH BABU A., RAMESH BABU N., A generic approach for nesting of 2-d parts in 2-d sheets using genetic and heuristic algorithms, Comp.-Aided Des., 2001, 33, 879-891.
• [42] ROCHA P., RODRIGUES R., GOMES A.M., TOLEDO F.M.B., ANDRETTA M., Circle covering representation for nesting problems with continuous rotations, Proc 19th IFAC World Congress, 2014, 5235-5240.
• [43] SONG X., BENNELL J.A., Column generation and sequential heuristic procedure for solving an irregular shape cutting stock problem, J. Oper. Res. Soc., 2014, 65 (7), 1037-1052.
• [44] STOYAN Y., TERNO J., SCHEITHAUER G., GIL N., ROMANOVA T., Phi-functions for primary 2d-objects, Studia Inf. Univ., 2001, 2, 1-32.
• [45] TERASHIMA-MARÍN H., ROSS P., FARÍAS-ZÁRATE C.J., LÓPEZ-CAMACHO E., VALENZUELA-RENDÓN M., Generalized hyper-heuristics for solving 2d regular and irregular packing problems, Ann. Oper. Res., 2010, 179, 369-392.
• [46] TOLEDO F.M., CARRAVILLA M.A., RIBEIRO C., OLIVEIRA J.F., GOMES A.M., The dotted-board model. A new MIP model for nesting irregular shapes, Int. J. Prod. Econ., 2013, 145 (2), 478-487.
• [47] WÄSCHER G., HAUSSNER H., SCHUMANN H., An improved typology of cutting and packing problems, Eur. J. Oper. Res., 2007, 183 (3), 1109-1130.
• [48] YANG Q., No fit polygon for nesting problem solving with hybridizing ant algorithms, J. Softw. Eng. Appl., 2014, 7 (5), 433-439.

Identyfikatory

DOI

10.5277/ord190103