下料问题解法

《下料问题解法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、有交货时间限制的大规模实用下料问题有交货时间限制的大规模实用下料问题朱珠,王辉,张志敏指导老师：鲁习文(华东理工大学理学院数学系,上海200237)摘要：本文讨论了有交货时间限制的大规模单一原材料下料问题。对于一维下料问题，本文提出一种新的算法：DP贪婪算法。在一维的基础上建立了二维的求解模型，运用降维思想结合一维的DP贪婪算法，给出解决该模型的算法。数值计算结果表明该算法对大规模下料问题是有效的。关键词：下料问题，DP，贪婪算法1、问题描述单一原材料下料问题.设这种原材料呈长方形，长度为,宽度为，现在需要将一批这种长方形原料分割成种规格的零件,所有零件的厚度均与原材料一致，但长度和宽度分

2、别为，其中。种零件的需求量分别为。下料时，零件的边必须分别和原材料的边平行。这类问题在工程上通常简称为二维下料问题。特别当所有零件的宽度均与原材料相等，即，则问题称为一维下料问题。一个好的下料方案是在生产能力容许的条件下，以最少数量的原材料，尽可能按时完成需求任务,同时下料方式数也尽量地小.2、一维下料问题2.1模型假设在充分了解并分析了实际情况后，我们对一维下料问题提出如下假设：（1）每天下料的数量受到企业生产能力的限制，在未完成需求任务前，每天下料的数量等于最大下料能力。（2）每个切割点处由于锯缝所产生的损耗不可忽略。（3）增加一种下料方式大致相当于使原材料总损耗增加。（4）每种零件有

3、各自的交货时间，若某零件无交货时间，则记该零件交货时间为无穷大。2.2一维单一原材料实用下料问题的模型根据公司要求，目标是既要所用材料最少，也要下料方式少。记：零件种类总数,：第种下料方式下料的根数，：下料方式的种类数，第i种下料方式的余料。借助函数，可得所用材料和采用的下料方式分别为：，借助模型假设中假设(3)：增加一种下料方式大致相当于使原材料总损耗增加。故可将双目标转化为单目标：5有交货时间限制的大规模实用下料问题由于每天下料的数量受到企业生产能力的限制，假设在天内各种下料方式的下料总根数分别为,,…,，零件的需求数量为，第种下料方式下料一次产生的零件的个数为。设是要求在天内完成的零

4、件集合，则必须满足：即天内需要完成的零件必须在前根原材料的切割中得到。根据上述分析，得到有时间限制的一维单一下料问题模型：s.t.其中：第种下料方式前天内下料总根数，：交货时间均等于的零件集合2.3模型求解对于该问题，因为可能的下料方式将随需要的零件种类数量成指数级增长，所以它是一个NP－Hard问题。这样对于大多数问题，一般方法无法得到最优结果或无法及时得到最优结果。因此对于大规模的一维下料问题，我们给出了结合动态规划和贪婪算法的新算法，称之为DP贪婪算法。基本思想是：对模型计算时，不用先得到一定数量的下料方案，而是在选取下料方案时就以数学模型中的目标和约束条件为基础来进行寻找。为了保证

5、尽量节省材料，应该尽量将比较大的零件先进行处理，并同时辅以长度小的零件，以保证单个原料的利用率尽量大。因此对每一个零件按照其长度大小依次给定处理顺序的权值。为了保证时间的要求，有要求的零件应该尽量优先处理，对每一个零件按时间紧迫度t依次给定一个处理顺序的权值。两者的结合将作为每一个零件动态规划初始权值。在决定了处理顺序后，首先利用贪婪思想，选取当前尚没有得到的零件集合中权值最大的一个进行处理。调用动态规划方法，得到一种下料方式，此方法里含有当前的零件，在得到此下料方式后，先尽可能按照此方式进行处理，以尽量减少下料方式数，然后再应用贪婪思想。依次类推，直到得到所有的零件。这样我们5有交货时间

6、限制的大规模实用下料问题将得到一种下料方案。如果此方案满足约束要求则停止处理，否则对权值进行调整，如果结果不能满足时间紧迫度的限制，则将优先权值步长直接调节到理论上限，随后通过二分查找的方法进行选择，如果材料利用率过低，则参照以上方法进行调节。而后重复上述过程，直到得到合理结果。算法描述：1.局部最优//计算当前单根利用率最大值，并得到一组可行下料方案FORI=1TO工件总种类数FORJ=原材料总长度DOWNTO0IF在J的位置已经有解FORK=第I件工件中未切割的数量DOWNTO1当前长度=J+第I件工件的长度*KIF当前长度位置尚未得到解THEN保存当前解ELSE对两个解进行比较选取较

7、优解FORI=材料长度DOWNTO1IF当前长度有解存在THEN返回解2.全局贪婪对所有需要的零件进行处理FORI=1TO工件种类总数WHILE如果当前种类还有剩余(按照权值大小依次处理)DO利用上述局部最优处理选取一种至少含有当前种类一根的最优解累加计算结果更新数据表格3.反复调整调整权值IF得到全局的解法不合理IF不能按时完成零件按规则加大优先权值ELSE浪费过于大按规则加大长度权值调用上述全局贪婪3、二维下料问题二