1. 研究目的与意义（文献综述）
近年以来，制造行业面临着越来越大的竞争与冲击，各企业纷纷在节省材料，提高材料利用率方面下功夫以降低成本，提高经济效益。优化排样，是提高材料利用率的重要方式之一。优化排样应用范围非常广泛。在工程应用领域中，型材和棒材下料、冲裁件排样、玻璃切割、报刊排版、家具下料、服装裁剪、皮革裁剪、造船、车辆和发电设备生产中都存在大量的下料问题[1]。从数学计算复杂性上讲下料排样问题属于np完全问题，存在“组合爆炸”[2]。由于下料排样问题的广泛存在，需要在可以接受的时间里得到问题的最优解或近似最优解，因此排样问题的研究具有深远的理论意义和现实意义[3]。国外有关下料排样问题的研究起步比较早。下料问题最早是由苏联人kantorovich[4]于1939年提出，其奠基性工作当属gilmore和gomory[5]在60年代的工作。
在研究排样算法的时候，当给定一组零件和原材料板，我们可能需要考虑排样对象几何和技术工艺方面的一些因素，这些因素会影响到问题的复杂性和算法的设计。
在几何特征方面，零件可以是比较规则的形状，简单的就像矩形零件，也可以是比较不规则的，甚至可以是高度不规则的。零件的几何轮廓可能是由直线构成，也可能是曲线，甚至零件内部有洞、切除部分等，而且切除部分也可能是规则的或者不规则的。同样，原材料板块也可以是规则的矩形，也可以是高度不规则的特殊形状，甚至手机带有缺陷的区域[6[。
2. 研究的基本内容与方案
基于以上对排样优化的介绍与研究现状，可知，优化排样设计对于制造业有着非常重要的意义，好的排样方案能够很好的提高材料的利用率，降低企业生产的成本，从而提高效益，增强市场竞争力。而排样问题属于np完全问题，在求解上有着非常大的计算难度，迄今未有彻底解决的方法，于是人们寻求各种启发式算法，去求得排样问题的近似最优解或可行解。本文基于遗传算法，对汽车零部件进行排样优化设计。研究的基本内容有：
(1) 研究一模一腔时级进模的排样优化，在考虑最小搭边值时，实现材料的最大利用率。
(2) 研究一模两腔时级进模的排样优化，在考虑最小搭边值时，实现材料的最大利用率。
3. 研究计划与安排
第1周 （7 学期第20周） 确定毕业设计题目、毕业设计任务书(相关参数)、校内资料收集
第2周 （8 学期第1周）方案构思、文献检索、完成开题报告
第3～4周 （8学期第2-3周）外文翻译、资料再收集
4. 参考文献（12篇以上）
[1]贾志欣.排样问题的的研究现状与趋势[j].计算机辅助设计与图形学学报，2004，16（7）:890-897.[2]刘德全，滕弘飞.矩形件排样问题的遗传算法求解[j].小型微型计算机系统，1998,19（12）:20-25.
[3]黄红兵.矩形件下料优化排样的遗传算法[d].桂林:广西师范大学，2002.
[4]kantorovich l v.mathematical methods of organizing and planning production[j].management science.1960,6:363-366.
