Dissertation > Excellent graduate degree dissertation topics show

Research on Heuristic Algorithms for the Packing Problems

Author: WeiLiJun
Tutor: ZhangDeFu
School: Xiamen University
Course: Applied Computer Technology
Keywords: Packing Problem Heuristic Algorithm Simulated Annealing
CLC: TP301.6
Type: Master's thesis
Year: 2008
Downloads: 294
Quote: 0
Read: Download Dissertation

Abstract


Packing problem is faced in many industries, for example, the container loading, the sheet cutting, the design of VLSI and the newspaper editor. It is a NP complete problem; the research on this problem is of great significance in both theory and practice. It is high complexity if we use the general exact algorithm to solve the packing problem, so a lot of heuristic algorithms have been proposed to solve it.In this paper, we first study the 2D-packing problem. Based on the known algorithm, we present a binary search heuristic algorithm (BSHA) for the 2D strip packing problem. Firstly, by introducing the binary search algorithm, we transform the 2D strip packing problem into the 2D knapsack packing problem. Then, for the 2D knapsack packing problem, we present a least wasted first strategy based on the way of finding positions to pack rectangles and introduce the conception of "the wasted area" and "variable flat point" to evaluate a pack. Lastly, a random local search is introduced to improve the results. The computational results on several classes of benchmark problems have shown that BSHA can find better solution than other known algorithms, such as GRASP, SPGAL, HRBB, especially, BSHA can find an optimal solution for many instances in short time.For the 3D-packing problem, we present a combinational heuristic algorithm. Firstly, we develop a personification heuristics, which is inspired by the strategy of building wall in the daily life. Similar to the personification heuristics for the 2D-packing problem, we introduce the "reference box" and the "reference line" to guide the process of packing. Lastly, a simulated annealing algorithm is further used to improve the personification heuristics. Computational results on benchmark instances show the algorithm can compete with excellent heuristics from the literatures.

Related Dissertations

  1. Active Power Filter and Its Application in Distribution Network,TN713.8
  2. Study on Site Selection of Ecological Food Franchisees in Jiaxiang, Taiyuan,F426.82
  3. Research on Combinatorial Optimization Problem Based on DNA Self-Assemble,TP399-C8
  4. The Research and Implementation of the Fault Management System for Triple Play,TP315
  5. Research of Vehicle Scheduling Problem Based on Ant Colony Algorithm,TP301.6
  6. The Research of Signal Detecting Algorithms and Improved Sphere Detecting Algorithms in MIMO Systems,TN919.3
  7. The Research of Trust Model and Related Technologies in P2P Networks,TP393.08
  8. Hysteresis -based optimization of vehicle routing problem,O224
  9. Parallel sorting multiple orders optimization problem,F224
  10. Single- and multi- assignment assigned coexistence with hub Logistics Network Design,F252
  11. Aircraft assembly moving assembly line job scheduling optimization,V262.43
  12. Civilian ship management system design and implementation,TP311.52
  13. Flexible resource scheduling algorithm for dynamic combinatorial production and realization,F426.8
  14. Radar jamming and interference covering optimal allocation of resources,TN974
  15. Resource-based needs analysis study time production plant logistics optimization,F426.471
  16. Research on Relations among Hot News,TP393.09
  17. Research and Application of hybrid genetic algorithm - based shop scheduling problem,TP18
  18. Improved Analysis and Applied Research of Artificial Glowworm Swarm Optimization Algorithm,TP18
  19. Image registration techniques and optimization algorithms research,TP391.41
  20. Paralleling Genetic Annealing Algorithm with OpenMP,TP301.6
  21. Optimization on Input Operations and Management Information System Development of a Steel Plate Stacking Yard in a Shipyard,F426.474

CLC: > Industrial Technology > Automation technology,computer technology > Computing technology,computer technology > General issues > Theories, methods > Algorithm Theory
© 2012 www.DissertationTopic.Net  Mobile