Solving the two-dimensional packing problem with m-M calculus
DOI:
https://doi.org/10.2298/YJOR1101093SKeywords:
Non-linear optimization, m-M calculus, two dimensional packingAbstract
This paper considers the two dimensional rectangular packing problem. The mathematical formulation is based on the optimization of a non-linear function with piecewise linear constraints with a small number of real variables. The presented method of m-M calculus finds all optimal solutions on small instances. Computational performance is good on smaller instances.References
Baldacci, R., Boschetti, M.A. (2007) A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem. European Journal of Operational Research, 183 (3), 1230-1248
Beasley, J.E. (1985) An exact two-dimensional nonguillotine cutting tree search procedure. Operations Research, 33(1): 49-64
Binkley, K., Hagiwara, M. (2007) Applying self-adaptive evolutionary algorithms to two-dimensional packing problems using a four corners heuristic. European Journal of Operational Research, 183(3): 1230-1248
Christofides, N., Hadjiconstantinou, E. (1995) An exact algorithm for orthogonal 2-D cutting problems using guillotine cuts. European Journal of Operational Research, 83(1): 21-38
Cintra, G.F., Miyazawa, F.K., Wakabayashi, Y., Xavier, E.C. (2008) Algorithms for twodimensional cutting stock and strip packing problems using dynamic programming and column generation. European Journal of Operational Research, 191 (1) 59-83
Coffman, E.G., Shor, P.W. (1990) Average-case analysis of cutting and packing in two dimensions. European Journal of Operational Research, 44(2): 134
Coffman, E.G.Jr., Lueker, G.S. (1992) Probabilistic analysis of packing and partitioning algorithms. Chichester: Wiley
Correa, J. (2004) Near-Optimal Solutions to Two-Dimensional Bin Packing With 90 Degree Rotations. Electronic Notes in Discrete Mathematics, 18: 89-95
Diegert, C. (1988) Practical automatic placement for standard-cell integrated circuit. American Journal of Mathematical and Management Sciences, 8 (34) 309-328
Dowsland, K.A., Dowsland, W.B. (1992) Packing problems. European Journal of Operational Research, 56(1): 2-14
Dyckhoff, H., Finke, U. (1992) Cutting and packing in production and distribution. Heidelberg: Physica Verlag
Dyckhoff, H., Scheithauer, G., Terno, J. (1997) Cutting and packing (C&P). u: DellAmico M., Maffioli F., Martello S. [ur.] Annotated bibliographies in combinatorial optimization, Chichester: Wiley, str. 393-413
Epstein, L., Levin, A., Stee, R. (2008) Two-dimensional packing with conflicts. Acta Informatica, 45(3): 155-175
Gonzalves, J.F., Resende, M.G.C. (2010) A parallel multi-population genetic algorithm for a constrained two-dimensional orthogonal packing problem. Journal of Combinatorial Optimization, 1-22 Article in Press
Hadjiconstantinou, E., Christofides, N. An optimal algorithm for general orthogonal 2-D cutting problems. London: Imperial College, Technical report MS-91/2
Harwig, J.M., Barnes, J.W., Moore, J.T. (2006) An adaptive tabu search approach for 2- dimensional orthogonal packing problems. Military Operations Research, 11 (2) 5-26
Hochbaum, D.S., Maass, W. (1985) Approximation schemes for covering and packing problems in image processing and VLSI. J. Assoc. Comput. Mach., 32(1): 130
Kim, J., Moon, B.R. (2009) A hybrid genetic algorithm for a variant of two-dimensional packing problem. u: Annual Genetic and Evolutionary Computation Conference (XI), GECCO, Proceedings, 287-292
Leung, J., Tam, T., Wong, C.S., Young, G., Chin, F. (1990) Packing squares into a square. Journal of Parallel and Distributed Computing, 10(3): 271-275
Lodi, A., Martello, S., Monaci, M. (2002) Two-dimensional packing problems: A survey. European Journal of Operational Research, 141(2): 241-252
Lu, S., Lu, Y., Zha, J., Lu, S. (2009) Cross-entropy method for two-dimensional packing problem with rectangle pieces. Beijing Jiaotong Daxue Xuebao / Journal of Beijing Jiaotong University, 33 (2) 39-43
Ortmann, F.G., Ntene, N., van Vuuren, J.H. (2010) New and improved level heuristics for the rectangular strip packing and variable-sized bin packing problems. European Journal of Operational Research, 203(2): 306-315
Prešić, S.B. (1998) A survey of the m-m calculus. Yugoslav Journal of Operations Research, vol. 8, br. 1, str. 137-168
Savić, A. (2000) Packing and cutting problems. Belgrade: Faculty of Mathematics, Master thesis
Toro, E.M., Garcs, A., Ruiz, H. (2008) Two dimensional packing problem using a hybrid constructive algorithm of variable neighborhood search and simulated annealing. Revista Facultad de Ingenieria, 46, 119-131
Wu, Y.L., Huang, W., Lau, S., Wong, C.K., Young, G.H. (2002) An effective quasi-human based heuristic for solving the rectangle packing problem. European J. Oper. Res., 141(2): 341
Downloads
Published
Issue
Section
License
Copyright (c) YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
