Nesting (Cutting and Packing) problems are optimization problem encountered in many areas of business that look for good arrangement of multiple items in larger containing regions. The objective of this problem is to maximize the utilization of resource material. There is a large range of the applicability of these problems as there are many diverse instances of it that are encountered in the industries as paper, glass, plastic and foam, leather, sheet metal cutting, furniture, garments, ship-building, shoe-making, car production, building materials, packaging etc. Most of the standard problems related to Nesting are known to be NP-complete. The development of exact algorithms which are faster and produce near optimal solutions is still a major research issue in this area. Proliferation of sophisticated desktops and faith of researchers in meta-heuristics have further allowed them to look beyond the traditional optimization techniques to solve this hard problem. In this paper Authors have tried to explore further expansion in feasible patterns for rectangle packing by applying genetic operators on the initial population of feasible patterns generated by revised AYC Nee’s Rectangle Packing heuristic.

1. Dowsland, K.A., and Dowsland, W.B. 1992. Packing problems. Eur. J. OR, 56, pp. 2-14.
2. Dyckhoff, H. and Finke, U. 1992. Cutting and packing” production and distribution. Physica Verlag, Heidelberg..
3. Dyckhoff, H., Scheithauer, G., and Terno, J. 1996. Cutting and packing: An annotated bibliography, Preprint MATH-NM-08-1996, Techn. Univ. Dresden, 1996. to appear in Combinatorial Optimization: An Annotated Bibliography, eds. Dell’Amico, Maffioli, Martello.
4. Sweeney, P.E., and Ridenour, E.L. 1989. Cutting and packing problems: A categorized, application–oriented research bibliography, Technical report, Working Paper 610, School of Business Administration, University of Michigan.
5. J. Terno, R. Lindemann, and G. Scheithauer. Zuschnittprobleme und ihre praktische L¨osung. Verlag Harri Deutsch, Thun und Frankfurt/Main, 1987.
6. Singh, K. 2001. Designing Algorithms For Nesting Regular and Irregular Shapes, Ph. D. Thesis, Thapar University, Patiala (India).
7. Singh, K and Jain, L. 2009. An empirical study of a modified Cheok-Nee’s heuristic for 2d rectangular packing problem, Appejay J. Management Technology. 4, 53-64.
8. Holland, J.H. 1975. Adaptation in Natural and Artificial Systems, The University of Michigan Press.
9. Braun, H. On Solving Travelling Salesman Problem by Genetic Algorithm”, in Parallel Problem-Solving from Nature, Lecture Notes in Computer Science 496, H.P. Schwefel and R. Manner Eds, Springer-Verlag, app. 129-133.
10. Lipnitskii, A.A. 2002. Use of Genetic Algorithms for Solution of The Rectangle Packing Problem. Cybernetics And Systems Analysis. 38 (6), 943-946.
11. Ismail, H.S. and Hon, K.K.B. 1995. Nesting of two-dimensional shapes using genetic algorithms, Proceedings of the Institution of Mechanical Engineers, Part B, 209, 115-124.
12. Goldstein, 1991. Genetic Algorithm Simulation of the SHOP Scheduling Problem, by Jonathan M. Goldstein, in September 1991 published by An ICMS/Shell Oil Business Consultancy, 1991.
13. Goldberg, D.E. 1989. Genetic algorithms in search, optimization, and machine learning. Addison-Wesley, Reading, Mass.
14. Vignaux, G.A. and Michalewicz, Z. 1991. A Genetic Algorithm for the Linear Transportation Problem, IEEE Transactions on Systems, Man and Cybernetics 2, 21, 445-452.
15. Goldberg, D. and Lingle, R. 1985. Alleles, loci and the traveling salesman problem. In Proceedings of the first international conference on genetic algorithms, 154–159, 1985.
16. Grefenstette, J., Gopal, R., Rosmaita, B., and Gucht, D.,1985. Genetic algorithms for the traveling salesman problem.. In Proceedings of the first international conference on genetic algorithms, 160–168.
17. Davis, L. 1995. Applying adaptive algorithms to domains. In Proceeding of the international joint conference on artificial intelligence, 162–164.
18. Oliver, I.., Smith, D., Holland, J. 1987. A study of permutation crossover operators on the traveling salesman problem, In Proceedings of the second international conference on genetic algorithms. 224–230.
19. Syswerda, G. 1991. Scheduling optimization using genetic algorithms. In L. Davis (Ed.), Handbook of genetic algorithms, 332–349. New York: Van Nostrand Reinhold,
20. Yamamura, M. Ono, T. and Kobayashi, S. 1992. Character-preserving genetic algorithms for traveling salesman problem.. J. Japanese Society Arti. Intelligence, 6, 1049–1059.
21. Gen, M. and R. Cheng, R. 1994. Evolution program for resource constrained project scheduling problem.” In Proceeding of the first IEEE conference on evolutionary computation. 736–741.
22. Gen, M. and R. Cheng, R. 1997. “Genetic algorithms and engineering design.” New York: Wiley.

Genetic algorithm NP-complete Rectangle packing heuristic