Evolutionary Algorithm's Application On Cutting Stock Problems

Layout problem is a kind of classical combinatorial optimization problem. It has a wide range of application in a wide field. Layout problem means putting some objects on a specified space (or plane) within reason, satisfying some necessary restrictions, and reaching some optimal aim. The result of layout has an important impact on rationality, economization and security of production.For circle packing on a Roll of Material, this paper puts forward a new method: oblique arrangement based on interlaced arrangement, which improves utilization percent of material. Because recently evolutionary algorithm has got a marked achievement on engineering, manufacturing, automation, business and finance, this paper adopts evolutionary strategy, one kind of evolutionary, to try to settle two kind of one dimensional layout problem. They are single stock length cutting stock problem (CSP) and CSP that items can be welded.For single stock length CSP, we propose a compound ES, which takes item list as chromosome, and just relies on individual mutation and elitist election to realize colony evolution. In addition, after a process of evolution, we add a search operator to enhance local search capability of ES.In the second problem, ES is combined with a linear aggregation method. Its fitness function synthetically considers maximizing the usage rate of material and minimizing the time of soldering the items, satisfying practice.Our work can be used for reference for other layout problems.