Research For The Optimal Cutting Of Punched Strips

Computer Aided Nesting (CAN) is an important branch of the computer aided design and manufacturer. The optimal layout technology is used to instruct industries to deal with the cutting stock problem, and appears in many industries, such as mechanical, clothing manufacturing, leather and construction industry. It has been proved to be a rather difficult nondeterministic polynomial (NP) complete problem with higher computational complexity. Traditional works always rely on artificially experience, which leads to increased product cost because of long working hours and unobvious effects. Accordingly, there is an important theoretic and actual purport for the design of reasonable and optimal algorithm.The shearing and punching process is often applied in manufacturing to cut the metal sheet, which consists of two stages:the strips cutting stage and the items punching stage. At the strips cutting stage, the plate is cut into strips by a guillotine shear, and at the items punching stage, the items are cut from the strips by a stamping press. Although the parameters (the strip width and the steps) of punched strips were determined at the tooling design stage and cannot be changed later, but the waste of raw material may be reduced by optimizing the layout of strips on the sheet. In generating cutting patterns of the strips at the strips cutting stage, strips of different item types can appear in the same pattern, and strips of the same item type can have different lengths and directions. At present, scholars in and abroad have been working on rectangle packing problem and proposed a variety of efficient algorithms such as dynamic programming, branch-and-bound, continued fraction, tabu search, ant algorithm. However, there are a few algorithms for the strip-cutting problem.The unconstrained strip-cutting problem discussed in this paper is as follows:There are various items, the value of each item type and the strip parameters are known. The sheet is cut into strips by a guillotine machine, there is no constraint on the number of each item type appearing in a pattern, the purpose is to make the total value of items in a pattern reach its maximum. The unconstrained algorithm and the linear programming approach are combined to solve the following strip-cutting stock problem:Appling the shearing and punching process, the demand of each item type and the strip parameters are known; the purpose is to make the total cost of sheet reach its minimum on the basis of satisfying the item's demand. This paper presents an algorithm for generating multiple-segment cutting patterns of strips, which uses the idea of the algorithm for generating multiple-segment cutting patterns of rectangular items. The main work is organized as follows:Firstly, the algorithm for generating multiple-segment cutting patterns is designed. The stock sheet is divided into segments by parallel dividing cuts. Each segment contains a group of strips which have the same orientation and length. The dynamic programming algorithm determines the optimal value of all the segments and the optimal combination of the segments included in the plate so as to maximize the value of the whole sheet.Secondly, in order to improve the algorithm, this paper presents one strategy to reduce the number of strips considered to improve the computation speed and reduce the computation time.Thirdly, base on the proposed algorithm, we design the basic functional modules of the strip-cutting system and develop the system. Various instances are used to test the algorithm. The computational results indicate that the algorithm can improve the material utilization, and the computation time is reasonable for practical use.