Dissertation > Excellent graduate degree dissertation topics show

The Algorithm and System for Two-Dimensional Irregular Nesting Problem

Author: LiuYueMing
Tutor: HuYueMing; LiSheng
School: South China University of Technology
Course: Control Engineering
Keywords: Irregular Nesting the Smallest Surrounding rectangle Heuristic Rule Geometrical Characteristic compare
CLC: TP391.7
Type: Master's thesis
Year: 2012
Downloads: 83
Quote: 0
Read: Download Dissertation

Abstract


Two-dimensional (2D) nesting problem, a layout optimization problem, concerns how toplace pieces on two-dimensional sheets of materials in most efficient layout problem.2Dproblem has a wide range of applications in many manufacturing field, such as ship buildingindustry, textile industry, newspapers and periodicals layout, cutting, etc. In some enterpriseswhich have low production level, the nesting problem is solved by manual and so the resultsgreatly rely on workers’ experience. With the rapid economic development, a slightimprovement in material sheet utilization can make huge economic profits. Therefore, it hasattracted many scholars around the world to make researches on different type of2D nestingproblem for decades of years. However,2D irregular nesting problem in which the pieces areirregular has high complexity, and there still have no good method to solve the problem.Although some studies have showed that no-fit polygon (NFP) based algorithm and geneticalgorithm may have higher material sheet utilization, the calculation of NFP is very complexin implementation and is hard to use in reality. For the above problems, this dissertationfocuses on the research of heuristic algorithms to nest2D irregular pieces rapidly andefficiently. The main works are listed as follows:(1) A simple method to calculate the smallest surrounding rectangle is first proposed.Then, a heuristic based on laying out the smallest surrounding rectangle of irregular pieces ondifferent levels to nest the irregular pieces indirectly. This algorithm can nest the irregularpieces rapidly and avoid producing large holes.(2) Another approach which nests2D irregular pieces directly is proposed. It comparesthe matching degrees of the geometrical characteristic between the material sheet and theirregular pieces and takes the matching degrees as reference criterions of nesting. There is noneed to calculate the NFP in this approach and the pieces are laid out rapidly. Combining thepieces dynamically in the nesting process also helps to yield higher material sheet utilization.(3) Combining the above two algorithms, an algorithm which lay the irregular piecesdirectly based on positioning the part of nested region is proposed. The irregular pieces arelaid out on the position with minimum area waste by the analysis of the reference position onthe nested region. Then, the pieces move close to the nested region by using the “shake” type.By such means, the complexity of nesting the irregular pieces is simplified, and the speed ofnesting is improved.(4) At last, a software with the three proposed nesting algorithms is designed anddeveloped. It can interact data with the AutoCAD and could be applied the nesting algorithms to solve the problems in real production.

Related Dissertations

  1. Workshop Production Scheduling Based on Manufacturing Workshop Real-time Information Network,TH186
  2. Intelligent optimization method of nesting,TP273.5
  3. Research on Chinese Named Entity Semantic Relation Extraction Based on Dependency Tree,TP391.1
  4. The Study of 2D Irregular Packing Problem,O224
  5. Study of the Production Planning and Scheduling System in Hybrid Production Style,TH162
  6. Research on Basic Algorithms of Digital Image Processing and Implementation with FPGA,TP391.41
  7. Research on Facial Feature Extraction and Matching Algorithms for Image Retrieval,TP391.41
  8. Research of High Speed Image Pre-processing System Based on FPGA,TP391.41
  9. The Research and Implemention of Image Retrieval Based on User Interested Feature,TP391.41
  10. Research of Image Mosaic Technology,TP391.41
  11. Research on the Classification Based on the Reconstruction of Solder Joint,TP391.41
  12. Tongue Feature Extraction and Research of Fusion Classification,TP391.41
  13. Research on Structure Transition Technology for SMT,TP391.2
  14. The Fatigue State Recognition of the Driver Based on Eye Detection,TP391.41
  15. Research on Image Compression and Implementation Using TMS320C6713 Based on SPIHT Algorithm,TP391.41
  16. Research of Images Enhancing Algorithms on Fog or Backlighting Conditions and Implementation with Hardwares,TP391.41
  17. Video Coding Research Based on Texture Characteristics,TP391.41
  18. Research on Feature Extraction and Classification of Pulse Waveform for Cholecystitis and Nephrotic Syndrome Diagnosis,TP391.41
  19. Application of Q-Learning in the Content-Based Image Retrieval Technology,TP391.41
  20. Research and Implementation on Content-Based Clothing Image Retrieval,TP391.41
  21. The Discovery of User Concept Region Based on Multiple Instance Learning,TP391.41

CLC: > Industrial Technology > Automation technology,computer technology > Computing technology,computer technology > Computer applications > Information processing (information processing) > Machine-assisted technology
© 2012 www.DissertationTopic.Net  Mobile