An Algorithm For The Cutting Stock Problem Of Circular Items With Leftovers Generation And Utilization

Cutting stock problems exist widely in many manufacturing industries,including machine building industry,wood processing industry and other industries in which cutting stock objects is necessary.The advanced computer aided design techniques are used in the cutting process,the material utilization can be improved effectively and the production cost can be reduced obviously.In this paper,the 2D cutting stock problem of circular items is studied.In some manufacturing industries,the diameter of circular items required for order production is not very large,and the diameters of circular items for continuous order production during the planned period(e.g.quarterly accounting)are taken from the standard diameters.According to above background,an algorithm is proposed for the cutting stock problem of circular items with leftovers generation and utilization.The aim of the algorithm is to adopt a simple cutting process and determine a reasonable cutting plan,so as to minimize the total cost of materials for production and consumption in the planned period.The following is an overview of the main research work of this paper:(1)The framework of sequential value correction heuristic is used to solve the cutting stock problem of circular items.First of all,to maximize the value of single sheet,the layout algorithm is generated by splicing strips with recursive strategy.The optimal layout of circular items on a single sheet is obtained.Then the sequential heuristic algorithm is used to call the generated layout algorithm.According to the residual demand of the circular items,the generated layout is sequentially added to the current cutting plan.The values of circular items are corrected after the generation of each pattern.This is helpful to adjust the order of the circular items in the next generation of the current layout pattern.Finally,the whole algorithm for cutting stock problem of circular items is iterated several times as much as possible so as to diversify the cutting plans generated.The cutting plan with minimum total cost of consumable materials was selected as the solution to the cutting stock problem of circular items.Compared with the algorithm based on the general sequential framework,the experimental result shows that algorithm based on the sequential value correction framework can effectively reduce the consumption of sheets and reduce the total cost of materials consumed in production.(2)In the above algorithm for the cutting stock problem of circular items,the idea of considering the generation and utilization of leftovers is introduced.In the production of consecutive orders during the planned period,considering a leftover strip is generated actively in the one side of layout pattern for the layout pattern generated to meet the current order requirements.The diameter of the circular items in the leftover strip take one of the standard diameters.The generated leftover strips are temporarily put into inventory.A leftover strip corresponds to one circular item of standard diameter.It can be directly applied to the production of follow-up orders without cutting the leftover strip.The types and quantities of the leftover strips generated are constrained.Reasonable use of leftover-inventory to reduce raw material cost of order production.The final cutting plan simplifies the cutting process and improves the material utilization rate throughout the planning period.Compared with the above algorithm,which do not consider leftover generation and utilization,as well as the published literature,the experimental result shows that this algorithm can significantly reduce the consumption of sheets and the total cost of materials consumed in production.(3)The optimization system of circular items is designed and developed by using C#language.Random instances are generated.Comparisons are made between the algorithms reported in the literature and those in this paper.The results show that within the allowable computing time,the proposed algorithm can be used to solve the cutting stock problem of circular items.Simple cutting process can also improve material utilization and reduce production costs.Therefore,the algorithm proposed in this paper has a certain guiding significance for the production of manufacturing industry.