1. 研究目的与意义（文献综述）

切割问题是在现实生活中经常能够遇到的一类问题。最早关于切割（gsp）问题的研究开始于1939年，俄国经济学家kantorovich建立了第一个一维切割模型，但在这个领域首先取得较为重要的开创性发展的工作则是由gilmore和gomory完成。他们提出用列生成技术求解一维csp,并对二维csp问题进行了开创性探讨。由于当时计算工具的限制，并未引起人们足够的重视。直至70年代，由于高速计算机的出现以及借助于计算机的现代化技术诸如线性规划、运筹学理论的发展，使得csp问题的研究有可能付诸于生产实践，二维切割问题重新引起国内外学者的兴趣，这个领域的研究日趋活跃，已取得了不少研究结论和成果。从那以后，这个领域不同应用研究的文章数量迅速增长，涉及面不断拓宽，不断在代表不同学科的杂志期刊上发表，各种切割模式以及各种求解方法迅速出现并蓬勃发展。

随着人民生活水平的提高，人们对各种装饰材料的需求大大增加，尤其是玻璃行业的快速发展使加工行业越来越受到人们的重视；但是，国内大多数企业切割排版主要还是依靠人工来实现，这样必然会造成工作效率低以及材料浪费严重等后果，企业的发展必然会受到限制。在这种情况下，产生了许多新兴的高科技的产物，其中计算机辅助排样（can）就是最重要的产物之一。目前，计算机辅助排样已经被广泛地应用于线材、卷材和板材的分割排样，它通过提供高质量的分割排样方案，节约原材料，降低产品成本，从而达到提高经济效益的目的。

目前，已有很多国内外学者在研究同一尺寸的玻璃单一排样问题，为了提高材料的利用率，提出了许多有用的算法。但是，现有的算法还存在着一些问题没有得到完善，最优化排样的问题没有得到最好的解决。例如，用分支定界算法解决矩形毛坯单一排样问题，所生成的排样方式考虑了切割工艺化简问题，但所采用的算法在毛坯尺寸与板材尺寸相差较大时，需要较长的计算时间并且内存需求很大，以至于实验计算时不得不抛弃了对部分问题的求解；有的算法非常有效，但从下料工艺角度考虑，所生成的排样方式不是最简单的排样方式，不利于在实践中加以应用，等等。

2. 研究的基本内容与方案

2.1设计的基本内容

本文主要完成在同尺寸矩形玻璃分割中做出最优化的算法处理，并在保证材料利用率最高的前提下，生成废料最少的分割方式。

本文主要设计内容从三个方面进行，首先进行理论研究，然后进行应用研究开发，最后通过大量的例题测试和分析，得出一些对指导生产实践有益的结论,设计的基本内容主要如下:

3. 研究计划与安排

第1-4周：查阅相关文献资料，明确研究内容，了解研究所需基础资料。确定方案，完成开题报告；

第5-6周：翻译英文资料，学习c语言编程开发等相关知识；

第7-8周：分析玻璃分割最优化算法的设计方法。运用所学的软件设计理论，完成整个系统的前期设计工作，进行系统的总体设计；

4. 参考文献（12篇以上）

[1] 杨少杰, 崔耀东. 同尺寸矩形毛坯排样算法[j]. 桂林理工大学学报, 2012, 32(4):628-630.

[2] 孟繁桢, 张庆翠. 用遗传算法求解最优切割方法[j]. 应用科学学报, 2000, 18(3):276-279.

[3] 杨振东. 基于数控的玻璃最优化切割的研究[d]. 山东科技大学, 2003.