文献类型：期刊文献

中文题名：有交货时间限制的大规模实用下料问题

英文题名：The Stock Cutting Problem in Large Scale within The Deadline

作者：王辉[1];朱珠[1];张志敏[1];鲁习文[1]

机构：[1]华东理工大学理学院数学系,上海200237

年份：2005

卷号：35

期号：7

起止页码：64

中文期刊名：数学的实践与认识

外文期刊名：Mathematics in Practice and Theory

收录：CSTPCD;;北大核心:【北大核心2004】；CSCD:【CSCD_E2011_2012】；

语种：中文

中文关键词：交货时间限制;下料问题;数学模型;DP贪婪算法;材料利用率

外文关键词：model; stock cutting problem; DP greedy algorithm

摘要：研究的是有交货时间限制的单一原材料下料问题(规模较大).对于一维下料问题,本文得到一个有各自交货时间的模型.针对该模型提出一种新的算法:DP贪婪算法.计算结果是总用料800根即可完成需求任务,材料利用率为99.6%.对于二维下料问题,在一维的基础上建立了二维的求解模型,运用我们自己设计的降维思想结合一维的DP贪婪算法,给出解决该模型的算法.计算结果是总用料451块即可完成需求任务,材料利用率位99.2%.算法设计时考虑了普遍的情况,所以算法在解决大多数实际下料问题,特别是大规模下料问题时是切实有效的.
This paper centers on the stock cutting problem of the single stock sheet within the deadline （of relatively large scale）. As for the one-dimensional cutting problem, the paper comes up with a model of mutual deadline, in allusion to which, a new algorithm is put forward, that is, DP greedy algorithm. And the solution is the task can be finished with a total use of 800 and the utility rate reaches as high as 99.6%. With regard to the two-dimensional cutting problem, based on tbe one-dimensional cutting problem we create a two-dimensional problem solving model with the idea of DP greedy algorithm guided by dimension-reducing principle. And the solution is that the task can be finished with only 451 with a utility rate of 99.2%. While designing the algorithm, we have considered the situation at large. Thus, the algorithm is feasible in solving most of the actual stock cutting problems especially in large scale.