Optimization Algorithms For The Two-dimensional Three-staged Guillotine Cutting Stock Problems

The Cutting Stock Problem(CSP) is an important combinational optimization problem with high computational complexity and engineering backgroup, metal cutting in machinery manufacturing, wood cutting in furniture manufacturing, glass cutting in construction, layout of printing, plastic processing in chemical industry, clothing trim and so on are such applications. Optimization algorithms can provide good cutting plans for the CSPs, and help to reduce the material cost and simplify the cutting process, thus reduce the production cost and improve the competitiveness of enterprises.Taking the two-dimensional guillotine cutting stock problem(2DGCSP) as the research object, we start from researching the homogenous three-staged(3H) cutting plan of minimum used plates, and extending to the CSP and the residual CSP with standard usable leftovers. The best cutting plan satisfies all the item demands with minimum plates, and improves the reusability of leftovers. The priority use of leftovers in the subsequent product periods decreases the number of used plates, reduces the material waste and the pollution on the environment.In this paper, we study the following three aspects of the 2DGCSP, the main work and innovation points include:(1) For the general 2DGCSP, an iterative sequential value correction(ISVC) method is used to generate 3H cutting plans that consist of 3H cutting patterns. Many 3H cutting plans are generated, and the one with minimum used plates is selected as the solution. The cutting plan is nested into multiple optimization cutting patterns. The cutting patterns are generated by fast recursive procedures. Initial item values are changed and are corrected after the generation of the current cutting pattern by a value correction formula, and inherited to the next iteration, so as to change the priority list of the items, which leads to the reasonable distribution of the item types in different cutting patterns.The experimental results of many instances show that the ISVC is especially suitable for solving the medium and large instances, the three-staged cutting plans generated by the ISVC are better than those generated by literature algorithms and the commercial software packages. The effect is not only reflected on used plates and computational time, but also on the simplification of cutting operation.(2) For the 2DGCSP with standard usable leftovers, a beam search heuristic is prsented to merge fragments to the right side of the plate, and form standard leftovers with the same width as the plate. The evaluation operator considers both the partial pattern value of the used sub-plate, and the estimated value of the unused sub-plate or the reused value of the leftover. The cutting pattern obtained from recurisions is used as a filter to remove bad nodes.Computational results show that the algorithm can merge the standard leftover in the cutting pattern. And the value of items in the 3HL cutting patterns that generated by the beam search heuristic is higher than similar patterns of the literature. With less scrap, the 3HL cutting patterns have larger reusable leftovers.(3) For the residual 2DGCSP with standard leftovers, two heuristic algorithms ISVCL and ISVC-BS are presented. The ISVCL extended the ISVC to consider the generation and priority use of standard leftovers, and the objective is to minimize material cost(the difference between the total area of used plates and that of leftovers). The ISVC-BS combines the ISVC with the beam search. The beam search is used to generate the initial cutting pattern. And the ISVC is used to improve the cutting plan of remainding demands with minimum number of used plate, with the beam search to emerge the standard leftovers of low usage cutting patterns. The pseudo cutting pattern is generated using maximum plate length and the one with highest value ratio is selected as the current cutting pattern. To make leftovers have higher priority compare with plates, a coefficient for using leftovers is attached.The computational results of single period show that the number of iteration of ISVC-BS is less than that of the ISVCL, and also the larger standard leftover. The computational results of multiple periods show that the leftovers of the ISVC-BS can be used effectively in the subsequent periods, as for that, the number of used plate is decreased, which helps to reduce the long-term production costs.