Design And Implementation Of Optimization Algorithms For Layout Based On Glass Cutting Machines

Continuous development of the automatic discharge technology of computer has made a large number of benefits for many areas of layout. Layout optimization based on glass cutting machines is just one of them. The layout of two-dimensional graphics is an NP complete problem, It has a higher computational complexity and it will be certainly bring a great challenge to the layout algorithms based on glass cutting machines which call for practicability. For the needs of specific area, this paper starts with some core algorithms. After having studied further of them, I design algorithms for rectangular parts and irregular parts respectively.For rectangular parts, this paper firstly makes some improvements for the greedy algorithm and the algorithm on the basis of the lowest horizontal line, and then makes a designation of them respectively, through Matlab simulations and comparisons as well as analysis I find that the greedy algorithm can make a very high utilization rate and it has a great potential to improve its property of time consuming, the combination algorithm on the basis of the lowest horizontal line can effectively improve the blank areas which have not been occupied and it can be chosen as a new idea to improve the algorithm on the basis of the lowest horizontal line. According to the requirements of the specific area, I choose the improved greedy algorithm as the one to put into practice. After that I continually making improvements for the improved greedy algorithm twice and make some comparisons. The layout of results from test datas through VC prove that the first one is better than the one done in the Matlab simulations indeed, and it fits medium scale rectangular parts which are in many different kinds and the dimension of each one is not relatively large to the sheets, which can make sure a better utilization; the second one makes a further improvement which take advantages of the idea of strips that reduces the objects to occupy corners and reduces the time for layout, which fits a larger scale. All the results above confirm that we can apply both of them to the layout based on glass cutting machines.For irregular parts, I start with the description of irregular graphics, set collision rules myself, and apply the idea of lowest horizontal line to the area of irregular parts. After the designing of data structures and the main modules as well as the overall flow chart of the algorithm, I fulfill the collision algorithm on the basis of the lowest horizontal line through VC, the results show that this algorithm suits for rapid packing and the utilization is satisfied, which can be put into practice.