|
Question refers to the next nesting material in the process to minimize the loss of material, and the material of the highest utilization. It is widespread in the production process, such as sheet metal cutting, container loading, clothing and furniture manufacturing. Solve this problem, not only can save raw materials, reduce production costs, but also improve production efficiency. Rectangular nesting problem is two-dimensional packing problem on a branch. Many domestic and foreign scholars have conducted in-depth and extensive study, theoretically proved that it belongs to NP-complete problem. When faced with a larger scale, the amount of computation is bound to bring a combinatorial explosion, it is difficult to obtain the optimal solution within a certain time. In response to these issues, the current solution is mostly heuristic approaches. Therefore, the study of existing problems Rectangular Nesting practical value and theoretical significance. Heuristic method is characterized by problem-solving, the use of past experience rules, choose effective method. For large-scale optimization problem solving, which has fast random global search capability, greatly reducing the amount of calculation, exhibit superior performance than the other methods. In addition, the heuristic method is simple, easy to understand, has good scalability, the problem is to solve an important tool for nesting. This study is two-dimensional rectangular pieces of nesting problem that more than one of the same specifications on a rectangular sheet of rough emit a certain demand, making the total area of the plate consumption to a minimum. Based on the above considerations, in order to solve this problem, this paper \Other instances reported in the literature test comparison, plates were improved utilization to verify the validity of the proposed algorithm. The main work of this paper is as follows: First, a careful analysis of a variety of Chinese and foreign scholars have proposed heuristic algorithm, after careful comparison, at the conclusion of its strengths and weaknesses, based on the \\In this paper, we propose two on the basis of its transformation strategy, first, the addition of a restriction, that after the rough into the area if the waste generated greater than a value, then cancel it into. The modified policy to avoid some of the appearance of undesirable programs. Secondly, it is discharged into the direction of the blank. Early strategies using the \In this paper, based on its transformation adds a \After transformation may increase the diversity of the blank display, perhaps to improve the utilization of help sheet. Second, consider optimizing the computation time is too long, as well as uneven nesting program and other issues, we propose a grouping strategy, that all the rough split three groups according to the area size, every generation before the current mode, all from three each group to select the appropriate number of blocks used to generate the current mode. In the grouping process, there are a number of parameters can be adjusted according to actual situation. For example, to determine the appropriate number of blocks selected from the group of rough area and what the value should be set, this provides a maximum sheet size of 1 times, 0.3 times the minimum size sheet. After grouping operation, select a subset of the set blank, thereby shortening the time required to generate the current mode. Third, the transformation of the minimum waste priority and packet combining strategy, we propose a heuristic algorithm - grouping search algorithm. How to generate nesting algorithm is the key step sequence. In the existing heuristics, some scholars have applied the principles of genetics to generate nesting sequence, has achieved good results. This article refers to the random local search, using random swap two blanks relative order to generate a new nesting sequence. In the random operation, the need to use some tricks, when two small rectangular pieces randomly generated position, if they have the same location, or the two locations are the same kind of small rectangular pieces, put one of the positions gradually sliding scale until position two small rectangular pieces of different kinds so far, so to maximize sequence diversity, avoiding duplication sequence generation. After repeating the whole calculation, by comparing the results of well preserved solution to obtain a final layout plan. Grouping search algorithm is a combination of algorithms, the paper gives a detailed description of the pseudo-code. Fourth, through the rectangular parts like system framework for analysis, respectively, to achieve its four main modules feature. Including data input module, optimal nesting module nesting results display module, the system help module. Wherein the algorithm module is the core part of the framework. This paper selected three groups of test cases in the literature, which are related to this research question nesting rules similar, so this algorithm and its test results are comparable. After testing, and the results were compared and analyzed with, sheet utilization have been enhanced to verify the effectiveness of the algorithm. Fifth, to have a summary of the work done, raised the need for further improvement.
|