CPGEA: a grouping genetic algorithm for material cutting plan generation

Construction firms specializing in large commercial buildings often purchase large steel plates, cut them into pieces and then weld the pieces into H-beams and other construction components. We formalize the material ordering and cutting problem faced by this industry and propose a grouping genetic algorithm, called CPG_EA, for efficiently controlling the relevant costs. We test the quality of CPG_EA in various ways. Three sets of simulated problems with known optimal solutions are solved using CPG_EA, and the gap between its solutions and optimal solutions is measured. The same problem sets are also solved with an expert system and a multi-start greedy heuristic. CPG_EA solutions are found to be consistently lower cost than the competing methods. The difference in solution quality is most pronounced for difficult problems requiring multiple identical plates in the optimal solution. CPG_EA is also tested using data from actual construction projects of a company faced with this problem. Since an optimal solution for the problems is not available, a lower bound is created. For the historical problems tested, the average percent difference between CPG_EA solutions and the lower bound is 0.67%. To put this performance in context, the results of solving these problems with an expert system and using experienced engineers is also reported. Of these three methods, CPG_EA achieves the best performance and the human experts the worst performance.