Material Cutting Plan Generation Using Multi-Expert and Evolutionary Approaches

Firms specializing in the construction of large commercial buildings and factories must often design and build steel structural components as a part of each project. Such firms must purchase large steel plates, cut them into pieces and then weld the pieces into H-beams and other construction components. The details of the order and the production operation are specified in the "cutting plan." This dissertation focuses on solving this "cutting plan generation" problem with the goal of minimizing cost.

Two solution approaches are proposed in this dissertation: a multi-expert system and an evolutionary algorithm. The expert system extends the field by relying on the knowledge of multiple experts. Furthermore, unlike traditional rule-base expert systems, this expert system (XS) uses procedural rules to capture and represent experts' knowledge. The second solution method, called CPGEA, involves development of an evolutionary algorithm based on Falkenauer's grouping genetic algorithm.

A series of experiments is designed and performed to investigate the efficiency and effectiveness of the proposed approaches. Two types of data are used in the experiments. Historical data are real data provided by a construction company. Solutions developed manually and implemented are available. In addition, simulated data has been generated to more fully test the solution methods. Experiments are performed to optimize CPGEA parameters as well as to compare the approaches to each other, to known solutions and to theoretical bounds developed in this dissertation.

Both approaches show excellent results in solving historical cases with an average cost 1% above the lower bound of the optimal solution. However, as revealed by experiments with simulated problems, the performance decreases in cases where the optimal solution includes multiple identical plates. The performance of the XS is affected by this problem characteristic more than that of CPGEA. While CPGEA is more robust in effectively solving a range of problems, the XS requires substantially less processing time. Both approaches can be useful in different practical situations.