×
Beasley, J. E.

A population heuristic for constrained two-dimensional non-guillotine cutting. (English) Zbl 1056.90011

Eur. J. Oper. Res. 156, No. 3, 601-627 (2004).
Summary: We present a heuristic algorithm for the constrained two-dimensional non-guillotine cutting problem. This is the problem of cutting a number of rectangular pieces from a single large rectangle so as to maximise the value of the pieces cut. In addition the number of pieces of each type that are cut must lie within prescribed limits. Our heuristic algorithm is a population heuristic, where a population of solutions to the problem are progressively evolved. This heuristic is based on a new, non-linear, formulation of the problem. Computational results are presented for a number of standard test problems taken from the literature and for a number of large randomly generated problems.

Cited in 31 Documents

MSC:

90B10 Deterministic network models in operations research
90C59 Approximation methods and heuristics in mathematical programming

Keywords:

Constrained two-dimensional non-guillotine cutting; Population heuristic

Software:

OR-Library
PDF BibTeX XML Cite
\textit{J. E. Beasley}, Eur. J. Oper. Res. 156, No. 3, 601--627 (2004; Zbl 1056.90011)
Full Text: DOI

References:

[3] Arenales, M.; Morabito, R., An AND/OR-graph approach to the solution of two-dimensional non-guillotine cutting problems, European Journal of Operational Research, 84, 599-617 (1995) · Zbl 0928.90074
[4] (Bäck, T.; Fogel, D. B.; Michalewicz, Z., Handbook of Evolutionary Computation (1997), Oxford University Press) · Zbl 0883.68001
[5] Beasley, J. E., An exact two-dimensional non-guillotine cutting tree search procedure, Operations Research, 33, 49-64 (1985) · Zbl 0569.90038
[6] Beasley, J. E., OR-Library: Distributing test problems by electronic mail, Journal of the Operational Research Society, 41, 1069-1072 (1990)
[7] Beasley, J. E., Obtaining test problems via Internet, Journal of Global Optimization, 8, 429-433 (1996) · Zbl 0848.90126
[8] Beasley, J. E., Population heuristics, (Pardalos, P. M.; Resende, M. G.C., Handbook of Applied Optimization (2002), Oxford University Press), 138-157
[9] Beasley, J. E.; Chu, P. C., A genetic algorithm for the set covering problem, European Journal of Operational Research, 94, 392-404 (1996) · Zbl 0953.90565
[10] Beasley, J. E.; Meade, N.; Chang, T.-J., An evolutionary heuristic for the index tracking problem, European Journal of Operational Research, 148, 3, 621-643 (2003) · Zbl 1037.90038
[11] Beasley, J. E.; Sonander, J.; Havelock, P., Scheduling aircraft landings at London Heathrow using a population heuristic, Journal of the Operational Research Society, 52, 483-493 (2001) · Zbl 1088.90514
[12] Chang, T.-J.; Meade, N.; Beasley, J. E.; Sharaiha, Y. M., Heuristics for cardinality constrained portfolio optimisation, Computers and Operations Research, 27, 1271-1302 (2000) · Zbl 1032.91074
[13] Chazelle, B., The bottom-left bin-packing heuristic: An efficient implementation, IEEE Transactions on Computers C, 32, 697-707 (1983) · Zbl 0526.68065
[15] Christofides, N.; Whitlock, C., An algorithm for two-dimensional cutting problems, Operations Research, 25, 30-44 (1977) · Zbl 0369.90059
[16] Chu, P. C.; Beasley, J. E., A genetic algorithm for the generalised assignment problem, Computers and Operations Research, 24, 17-23 (1997) · Zbl 0881.90070
[17] Chu, P. C.; Beasley, J. E., A genetic algorithm for the multidimensional knapsack problem, Journal of Heuristics, 4, 63-86 (1998) · Zbl 0913.90218
[18] Chu, P. C.; Beasley, J. E., Constraint handling in genetic algorithms: The set partitioning problem, Journal of Heuristics, 4, 323-357 (1998) · Zbl 1071.90573
[20] Dowsland, K. A.; Dowsland, W. B., Packing problems, European Journal of Operational Research, 56, 2-14 (1992) · Zbl 0825.90355
[21] Dyckhoff, H., A typology of cutting and packing problems, European Journal of Operational Research, 44, 145-159 (1990) · Zbl 0684.90076
[22] Fekete, S. P.; Schepers, J., A new exact algorithm for general orthogonal d-dimensional knapsack problems, Springer Lecture Notes in Computer Science, 1284, 144-156 (1997) · Zbl 1482.90182
[24] Hadjiconstantinou, E.; Christofides, N., An exact algorithm for general, orthogonal, two-dimensional knapsack problems, European Journal of Operational Research, 83, 39-56 (1995) · Zbl 0903.90124
[25] Haessler, R. W.; Sweeney, P. E., Cutting stock problems and solution procedures, European Journal of Operational Research, 54, 141-150 (1991) · Zbl 0736.90062
[26] Healy, P.; Creavin, M.; Kuusik, A., An optimal algorithm for rectangle placement, Operations Research Letters, 24, 73-80 (1999) · Zbl 0956.90034
[27] Holland, J. H., Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence (1975), University of Michigan Press · Zbl 0317.68006
[28] Jakobs, S., On genetic algorithms for the packing of polygons, European Journal of Operational Research, 88, 165-181 (1996) · Zbl 0913.90229
[29] Lai, K. K.; Chan, J. W.M., Developing a simulated annealing algorithm for the cutting stock problem, Computers and Industrial Engineering, 32, 115-127 (1997)
[30] Lai, K. K.; Chan, W. M., An evolutionary algorithm for the rectangular cutting stock problem, International Journal of Industrial Engineering, 4, 130-139 (1997)
[31] Leung, T. W.; Yung, C. H.; Troutt, M. D., Applications of genetic search and simulated annealing to the two-dimensional non-guillotine cutting stock problem, Computers and Industrial Engineering, 40, 201-214 (2001)
[32] Mitchell, M., An Introduction to Genetic Algorithms (1996), MIT Press
[33] Reeves, C. R., Genetic algorithms, (Reeves, C. R., Modern Heuristic Techniques for Combinatorial Problems (1993), Blackwell Scientific Publications: Blackwell Scientific Publications Oxford), 151-196
[34] Reeves, C. R., Genetic algorithms for the operations researcher, INFORMS Journal on Computing, 9, 231-250 (1997) · Zbl 0893.90145
[35] Scheithauer, G.; Terno, J., Modeling of packing problems, Optimization, 28, 63-84 (1993) · Zbl 0818.90083
[36] Sweeney, P. E.; Paternoster, E. R., Cutting and packing problems: A categorized, application-orientated research bibliography, Journal of the Operational Research Society, 43, 691-706 (1992) · Zbl 0757.90055
[37] Tsai, R. D.; Malstrom, E. M.; Meeks, H. D., A two-dimensional palletizing procedure for warehouse loading operations, IIE Transactions, 20, 418-425 (1988)
[38] Wang, P. Y., Two algorithms for constrained two-dimensional cutting stock problems, Operations Research, 31, 573-586 (1983) · Zbl 0517.90093
[39] Wu, Y.-L.; Huang, W.; Lau, S.-C.; Wong, C. K.; Young, G. H., An effective quasi-human based heuristic for solving the rectangle packing problem, European Journal of Operational Research, 141, 341-358 (2002) · Zbl 1081.90615
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.