A Simulated Annealing Enhancement of the Best-Fit Heuristic for the Orthogonal Stock-Cutting Problem

References

• Baker B. S., Coffman E. G., Rivest R. L. Orthogonal packing in two dimensions. SIAM J. Comput. (1980) 9(4):846–855Crossref, Google Scholar
• Belov G., Scheithauer G. A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting. Eur. J. Oper. Res. (2006) 171(1):85–106Crossref, Google Scholar
• Bennell J. A., Song X. A comprehensive and robust procedure for obtaining the no-fit polygon using Minkowski sums. Comput. Oper. Res. (2008) 35(1):267–281Crossref, Google Scholar
• Bennell J. A., Dowsland K. A., Dowsland W. B. The irregular cutting-stock problem—A new procedure for deriving the no-fit polygon. Comput. Oper. Res. (2001) 28(3):271–287Crossref, Google Scholar
• Burke E. K., Kendall G. A comparison of meta-heuristic algorithms for clustering rectangles. Comput. Indust. Engrg. (1999) 37(1–2):383–386Crossref, Google Scholar
• Burke E. K., Kendall G., Whitwell G. A new placement heuristic for the orthogonal stock cutting problem. Oper. Res. (2004) 52(4):655–671Link, Google Scholar
• Burke E. K., Hellier R. S. R., Kendall G., Whitwell G. A new bottom-left-fill heuristic algorithm for the two-dimensional irregular packing problem. Oper. Res. (2006) 54(3):587–601Link, Google Scholar
• 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(1):27–49Crossref, Google Scholar
• Coffman E. G., Leighton F. T. A provably efficient algorithm for dynamic storage allocation. J. Comput. System Sci. (1989) 38(1):2–35Crossref, Google Scholar
• Coffman E. G., Garey M. R., Johnson D. S. An application of bin packing to multiprocessor scheduling. SIAM Comput. (1978) 7(1):1–17Crossref, Google Scholar
• Coffman E. G., Garey M. R., Johnson D. S. Approximation algorithms for bin packing—An updated survey. Algorithm Design for Computer Systems Design (1984) (Springer-Verlag, Berlin) 49–106Crossref, Google Scholar
• Dagli C. H., Hajakbari A. Simulated annealing approach for solving stock cutting problem. Proc. IEEE Internat. Conf. Systems, Man, Cybernetics (1990) Los Angeles(IEEE, Washington, DC) 221–223Crossref, Google Scholar
• Dagli C. H., Poshyanonda P. New approaches to nesting rectangular patterns. J. Intelligent Manufacturing (1997) 3(3):177–190Crossref, Google Scholar
• Dowsland K. A., Dowsland W. B. Packing problems. Eur. J. Oper. Res. (1992) 56(1):2–14Crossref, Google Scholar
• Dyckhoff H. A typology of cutting and packing problems. Eur. J. Oper. Res. (1990) 44(2):145–159Crossref, Google Scholar
• Garey M. R., Johnson D. S.Computers and Intractability: A Guide to the Theory of NP-Completeness (1979) (W. H. Freeman and Company, San Francisco) Google Scholar
• Garey M. R., Johnson D. S., Ausiello D., Lucertini M. Approximation algorithms for bin packing problems: A survey. Analysis and Design of Algorithms in Combinatorial Optimization (1981) 266(Springer, Vienna) 147–172CISM Courses and LecturesCrossref, Google Scholar
• Gilmore P. C. The cutting stock problem. Proc. IBM Sci. Comput. Sympos. Combin. Problems (1966) (IBM Data Procesing Division, White Plains, NY) 211–224Google Scholar
• Gilmore P. C., Gomory R. E. A linear programming approach to the cutting stock problem. Oper. Res. (1961) 9(6):849–859Link, Google Scholar
• Golden B. L. Approaches to the cutting stock problem. IIE Trans. (1976) 8(2):265–274Google Scholar
• Hopper E., Turton B. C. H. A genetic algorithm for a 2D industrial packing problem. Comput. Indust. Engrg. (1999) 37(1–2):375–378Crossref, Google Scholar
• Hopper E., Turton B. C. H. An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem. Eur. J. Oper. Res. (2001) 128(1):34–57Crossref, Google Scholar
• Hower W., Rosendahl M., Köstner D.Evolutionary Algorithm Design. Artificial Intelligence in Design '96 (1996) (Kluwer Academic Publishers, Dordrecht, The Netherlands) 663–680Google Scholar
• Iori M., Martello S., Monaci M., Pardalos P. M., Korotkikh V. Metaheuristic algorithms for the strip packing problem. Optimization and Industry: New Frontiers (2003) (Kluwer Academic Publishers, Boston) 159–179Crossref, Google Scholar
• Jakobs S. On genetic algorithms for the packing of polygons. Eur. J. Oper. Res. (1996) 88(1):165–181Crossref, Google Scholar
• Lai K. K., Chan J. W. M. Developing a simulated annealing algorithm for the cutting stock problem. Comput. Indust. Engrg. (1996) 32(1):115–127Crossref, Google Scholar
• Li Z., Milenkovic V. Compaction and separation algorithms for non-convex polygons and their applications. Eur. J. Oper. Res. (1995) 84(3):539–561Crossref, Google Scholar
• Lodi A., Martello S., Monaci M. Two-dimensional packing problems: A survey. Eur. J. Oper. Res. (2002) 141(2):241–252Crossref, Google Scholar
• Paull A. E. Linear programming: A key to optimum newsprint production. Pulp Paper Magazine Canada (1956) 57:85–90Google Scholar
• Ramesh Babu A., Ramesh Babu N. Effective nesting of rectangular parts in multiple rectangular sheets using genetic and heuristic algorithms. Internat. J. Productions Res. (1999) 37(7):1625–1643Crossref, Google Scholar
• Roberts S. A. Application of heuristic techniques to the cutting stock problem for worktops. J. Oper. Res. Soc. (1984) 35(5):369–377Crossref, Google Scholar
• Smith D. Bin packing with adaptive search. Proc. 1st Internat. Conf. Genetic Algorithms Appl. (1985) (Lawrence Erlbaum Associates, Hillsdale, NJ) 202–207Google Scholar
• Stoyan Y., Scheithauer G., Pridatko D., Romanova T., Gil N. Phi-functions for primary 3D-objects. (2002) . Technical Report MATH-NM-15-2002, Technical University of Dresden, Dresden, GermanyGoogle Scholar
• Sweeney P. E., Paternoster E. R. Cutting and packing problems: A categorized application-orientated research bibliography. J. Oper. Res. Soc. (1992) 43(7):691–706Crossref, Google Scholar
• Valenzuela C. L., Wang P. Y. Heuristics for large strip packing problems with guillotine patterns: An empirical study. Proc. 4th Metaheuristics Internat. Conf., (MIC'2001) (2001) Porto, Portugal:417–421Google Scholar