钢卷入库问题的离线算法.pdf

钢卷入库问题的离线算法.pdf

ID:52240520

大小:134.77 KB

页数:7页

时间:2020-03-25

钢卷入库问题的离线算法.pdf_第1页
钢卷入库问题的离线算法.pdf_第2页
钢卷入库问题的离线算法.pdf_第3页
钢卷入库问题的离线算法.pdf_第4页
钢卷入库问题的离线算法.pdf_第5页
资源描述:

《钢卷入库问题的离线算法.pdf》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、2002年8月系统工程理论与实践第8期 文章编号:100026788(2002)0820108206钢卷入库问题的离线算法王小明,李建国(清华大学数学科学系,北京100084)摘要:在钢铁工厂车间,钢卷入库是一道非常重要的工序L在某钢铁厂解决实际问题的过程中,所有的1hi1钢卷的高度hi满足:<<,Pi(其中H为高度限制)L针对这一问题,我们设计了一种离线算5H3法L实际数据试验说明,该算法在解决钢卷入库问题时是可行的L通过大量的模拟数据试验表明,在一维1hi1装箱问题中,当所有物品高度满足条件(3):<<,Pi(其中

2、H为高度限制)时,该N0+1HN0-1算法相比于两种经典的离线装箱算法(FFD,BFD)效果要好L关键词:钢卷入库问题;离线装箱算法;启发式算法;大小搭配中图分类号:O224文献标识码:AaAnOff2lineAlgorithmforSteelCoilsPackingProblemWANGXiao2ming,LIJian2guo(DepartmentofMathematicalSciences,TsinghuaUniversity,Beijing100084,China)Abstract:Insteelfactorie

3、s,thepackingofsteelcoilsisveryimportant.Whensolvingapracticalprob21hi1lemofsomefactory,wefindthatallcoils'heightshisatisfy:<<,Pi(inwhichHisthe5H3heightlimit).Forthisproblem,anoff2linealgorithmisproposed.Practicaldatatestsshowthattheal2gorithmisfeasibleinsolvings

4、teelcoilspackingproblem.Moreover,agreatdealofdatasimulationtestsshowthat,thealgorithmisbetterthanthetwoclassicaloff2linebin2packingalgorithms(FFD,BFD)insolvingone2dimensionbin2packingproblemswhenallitems'heightssatisfythecondition(3).Keywords:steelcoilspackingpr

5、oblem;off2linebin2pacingalgorithm;heusiticalgorithm,arrangeinpairsorgroups1 引文在某钢铁工厂里,冷轧后的钢卷(圆柱形,工业上称之为冷卷)在热处理前,会在热处理车间的前库存放,等待入炉L前库中有许多垛位,但由于热处理的周期较长,并且等待热处理的冷卷的数量太多L为了节约垛位,允许钢卷重叠堆放,每层一个钢卷L当然由于库房的高度,地面的承受能力的限制,后续的装炉工序的要求,吊车工作的安全要求等等原因,堆放的高度和总重量必须有所限制L另外,出于安全方面的

6、考虑,钢卷必须按照从下到上半径逐渐减小的规则来堆放L这样,每个垛位上堆放的钢卷都呈A形(底宽顶窄,见图1)L钢卷入库问题在数学上,就是一个复杂的装箱问题L我们首先简要介绍一下装箱问题L假定L={a1,a2,a3,⋯,an}为给定的一个实数数组,每一个ai∈(0,1],b1,b2,⋯为一个由单位容积的箱子组成的无限序列L我们要求:每一个物品ai只能装入到唯一的箱子里,每一个箱子中的数字和不超过1,如何用最少的[4]单位容积的箱子,装下所有的物品,这就是经典一维装箱(BinPacking)问题,简称装箱问题,解决此类问题的

7、方法称为装箱算法La收稿日期:2001202228作者简介:王小明(1977-),江西丰城,硕士研究生,研究方向:装箱问题及排序问题.©1995-2005TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.第8期钢卷入库问题的离线算法109装箱算法又可分为在线的和离线的两种情况:·在线的 装入新到来的物品ai时,仅仅根据已装物品aj(1FjFi)的大小,而不考虑后面的物品的信息,并且不允许移动已经放好的物品L·离线的 在进行装箱前,所有物品的信息都知道L因此,装入任

8、何物品时,都要考虑其他所有物品的信息,使整体上达到最优L在我们处理的实际问题中,所有钢卷的高度hi,i=1,2,⋯,n满足:1hi1<<,Pi∈1,2,⋯,n}5H3图1 钢卷堆放示意图式中H为高度限制L此即条件(3)中N0=4的情况L针对所有物品高度满足条件(3)的情况,本文专门设计了一种离线装箱算法A,通过将其应用于某钢铁工厂

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。