资源描述：
《钢卷入库问题的离线算法.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,通过将其应用于某钢铁工厂
