Advertisement

On Improved Least Flexibility First Heuristics Superior for Packing and Stock Cutting Problems

  • Yu-Liang Wu
  • Chi-Kong Chan
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3777)

Abstract

Two dimensional cutting and packing problems have applications in many manufacturing and job allocation problems. In particular, in VLSI floor planning problems and stock cutting problems, many simulated annealing and genetic algorithms based methods have been proposed in the last ten years. These researches have mainly been focused on finding efficient data structures for representing packing results so the search space and processing time of the underlying search engine can be minimized. In this paper, we tackle the problem from a different approach. Instead of using stochastic searches, we introduce an effective deterministic optimization algorithm for packing and cutting. By combining an improved Least Flexibility First principle and a greedy search based evaluation routine, we can obtain very encouraging results: In stock cutting problems, our algorithm achieved over 99% average packing density for a series of public rectangle packing data sets, which is significantly better than the 96% packing density obtained by meta-heuristics (simulated annealing) based results while using much less CPU time; whereas in rectangle packing applying the well-known MCNC and GSRC benchmarks, we achieved the best (over 96%) packing density among all known published results packed by other methods. Our encouraging results seem to suggesting a new experimental direction in designing efficient deterministic heuristics for some kind of hard combinatorial problems.

Keywords

Simulated Annealing Packing Density Packing Problem Placement Location Greedy Search 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. 1.
    Baker, B.S., Coffman Jr., E.G., Rivest, R.L.: Orthogonal Packing in two dimensions. SIAM Journal on Computing 9, 846–855 (1980)zbMATHCrossRefMathSciNetGoogle Scholar
  2. 2.
    Bentley, J.L.: Multidimensional binary search trees used for associative searching. Communication of ACM 18(9), 507–517 (1975)CrossRefMathSciNetGoogle Scholar
  3. 3.
    Kenyon, C., Remila, E.: Approximate strip packing. In: Proc. 37th IEEE Symposium on Foundations of Computer Science, pp. 31–36 (1996)Google Scholar
  4. 4.
    Kenyon, C., Remila, E.: A near optimal solution to a two-dimensional cutting stock problem. Mathematics of Operations Research 25(4) (2000)Google Scholar
  5. 5.
    Dowsland, K.: Some experiments with simulated annealing techniques for packing problems. European Journal of Operational Research 68, 389–399 (1993)zbMATHCrossRefGoogle Scholar
  6. 6.
    Jacobs, S.: On Genetic algorithms for the packing of polygons. European Journal of Operational Research 88, 165–181 (1996)CrossRefGoogle Scholar
  7. 7.
    Leung, T.W., Chan, C.K., Troutt, M.D.: Mixed simulated annealing-Genetic algorithm Application of a mixed simulated annealing-genetic algorithm heuristic for the two-dimensional orthogonal packing problem. European Journal of Operational Research 145, 530–542 (2003)zbMATHCrossRefMathSciNetGoogle Scholar
  8. 8.
    Wu, Y.L., Huang, W.Q., Lau, S.C., Wong, C.K., Young, G.H.: An effective quasi-human heuristic for solving the rectangle packing problem. European Journal of Operational Research 141, 341–358 (2002)zbMATHCrossRefMathSciNetGoogle Scholar
  9. 9.
    Murata, H., Fujiyoshi, K., Kaneko, M.: VLSI/PCB placement with obstacles based on sequence pair. IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems 17(1), 60–67 (1998)CrossRefGoogle Scholar
  10. 10.
    Burke, E., Kendall, G.: Applying Simulated Annealing and the No Fit Polygon to the Nesting Problem. In: Proceedings of the World Manufacturing Congress, Durham, UK, pp. 27–30 (1999)Google Scholar
  11. 11.
    Dagli, C.H., Poshyanonder, P.: New Approaches to Nesting Rectangular Patterns. Journal of Intelligent Manufacturing 8(3), 177–190 (1997)CrossRefGoogle Scholar
  12. 12.
    Chazzelle, B.: The Bottom-Left Bin Packing Heuristic: An efficient Implementation. IEEE Transactions on Computers 32/8, 697–707 (1983)CrossRefGoogle Scholar
  13. 13.
    Hopper, E., Turton, B.C.H.: An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem. European Journal of Operational Research 128/1, 34–57 (2000)Google Scholar
  14. 14.
    Ratanapan, K., Dagli, C.H.: An object-based evolutionary algorithm for solving irregular nesting problems. In: Proceedings for Artificial Neural Networks in Engineering Conference, vol. 7, pp. 383–388. ASME Press, New York (1997)Google Scholar
  15. 15.
    Ratanapan, K., Dagli, C.H.: An object-based evolutionary algorithm: the nesting solution. In: Proceedings of the International Conference on Evolutionary Computation 1998, ICEC 1998, pp. 581–586. IEEE, Piscataway (1998)Google Scholar
  16. 16.
    Liu, D., Teng, H.: An Improved BL-algorithm for Genetic Algorithm of the Orthogonal. Packing of Rectangles. European Journal of Operational Research 112, 412–420 (1999)Google Scholar
  17. 17.
    Zhou, S., Dong, S., Hong, X., Cai, Y., Cheng, C.K., Gu, J.: ECBL, An Extended Corner BlockList with solution Space including Optimum Placement. In: Proceeding of International Symposium on Physical Design, pp. 156–161 (2001)Google Scholar
  18. 18.
    Zhuang, C., Saknushi, K., Jin, L., Kajitani, Y.: An Enhanced Q-Sequence Augmented with Empty-Room-Insertion and Parenthesis Trees. In: Proceedings of Design, Automation and Test in Europe, pp. 61–68 (2002)Google Scholar
  19. 19.
    Tang, X., Wong, D.F.: FAST-SP: A Fast Algorithm for Block Placement based on Sequence Pair. In: Proceeding of IEEE Asia South Pacific Design Automation Conference, pp. 521–526 (2001)Google Scholar
  20. 20.
    Lin, J.-M., Chang, Y.-W.: TCG: A Transitive Closure Graph-Based Representation for Non-Slicing Floorplans. In: Proceedings of the 38th ACM/IEEE Design Automation Conference, pp. 764–769 (2001)Google Scholar
  21. 21.
    Wong, D.F., Liu, C.L.: Anew algorithm for floorplanning design. In: DAC 1986, pp. 101–107 (1986)Google Scholar
  22. 22.
    Lin, J.-M., Chang, Y.-W.: TCG-S: orthogonal coupling of P*-admissable representation for general floorplans. In: DAC 2002, pp. 764–769 (2002)Google Scholar
  23. 23.
    Zhou, H., Wang, J.: ACG- adjacent constraint graph for general floorplans. In: ICCD 2004, pp. 572–575 (2004)Google Scholar
  24. 24.
    Wang, P., Cheng, C.K., Yoshimura, T.: An enhanced perturbing algorithm for floorplan design using the O-tree representation. In: ISPD 2000, pp. 168–173 (2000)Google Scholar
  25. 25.
    Chang, Y.C., Chang, Y.W., Wu, E.M., Wu, S.W.: B*-trees: a new representation for non-slicing floorplans. In: DAC 2000, pp. 458–463 (2000)Google Scholar
  26. 26.
    Young, E.F.Y., Chu, C.C.N., Sgen, Z.C.: Twin binary sequences: a non-redundant, representation for general non-slciing floorplan. IEEE Transaction on CAD 22(4), 457–469 (2003)Google Scholar
  27. 27.
    Chan, H.H., Markov, I.L.: Practical slicing and non-slicing block-packing without simulated annealing. In: IEEE Great Lake Symp. On VLSI 2004, pp. 282–287 (2004)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Yu-Liang Wu
    • 1
  • Chi-Kong Chan
    • 1
  1. 1.The Chinese University of Hong KongShatin, Hong Kong

Personalised recommendations