【作者】 凌少东；

【导师】 曹炬；

【作者基本信息】 华中科技大学 ， 应用数学， 2006， 硕士

【摘要】 排样问题是一类经典的组合优化问题,在现实生产中具有广泛的应用。排样问题是将待排样物体合理的摆放在指定的空间(平面)中,满足必要的约束,并且达到某种最优目标。布局结果的好坏对相关行业生产的合理性、经济性和安全性等指标有重大影响。针对卷料上的圆形件下料问题,本文提出了基于品排的斜排,有效的提高了原材料的利用率。基于遗传算法等进化算法在工程设计、制造业、自动控制和商业金融等领域的广泛应用和取得的显著效果,本文采用另一种进化算法--进化策略来尝试解决两类一维下料问题。它们分别是单型材长的一维下料问题(Cutting Stock Problem,CSP)和可接的一维下料问题。对于单型材长的CSP,提出了基于进化策略的复合算法。它采用零件序列作为染色体,只采用单个体的变异和精英选择机制来实现进化。另外,在一次进化过程完成后,增加一个搜索算子来增强ES的局部搜索能力,弥补了ES在这方面的缺陷。对于可接的CSP,ES结合了排序聚合法。它的适应值函数综合考虑了型材利用率最大化和焊点数最小化,满足了企业的实际要求。我们的工作对于二维和其他的排样问题具有一定的借鉴价值。更多还原

【Abstract】 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.更多还原