有交货时间限制的大规模实用下料问题朱珠,王辉,志敏指导老师：鲁习文(华东理工大学理学院数学系,200237)摘要：本文讨论了有交货时间限制的大规模单一原材料下料问题。

对于一维下料问题，本文提出一种新的算法：DP 贪婪算法。

在一维的基础上建立了二维的求解模型，运用降维思想结合一维的DP 贪婪算法，给出解决该模型的算法。

数值计算结果表明该算法对大规模下料问题是有效的。

关键词：下料问题，DP ，贪婪算法 1、问题描述单一原材料下料问题. 设这种原材料呈长方形，长度为L ,宽度为W ，现在需要将一批这种长方形原料分割成m 种规格的零件, 所有零件的厚度均与原材料一致，但长度和宽度分别为),(,),,(11m m w l w l ，其中m i W w L l w i i i ,,1,, =<<<。

m 种零件的需求量分别为m n n ,,1 。

下料时，零件的边必须分别和原材料的边平行。

这类问题在工程上通常简称为二维下料问题。

特别当所有零件的宽度均与原材料相等，即m i W w i ,,1, ==，则问题称为一维下料问题。

一个好的下料方案是在生产能力容许的条件下，以最少数量的原材料，尽可能按时完成需求任务, 同时下料方式数也尽量地小.2、一维下料问题2.1 模型假设在充分了解并分析了实际情况后，我们对一维下料问题提出如下假设：（1）每天下料的数量受到企业生产能力的限制，在未完成需求任务前，每天下料的数量等于最大下料能力。

（2）每个切割点处由于锯缝所产生的损耗不可忽略。

（3）增加一种下料方式大致相当于使原材料总损耗增加%08.0。

（4）每种零件有各自的交货时间，若某零件无交货时间，则记该零件交货时间为无穷大。

2.2 一维单一原材料实用下料问题的模型根据公司要求，目标是既要所用材料最少，也要下料方式少。

记m ：零件种类总数,i x ：第i 种下料方式下料的根数，k ：下料方式的种类数，:i δ第i 种下料方式的余料。

借助函数⎩⎨⎧=01)(i x signal 00=>i i x x ，可得所用材料)(1x f 和采用的下料方式)(2x f 分别为：∑==k i i i x x f 11)(δ，()∑==ki i x signal x f 12)(借助模型假设中假设(3)：增加一种下料方式大致相当于使原材料总损耗增加%08.0。

故可将双目标转化为单目标：()⎪⎪⎭⎫ ⎝⎛⎪⎭⎫ ⎝⎛-⨯+⨯=∑∑==1%08.01)(min 11k i i ki i i x signal x x f δ由于每天下料的数量受到企业生产能力max 的限制，假设在d 天各种下料方式的下料总根数分别为1y ,2y ,…,k y ，零件j 的需求数量为j n ，第i 种下料方式下料一次产生的零件j 的个数为ij a 。

设F 是要求在d 天完成的零件集合，则必须满足：⎪⎪⎩⎪⎪⎨⎧⋅≤∈=∑∑==max (11d y F j n y a k i i j ki i ij ）即d 天需要完成的零件必须在前max ⋅d 根原材料的切割中得到。

根据上述分析，得到有时间限制的一维单一下料问题模型： ()()⎪⎪⎭⎫ ⎝⎛⎪⎭⎫ ⎝⎛-⨯+⨯=∑∑==1%08.01min 11k i i ki i i x signal x x f δs.t.()()()⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎨⎧==≥<=≤≤∈==⋅≤==∑∑∑===),,1;,,1(0,);,,1(,,1max ,...,1,,,1,1,1m j k i y x d d k i x y y S j n y a m j d y m j n x a j j l j j j d i i j l i d i d i d j k i d i ij j k i d i j k i i ij 且为整数 其中j d i y ,：第i 种下料方式前j d 天下料总根数，j d S ：交货时间均等于j d 的零件集合2.3 模型求解对于该问题，因为可能的下料方式将随需要的零件种类数量成指数级增长，所以它是一个NP －Hard 问题。

这样对于大多数问题，一般方法无法得到最优结果或无法及时得到最优结果。

因此对于大规模的一维下料问题，我们给出了结合动态规划和贪婪算法的新算法，称之为DP 贪婪算法。

基本思想是：对模型计算时，不用先得到一定数量的下料方案，而是在选取下料方案时就以数学模型中的目标和约束条件为基础来进行寻找。

为了保证尽量节省材料，应该尽量将比较大的零件先进行处理，并同时辅以长度小的零件，以保证单个原料的利用率尽量大。

因此对每一个零件按照其长度大小依次给定处理顺序的权值。

为了保证时间的要求，有要求的零件应该尽量优先处理，对每一个零件按时间紧迫度t 依次给定一个处理顺序的权值。

两者的结合将作为每一个零件动态规划初始权值。

在决定了处理顺序后，首先利用贪婪思想，选取当前尚没有得到的零件集合中权值最大的一个进行处理。

调用动态规划方法，得到一种下料方式，此方法里含有当前的零件，在得到此下料方式后，先尽可能按照此方式进行处理，以尽量减少下料方式数，然后再应用贪婪思想。

依次类推，直到得到所有的零件。

这样我们将得到一种下料方案。

如果此方案满足约束要求则停止处理，否则对权值进行调整，如果结果不能满足时间紧迫度的限制，则将优先权值步长直接调节到理论上限，随后通过二分查找的方法进行选择，如果材料利用率过低，则参照以上方法进行调节。

而后重复上述过程，直到得到合理结果。

算法描述：1. 局部最优//计算当前单根利用率最大值，并得到一组可行下料方案FOR I = 1 TO 工件总种类数FOR J = 原材料总长度 DOWNTO 0IF 在J 的位置已经有解FOR K = 第I 件工件中未切割的数量 DOWNTO 1当前长度 = J + 第I 件工件的长度*KIF 当前长度位置尚未得到解 THEN保存当前解ELSE 对两个解进行比较选取较优解FOR I = 材料长度 DOWNTO 1IF 当前长度有解存在 THEN返回解2. 全局贪婪对所有需要的零件进行处理FOR I = 1 TO 工件种类总数WHILE 如果当前种类还有剩余(按照权值大小依次处理) DO利用上述局部最优处理选取一种至少含有当前种类一根的最优解累加计算结果更新数据表格3. 反复调整调整权值IF 得到全局的解法不合理IF 不能按时完成零件 按规则加大优先权值ELSE 浪费过于大 按规则加大长度权值调用上述全局贪婪3、二维下料问题二维情况下，假设在矩形原料切割时采用正交切割，切割时的锯缝可以是直的也可以是弯的；不允许零件旋转；而且切割所引起的锯缝损耗忽略不计。

3.1 模型建立假设共有k 种不同下料方式，第i 种下料方式下料的总块数记为()k i x i ,...,1=，并记第i 种下料方式产生零件j 的个数记为ij a (如果某零件j （M j ≤≤1）满足W w L l j j >>或，则0≡ij a （k i ,,1 =）)，记第i 种下料方式下料一次产生的余料（即料头）为()k i i ,...,1=δ。

二维单一原材料下料模型的建模思想与一维单一原材料下料模型类似。

得到如下有交货时间限制的二维下料问题的数学模型：()()⎪⎪⎭⎫ ⎝⎛⎪⎭⎫ ⎝⎛-⨯+⨯=∑∑==1%08.01min 11k i i ki i i x signal x x f δs.t. ()⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎨⎧==≥<=≤≤===⋅≤==+∑∑∑===+),,1;,,1(0,);,,1(),,1(),,1(max ,...,1)(,,,1,1,1,m j k i y x d d k i x y y m j n y a m j d y m j n x a a j j l j j d i i j l i d i d i j k i d i ij j k i d i j ki i ij m j i 且为整数 3．3 模型求解目前，解有交货时间限制的二维下料问题的常用方法是启发式算法，但是这种方法在大规模的下料问题中并不能将问题的规模降到一个合理的围。

对于大规模的二维下料问题，本文给出新的求解方法。

先利用降维思想将二维下料问题化为两个一维下料问题，对每一个一维下料问题，再使用本文一维下料问题的DP 贪婪算法进行计算，再将两者的结果结合起来，得到最终的结果。

本文采用的降维思想为：第一步，先考虑长度（或宽度）这一维(以下采用先考虑宽度为例进行说明)，将宽度相同的零件归为一类，对每一类,假设各自存在与该类等宽与原母板等长的母板。

这样，每一类零件宽度与各自的母板宽度相等，这就转化为一维下料问题。

故可借助一维下料模型的算法解出原母板在长度维上的切割方式。

这种方式找到的是长度维上的局部近似最优。

第二步，考虑宽度（或长度）这一维。

由上一步，我们可以得到每一宽度各自所需的母板根数，可将每一类宽度视为一维切割中一个零件的长度，将每一类所需的根数作为零件的下料任务，原母板的宽度作为现在一维切割原料的长，这样又得到一个一维下料问题，同样借助一维下料模型的解法来获得局部近似最优解。

经过上述两步后，二维下料问题就转化为了两个一维下料问题，在借助一维下料问题的求解算法得到两个局部最优解后，可以通过两者的结合得到最终解。

算法的基本思想是：首先比较长的种类和宽的种类，从中选取种类比较少的一个作为第一次降维考虑的基础(在不影响一般性的前提下，以下假设宽度种类较少来进行描述)。

按照宽度对所有零件进行分类，然后假设已经有各种宽度的模板足够多，而模板的长和原材料的长相等。

这样在接下来的切割过程中将不考虑跨度问题，这样将完全变为一维下料问题。

为了得到更优的解应该优先处理宽度最宽的一类，所以依据宽度给定每一类零件一个权值。

同时要考虑到交货时间的要求，交货时间比较短的零件应该优先处理，所以依据交货时间给定每一类零件一个权值，两者的结合作为处理顺序的权值。

在接下来的处理中，应该选取当前未处理集合中权值最大一类宽度的零件借助一维下料算法进行处理，以得到需要此类宽度模板的数量。

为了提高原材料利用率，当一类宽度零件处理完毕后，如果有一些余料，将采用动态规划方法，在利用率高的要求下将其它宽度的零件尽量用这些余料来获得，直到剩下的余料不能再被使用为止。

重复这个过程，可以得到每一类宽度的模板需要多少数目，同时得到一种下料方案。

接下来，将每一种宽度作为一维下料问题中零件的规格，而每一类宽度需要的数目就是一维下料问题中零件的数量要求，而此次一维下料问题的原材料长度是二维下料问题中原材料的宽度，对于这个一维下料问题借助上文的算法对其进行处理，得到一种下料方案。

将第一次得到的一维下料方案和第二次得到的一维下料方案按顺序进行组合，即得到这个问题的下料方案。