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

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

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

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

2.1设计的基本内容

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

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

（1）根据生产实践的要求提出要解决的分割问题，对同尺寸矩形玻璃分割的研究现状及其研究成果进行分析，论证本文研究的必要性。

（2）对现有的同尺寸矩形玻璃的分割算法进行研究，进一步分析和总结，同时对国内外学者对同尺寸矩形玻璃的分割算法的技术思想进行研究,选择合适的算法作为本课题研究的主要算法。

（3）在现有算法的基础上，设计出新的算法，解决本课题研究所涉及的分割问题。详细介绍算法的基本设计思想、具体设计过程、算法的C语言描述、算法特点以及实例用于验证本文解决方法的求解说明。在C语言开发环境下，开发出同尺寸矩形玻璃分割系统，用于验证本文解决方法的可行性。

（4）通过实验计算并分析测试本文提出的算法，得到对生产实践具有指导意义的结论。