In order to solve the problems such as low production efficiency in large thin-walled frame parts machining process and difficulty in ensuring accuracy due to too much turning over times in the fuselage processing,marine diesel engine cylinder block key hole processing and clamping scheme optimization method was proposed based on graph theory.The processing characteristics of the key hole on the diesel engine cylinder were analyzed,and the processing scheme was determined;VERICUT software was used to simulate the whole machining process,and an optimal clamping path scheme was designed based on graph theory considering constraints;a certain type of diesel engine was used as the research object.The results show that by using the optimized scheme,the clamping time and processing time of the engine cylinder are effectively reduced by 17.24%,and the processing efficiency is improved.