Abstract: In order to resolve the contradiction of time efficiency and material utilization ratio in large-scale parts cutting stock problem(LPCSP),a grouping optimization method based on parts' cutting stock characteristics is proposed.By analyzing the association of parts' cutting stock characteristics with graph theory,the weighted undirected graphs of parts' similarity association and parts' combination association are established.Then,with cutting stock characteristics of parts samples as grouping constraints,the adaptive grouping of parts is accomplished by segmenting MST of the weighted undirected graph.The LPCSP is decomposed into several small-scale parts cutting stock problems(SPCSP).Before parts nesting,the SPCSPs are sorted in descending order according to material utilization ratio.For every pair of two adjacent SPCSPs,a dynamic compensation strategy is adopted to adjust parts in different groups.Finally,the result of the LPCSP is obtained by combining all the results of the SPCSPs.The experimental results validate the feasibility and effectiveness of the proposed method.