Research On The Planning And Scheduling Problem Considering Cutting Stock

The cutting stock problem is often encountered in the manufacturing industry.It is one of the most representative problems in the field of combinatorial optimization.Its essence is to decide the spatial combination of small items in large objects to improve the space utilization.Mathematical modelling and algorithms development for the cutting stock problem can reduce the production resources and costs,thereby,enhancing the competitiveness of enterprises.This paper conducts the following systematic research on the one-dimensional multi-stock cutting stock problem:This paper first focuses on the large-scale cutting stock problem considering the batch feed,i.e.balancing of the batch conveyance cost and the the board diversity,which influences the cutting waste,so that to make the cutting and batch feed plans simultaneously.Stems from the industrial production of a furniture factory,this paper establishes three types of mathematical models,including the assignment-based model,the clusteringassignment-based model,and the pattern-based model.Based on the lower bounds for the original problem provided by the former two models,and the idea of rounding and local search,this paper developed two types of residual heuristic.Based on the pattern-based model,a set-covering heuristic algorithm which is based on the column generation is proposed.Based on the real data,performances of different algorithms are tested.The results demonstrate that,the set-covering heuristic obtains optimal or near-optimal solutions in several seconds.Compared with the algorithm presently used in the factory,on average,it reduces the cutting waste by 16.83% and the total costs by 26.15%.The iterative heuristic solves the problem in around one minute and reduce more batch transportation cost.This paper also conducts research on the cutting stock problem considering lot-sizing and configuration-dependent production process.This problem considers both the cutting stock decisions and the balance of setup costs and holding costs in the planning horizon,so that to make the cutting and lot-sizing decisions simultaneously.Based on the industrial production in an aviation manufacturing factory which focuses on the production of composite aeronautic products,this paper considers the “configuration-dependent production process”,i.e.the production time and production cost are dependent on the configuration of the machine.And,the production process takes a long time,resulting in the consideration of various lead times.To solve the large-scale instances efficiently,this paper decomposes the original model based on the Dantzig–Wolfe framework.A hybrid algorithm that combines the column generation and the fix-and-optimize heuristic is proposed to generate feasible solutions.To accelerate the column generation process,this paper develops a bi-level dynamic programming algorithm,i.e.solving unbounded knapsack problems – passing the results and reformulating the sub-problem – solving the reformulated sub-problem,to solve the sub-problems exactly.The computational results show that the bi-level dynamic programming algorithm has an obvious advantage over CPLEX in terms of the computational efficiency and stability.For the large-scale instances,the combined heuristic reduces the computational time by 43.96% while improve the quality of feasible solutions by 3.34% compared with CPLEX,a commercial solver.And the heuristic performs better in terms of the convergence performance.Finally,this paper conducts research on the dynamic scheduling problem considering cutting stock in the dynamic workshop environment.An algorithm which is designed based on the predictive-reactive strategy and the idea of decomposition – neighbourhood search is proposed.It applies to the production system in which the multi-level products are produced and the cutting stock process is the bottleneck.The algorithm has the advantages such as high efficiency and good extensibility.Based on the algorithm,this paper designs the architecture,use case tables,entity–relationship model for the production management information system,and shows parts of the prototype system.