Evolving human-competitive reusable 2D strip packing heuristics

ABSTRACT

This extended abstract presents preliminary work on reusable automatically generated heuristics for the 2D strip packing problem. It builds on our previous work, where the heuristics were not shown to be reusable. The best constructive heuristic for this problem in the literature is 'best-fit', and the motivation of this work is to obtain heuristics which are comparable to the performance of this heuristic.

REFERENCES

• 1: M. B. Bader-El-Din and R. Poli. Generating sat local-search heuristics using a gp hyper--heuristic framework. In LNCS 4926. Proceedings of the 8th International Conference on Artifcial Evolution, pages 37--49, October 2007.
• 2: E. K. Burke , G. Kendall , G. Whitwell, A New Placement Heuristic for the Orthogonal Stock-Cutting Problem, Operations Research, v.52 n.4, p.655-671, July - August 2004 [doi>10.1287/opre.1040.0109]
• 3: E. K. Burke, M. R. Hyde, and G. Kendall. Evolving bin packing heuristics with genetic programming. In T. Runarsson, H.-G. Beyer, E. Burke, J. J.Merelo-Guervos, D. Whitley, and X. Yao, editors, LNCS 4193, Proceedings of the 9th International Conference on Parallel Problem Solving from Nature (PPSN'06), pages 860--869, Reykjavik, Iceland, September 2006.
• 4: Edmund K. Burke , Matthew R. Hyde , Graham Kendall , John Woodward, Automatic heuristic generation with genetic programming: evolving a jack-of-all-trades or a master of one, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277273]
• 5: E. K. Burke, M. R. Hyde, G. Kendall, and J. Woodward. The scalability of evolved on line bin packing heuristics. In Proceedings of the IEEE Congress on Evolutionary Computation (CEC'07), pages 2530--2537, Singapore, September 2007.
• 6: E. K. Burke, M. R. Hyde, G. Kendall, and J. Woodward. A genetic programming hyper-heuristic approach for evolving two dimensional strip packing heuristics. Technical report, University of Nottingham, Dept of Computer Science, 2008.
• 7: Alex S. Fukunaga, Automated discovery of local search heuristics for satisfiability testing, Evolutionary Computation, v.16 n.1, p.31-61, Spring 2008 [doi>10.1162/evco.2008.16.1.31]
• 8: Christopher D. Geiger , Reha Uzsoy , Haldun Aytug, Rapid Modeling and Discovery of Priority Dispatching Rules: An Autonomous Learning Approach, Journal of Scheduling, v.9 n.1, p.7-34, February 2006 [doi>10.1007/s10951-006-5591-8]
• 9: Joc Cing Tay , Nhu Binh Ho, Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems, Computers and Industrial Engineering, v.54 n.3, p.453-473, April, 2008 [doi>10.1016/j.cie.2007.08.008]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program synthesis

General Terms:
Design, Performance, Reliability

Keywords:
GP, heuristics, hyper-heuristics, strip packing