Heuristic Algorithm For The Stack Cutting Stock Problem Of Rectangular Items

Stacking Cutting Problem(SCP)appears widely in plate cutting,but algorithms for the classical two-dimensional cutting stock problem cannot effectively reduce the total cost(sum of material cost and cutting cost)of the TSCSP.And there are few studies on the number of blocks in restricted pattern.In view of the above research status,this paper presents a Sequential Stacking Grouping Heuristic(SSGH)to solve the TSCSP.The purpose of the algorithm is to reduce the number of pattern and stack in the process of cutting by stack,and to reduce the total cost of the cutting plan as much as possible.The main research work of this paper is summarized as follows:(1)The SSGH sequentially generates the cutting patterns in the cutting plan,For each cutting pattern,residual items(rectangular parts)are selected to form a candidate items set according to the stacking rule,and the candidate set are used to generate the current pattern whose frequency is determined according to the stacking rule.Repeat the pattern-generation process until all item demands are met and a cutting plan is determined.Each time a cutting pattern is generated,values of the items included in the cutting pattern are corrected by a value correction algorithm,so that the item value tends to be reasonable.Multiple iterations generate different cutting plans from which the lowest total cost is selected as the solution to the problem.Experimental results show that the SSGH based on the stacking rule can obviously reduce the total cost of the cutting plan.(2)Adding the restriction of the number of blocks in the pattern and the consideration of the turning of the items to the heuristic algorithm of sequential grouping.Combined with the actual cutting and sawing process,if there is a pattern of different blocks,the cutting direction of the plate needs to be constantly changed to increase the cutting cost.Therefore,based on the strategy of stacking and grouping,a pattern method with block number restriction is proposed to reduce the total cost of cutting plan.Through the analysis of several groups of experimental data,it shows that the cutting mode with block number restriction provides a strategy for enterprises to reduce the total cost of cutting plan.Enterprises can flexibly choose whether to limit the number of blocks according to different production needs and limit the upper bound of the number of blocks in each pattern drawing as the most suitable value for production purpose,so as to reduce the cutting cost.In the process of cutting plan,because many applications are not limited by the plate turning,the pattern mode of item turning is proposed to further improve the utilization rate of the plate,so as to ensure the effective utilization of the plate in the block limited blanking mode.(3)Using C# language to design and develop the optimized cutting system according to stack.The random examples in the literature are used to compare the research contents of this paper.The experimental results show that the proposed heuristic algorithm is effective in reducing the number of layouts and stacks and the total cost of production.