钢坯入库路径优化模型与算法.pdf

第19卷．第12期计算机技术与发展V01．19No．12
2009年l2月0P1兀RTECHNOIOGYANDDEVEL0PMENTDec．2009

钢坯入库路径优化模型与算法

陈小文，杨静，杨观赐2
(1．贵州大学计算机科学与技术学院，贵州贵阳550025；
2．贵州大学教育部现代制造技术重点实验室，贵州贵阳550025)

摘要：在钢铁工厂的车间里，钢坯入库是一道非常重要的工序，它可归结为装箱问题。文中根据某钢厂的实际情况建立
了相应的数学模型，以减少天车的行走距离，提高库房的利用率。通过分析天车行走总距离与钢坯入库顺序的关系．提出
并论证了单存储区的最小入库序列所满足的性质，并利用该性质设计了多存储区的入库算法。多组模拟实验数据测试表
明，单存储区测试结果验证了最小入库序列性质的正确性，多存储区测试结果表明了文中算法可大量缩短天车行走总距
离和提高库房利用率。
关键词：装箱问题；可变路径；固定路径；最小入库序列
中图分类号：0224；TP391文献标识码：A文章编号：1673—629X(2009)12—0196—05

ModelsandAlgorithmsofPathOptimizationforLoadingofSteel

CHENXiao-wen。YANGJing，YANGGuan．ci
(1．Sch．ofInstituteofComputerScieaaceandTechnology，GuizhouUniversity，Guiyang550025，China；
2．MinistryofEducationKeyLaboratoryofAdvancedManufacturingTechnology．Guizhou
University，Guiyang550025，China)

Abstract：Insteelfactories．幽eloadingofsteelisaveryimportantprocessanditcanbeattributedtobin—packingproblan．Toreducethe

mobiledistanceofcraneandimprovetheutilizationofwarehouse，amodeltosolvethisproblemisestablishedaccordingtotheactualsitua·

tioninasteelplant．Basedonthismodel，analysingthecontactsbetweenwalkingdistanceofcraneandstorageordersofsteel，aproperty

whichtheminimalloadingsequencesofsingle—storage一~re．amustsatisfyisputforwardandproved．thenakindofloadingalgorithmba-

sisofthatpmpertyfOrmulti—storage—areaisproposed．Thetestresultsofsingle—storage—areaareverifiedthatcorrectnessofthe

propertyandthetestresultsofmulti—storage—areashowthatmealgorithmcangreatlyreducethecranewalkingdistancemadimprove

theutilizationrateofthewarehouse．

Keywolds：binpacking；vailablepath；fixedpath；minimalloadingsequellees

O引言于库房的高度、地面的承受能力等其它因素的限制，每
在某钢铁工厂车间里，钢条通过连铸线的切割以一堆的最大叠放层数不能超过l1层，所有的钢坯宽度
后，按其切割长度与钢号的不同分为多种不同类型钢与存放区的宽度相同。
坯。在生产过程中，需要在库房中找到一个合适的位
置，用天车将其调入库房进行临时存放。合格品库房
分为六个相同长度的存放区间，按照离火车道的远近
分别命名为1到6区(见图1)。钢坯在库房中的摆放，
必须遵循同钢号同长度的钢坯摆放在同一堆上，且由
图1库厉示意图
深入研究钢坯入库问题，同时将其抽象简化，发现
收稿日期：2009—03—21；修回日期：2009—06—24
它在数学上是一个复杂的装箱(BinPacking)问题l_1J。
基金项目：国家自然科学基金项目(90718009)；上海高可信计算实
在解决此类问题时，该问题又分为“在线”和“离线”两
验室开放项目；贵州省科学技术基金(黔科合J字(2oo9，2123))
作者简介