计算机辅助排样,又称为CAN(Computer Aided Nesting),是广泛应用的计算机辅助技术之一。CAN广泛的应用于电气机械制造业、服装制造业、家具制造业、交通运输设备制造业等行业。CAN的目的在于寻求某种优化的布局方式使平面区域的面积利用率较高、减少排样工作量和化简切割工艺,达到降低产品成本的目地,最终增强企业在同行业的竟争力。矩形排样问题是计算机辅助排样的一个重要分支。由于矩形毛坯优化下料方案不仅通过提高材料利用率节约生产成本,而且可以通过简化切割工艺、缩短计算时间,提高生产效率,所以对矩形毛坯优化排样问题的研究具有深远的理论和实际意义。并且对于不规则零件的排样问题,可通过计算机的图形处理技术将一个或几个零件套排在一个包容矩形中,然后对包容矩形进行排样,从而转化为矩形件排样问题。由于排样问题要考虑到的因素有三个方面:材料利用率、切割工艺和计算时间。在提高材料利用率方面,本文采用四块排样方式和线性规划相结合,保证了较高的材料利用率。另外,由于排样问题是NP难度问题,如果不对排样方式加以必要的限制,不仅计算时间难以接受,排样方式也十分复杂。本文采用了四块排样方式:先用一条竖直或水平剪切线把板材分为左右或上下两块,然后每块分别用垂直于剪切线的两条直线将其分为两块。每个区域中包含一个由同尺寸毛坯组成的均质块,板材中最多含四种毛坯。实现了四块排样方式生成算法FBPFRB,它基于背包问题和动态规划算法,可以求解矩形毛坯无约束二维剪切排样问题。并且用二十道例题做了对比实验。然后本文根据线性规划的原理把四块排样方式生成算法FBPFRB和线性规划结合后的算法称为四块排样方案生成算法FBPFRBLP,用来求解矩形毛坯下料问题。并且用一道例题做了对比实验。由于四块排样方式由条带组成,适合剪冲下料工艺的需要;可以单独应用匀质块排样方式,简化下料过程的管理,缩短生产周期;和线性规划结合,在求解最优排样方案时,时间效率较高,生成每种排样方案中的毛坯种数最多不超过四种,排样方式简单,能在一定程度上简化切割工艺,提高下料效率,有实际应用价值。本文算法分为两部分:第一部分为四块排样方式生成算法FBPFRB,其步骤如下:第一步:求解规范尺寸;第二步:用动态规划算法确定各种尺寸的匀质块中含每种毛坯的最大数量值;第三步:确定四块排样方式的最大价值V并生成排样方式。第二部分将FBPFRB和线性规划算法LP结合形成四块排样方案生成算法FBPFRBLP,其主要步骤如下:第一步:给出一个初始基可行解;第二步:根据用单纯形法求解线性规划问题所得到的当前基对应的检验数,确定每种毛坯当前价值系数;第三步:调用FBPFRB算法,根据毛坯的当前价值系数,生成一个四块排样方式;第四步:如果能够使解改善,就将生成的四块排样方式引入当前基并转第二步;否则转第五步;第五步:输出排样方案。采用文献中报道的两组例题进行对比实验。第一组是矩形毛坯无约束二维剪切排样实验,即确定毛坯在一张板材上的排列方式,使板材总价值达到最大,并且对每种毛坯在板材中出现的次数没有约束。采用算法FBPFRB生成了每道例题的最优四块排样方式,并与二阶段方式和三块排样方式进行比较,结果表明四块排样方式的平均材料利用较高。第二组是矩形毛坯下料实验,要求切出全部所需毛坯,使所使用的板材总成本最小。实验结果表明:当只允许使用均质条带时,使用四块排样方式,可以比三块、二阶段、T形和三阶段等排样方式取得较高或相当的材料利用率;当允许使用普通条带时,虽然采用四块排样方式比采用T形、两段、三阶段等排样方式的材料利用率稍低,但能够有效简化排样方案。实验结果还表明,算法FBPFRBLP的计算时间可以满足实际应用的要求。由于四块排样方式较为简单,能够有效简化切割下料工艺,所能达到的材料利用率和采用其它排样方式也相距不远,因此,四块排样方案生成算法是一种值得推荐的算法。