B题：矩形件排样程序实现.doc

矩形件排样程序实现(要求:只能由一个学生独立完成,不得抄袭)工业上经常需要在一块大板材上下料得到若干个小的矩形件,使得板材的利用率最高,即所剩余的边角料最少。例如在一块宽40、高15的矩形板材上,排列25块尺寸已知的小矩形,25块小矩形的尺寸如表1,板材的利用率达100%,如图1所示。图1一种排样方案表1小矩形的尺寸序号宽高112624736741025256647428469791045116412461363144515241684178618831963202621822235232524342524如果上述排样方案未知,即不知道图1的排法,那么如何将这25块小矩形按照某种次序排在一个大的板材上呢?目前这仍是一个世界难题。通常要求在一个排样图中,任何一个矩形件在不超出板材边界的情况下,按照一个排样方案(给定的次序)采用下列一些方法来安排实际矩形件的排列,对于一个排样方案(解),其中,,pi为矩形件的序号,ri为排样方式,ri=1表达将矩形件旋转90°,ri=0表达矩形件不旋转。将第i个矩形件安排在板材上的过程中,均不能再往下、往左移动,则称其满足BL条件(bottom-left-condition,BL-condition)。基于BL条件,有一种下台阶算法,具体步骤如下:将零件排放在板材的左下角,若则将其旋转90°后再排放,求出排放后所占板材的最大高度;将根据其排样方式置于板材右边最大高度处,向下向左移动,且向下移动优先(即原本已无法再向下移动,故开始向左移动,而在向左移动的过程中若发现又能继续向下移动,则先向下移动),直至无法向下向左移动为止(即接触到其他零件或板材边界),并求出此时的最大高度;反复上述过程,直至所有零件排放完毕,最后所得最大高度即为所需板材高度。其排样过程如图2所示,就好象下台阶一样,于是形象地称之为下台阶算法。图2下台阶算法的排样过程剩余矩形排样法是目前所提出的一种有效的排样算法,该方法记录了所有可利用的空间,更能合理地分配给待排样的矩形件,提高了每个排样方案的板材利用率,更接近最优排样方案。例如对于同一个矩形件序列进行排样,图3(a)中下方的空洞以往的排样算法都无法利用,矩形4只能被排到上方。而利用剩余矩形排样法可以很好的解决这个问题,它可以使矩形4充足利用下方的空间,如图3(b)。图3剩余矩形排样法的优越性剩余矩形排样算法用一个矩形数据集合来表达板材目前的剩余位置情况,任何未被排样的空间(包括孤立的缝隙),都在剩余矩形集合中表达,不会遗漏任何一个。而在每一个矩形件被排入前,都需根据这个剩余矩形集合中的数据来选择最为合理的位置进行排放。下面给出剩余矩形的具体形成方法(这里用矩形的左下角坐标和右上角坐标来确定这个矩形的位置):板材的左下角和右上角坐标分别为,于是开始时剩余矩形数据集中只有一个矩形为。当排入一个矩形件(宽高)后,需将剩余矩形数据集合中的每一个矩形都减掉此矩形件所占的位置。若此矩形件的左下角坐标为,且为横排(即矩形件不旋转90°),则每个剩余矩形都减掉与矩形件相交的部分。例如矩形减掉与矩形件相交的部分后,形成了四个新的剩余矩形为:按顺时针方向记录矩形。如图4所示。若为竖排(即矩形件旋转90°),计算方法类似。图4剩余矩形表达法依此类推,将矩形数据集中的所有剩余矩形都作如此操作,减去所排入矩形件所占位置,形成新的