有交货时间限制的大规模实用下料问题 摘要：本文讨论了有交货时间限制的大规模单一原材料下料问题
对于一维下料问题，本文提出一种新的算法：DP 贪婪算法
在一维的基础上建立了二维的求解模型，运用降维思想结合一维的DP 贪婪算法，给出解决该模型的算法
数值计算结果表明该算法对大规模下料问题是有效的
关键词：下料问题，DP，贪婪算法1、问题描述单一原材料下料问题
设这种原材料呈长方形，长度为,宽度为，现在需要将一批这种长方形原料分割成种规格的零件, 所有零件的厚度均与原材料一致，但长度和宽度分别为，其中
种零件的需求量分别为
下料时，零件的边必须分别和原材料的边平行
这类问题在工程上通常简称为二维下料问题
特别当所有零件的宽度均与原材料相等，即，则问题称为一维下料问题
一个好的下料方案是在生产能力容许的条件下，以最少数量的原材料，尽可能按时完成需求任务, 同时下料方式数也尽量地小
2、一维下料问题2
1 模型假设在充分了解并分析了实际情况后，我们对一维下料问题提出如下假设：（1）每天下料的数量受到企业生产能力的限制，在未完成需求任务前，每天下料的数量等于最大下料能力
（2）每个切割点处由于锯缝所产生的损耗不可忽略
（3）增加一种下料方式大致相当于使原材料总损耗增加
（4）每种零件有各自的交货时间，若某零件无交货时间，则记该零件交货时间为无穷大
2 一维单一原材料实用下料问题的模型根据公司要求，目标是既要所用材料最少，也要下料方式少
记：零件种类总数,：第 种下料方式下料的根数， ：下料方式的种类数，第 i 种下料方式的余料
借助函数，可得所用材料和采用的下料方式分别为：，借助模型假设中假设(3)：增加一种下料方式大致相当于使原材料总损耗增加
故可将双目标转化为单目标：由于每天下料的数量受到企业生产能力的限制，假设在 天内各种下料方式的下料总根数分别为,,…,，零件 的需求
