| The cutting stock problem is widely existed in the manufacturing industries of metals,wood,glass,plastics,and clothing,et al.The application of the cutting stock technology can reduce the material consumption and improve the production efficiency of enterprises.The traditional cutting stock technology mainly seeks the optimal combination of cutting patterns in the mathematical sense by designing a reasonable cutting stock algorithm.However,there are complex constraints in the real cutting stock process of enterprises.Those constraints are related to each other,which have certain influence on the mathematical model and optimization result of the cutting stock problem.Therefore,it is difficult for the traditional cutting stock technology to adapt real cutting stock process with the variability of constraints and the diversity of constraints combination.Focusing on the complex constraint during the real cutting stock process and the manufacturability of the cutting plan,this thesis conducts relatively research on the manufacturability oriented cutting stock technology under complex constraints.The complex constraints of cutting stock problem are classified according to the constraints source through the analysis of the main cutting stock process of the enterprise.The correlation of complex constraints in the cutting stock problem is studied.The mathematical description and modeling method of the manufacturability oriented cutting stock problem under the complex constraints is given with combination of the correlation of complex constraints and the main evaluation demand and framework of the manufacturability for cutting plans.An optimized decision-making method is proposed for the manufacturability oriented cutting stock technology under complex constraints.For the one-dimensional(1D)cutting stock problem in the cutting stock process,the correlations of stock constraint,item constraint,usable leftover constraint and cutting process constraint are considered,comprehensively.A mathematical model of 1D cutting stock problem is established based on manufacturability for 1D cutting plans.A sequential heuristic 1D cutting stock method based on cost balance is proposed.In this method,the compensation of 1D stocks and items is used to realize the length standardization of 1D stocks and items,which meets the requirement of process parameters in the cutting process.The 1D cutting plan generation technology based on dynamic programming algorithm is applied to achieve a cutting plan corresponding to satisfying the selected 1D item set with the given constraint by 1D item candidate set.The 1D cutting plan cost evaluation technology can be used to realize the balance between stock cost and setup cost of the 1D cutting patterns with cost balance utilization,and combine the architecture of sequential heuristic algorithm to select a cutting plan with the least sum of stock cost and 1D setup cost.Finally,the feasibility and effectiveness of the proposed method are verified by the instances.For the 1.5D cutting stock problem in the cutting stock process,the special cutting stock process is considered that two-dimensional(2D)items are cut down from metal coil with slitting and then stamping,combining the correlations of stock constraint,item constraint and cutting process constraint.A mathematical model of 1.5D cutting stock problem is established based on manufacturability for 1.5D cutting plans.A sequential heuristic 1.5D cutting stock method based on cost greedy is proposed.In this method,the compensation of metal coils and two-dimensional items is used to realize the size standardization of and metal coils items,which meets the requirement of process parameters in the special cutting stock process of metal coils.The strip combination generation technology based on FFD and iterative greedy algorithm in the width direction of metal coils is applied to construct various strips combination along the width direction of the metal coil corresponding to satisfying the selected 2D item set with the given constraint by 2D item candidate set.The cutting plan generation technology on metal coils based on dynamic programming algorithm can be used to combine the architecture of sequential heuristic to select a cutting plan with the least sum of stock cost and 1.5D setup cost.Finally,the feasibility and effectiveness of the proposed method are verified by the instances.For the 2D cutting stock problem in the cutting stock process,the special cutting stock process is considered that two-dimensional items are cut down from 2D stocks with guillotine cuts,combining the correlations of stock constraint,item constraint and cutting process constraint.A mathematical model of 2D cutting stock problem is established based on manufacturability for 2D cutting plans.A sequential heuristic 2D cutting stock method with combination of two types of staged cutting patterns is proposed.In this method,the compensation of 2D stocks and items is used to realize the size standardization of and 2D items,which meets the requirement of process parameters in the special cutting stock process of guillotine cuts.The staged patterns generation technology calls multiple times of dynamic programming algorithm to construct two types of different staged cutting patterns,and selects a staged cutting pattern with a larger value.To avoid the solution trapping into local optimum,the 2D item value correction method is used to correct value of each item based on generated the cutting pattern by the staged patterns generation technology.The 2D cutting plan generation technology can be used to combine the architecture of sequential heuristic algorithm to select a cutting plan with the least stock cost.Finally,the feasibility and effectiveness of the proposed method are verified by the instances.Finally,based on the above research on cutting stock method,the overall scheme and functional system of manufacturability oriented cutting stock technology under complex constraints are designed.The system of manufacturability oriented cutting stock technology under complex constraints is preliminarily established.Some technologies are integrated into a cutting stock system software of a company,and achieve good application results. |
