约束入库问题模型与算法研究-控制理论与应用.PDF

第 20卷第 1期 控 制 理 论 与 应 用 Vo1．20No．1 2003年 2月 ControlTheory Applications Feb．2003 文章编号 ：1000—8152(2003)01—0150—03 约束入库 问题模型与算法研究 刘志新，李建国，谢金星 ，邢文 (清华大学 数学科学系 ，北京 100084) 摘要 ：对某冷轧厂冷卷约束入库 问题建立数学模 型，归结为有约束的装箱 问题 (binpacldIlg)，设计带 匹配权值 的bestfit算法实现优化入库 ．该算法简便易行 ，效果 良好 ，是求解一类约束入库 问题的有效算法 ．计算实例说 明了 模型的合理性与算法的有效性 ． 关键词：约束入库 ；装箱问题 ；bestfit算法 中图分类号 ：0224 文献标识码 ：A M odeland algorithm ofsolvingrestricted loadingproblem LIU Zhi—xin，LIJian—guo，XIE Jin—xing，XING W en—xun (DepartmentofMathematics，TsinghuaUniversity，Beijing100084，China) Abstract：W ith hteanalysisofloadingprocessna drestriction forasteelrolling factory，amodelofbinpackingisbuiltna d abestfitalgorithm wim matchingweightisdesigned．Thealgorithm iseasytocarryna dhasfineeffect．SOitcan solveakind ofrestrictedloadingproblem ．Th eresultsofhtecomputational nistance show htathtemod elisreasonablena dhtealgorithm is effce tive． Keywords：restrictedloading；bni packing；bestfitalgorithm 1 引言 (Introduction) 厂前库采用冷卷叠放的存储方式 ，为了充分利用前 现代企业生产 中，仓储管理在生产流程 中占有 库空间，保证 同一库位的冷卷 同炉热处理，需要采用 重要地位，合理入库是仓储管理的前提 ．一类入库 问 优化算法为人库冷卷指定库位 ． 题可 以归纳为线装箱 问题来解决 ．装箱 问题是优化 冷卷 以在线方式到达前库入 口，在线是指为当 领域 的经典 NP问题 ，其 中的在线 问题 已有较多研 前冷卷选择库位时下一个入库冷卷的数据未知 ，且 究nJ，也是最近研究的热点 “J．本文讨论 的某钢铁 冷卷一旦入库 即不再移动 ．不 同冷卷有不 同的规格 ， 公司冷轧厂热处理前库冷卷入库 问题 ，与装箱 问题 由众多参数确定，如品种、品名、钢种、退火 曲线号 、 存在密切关系，但约束条件众 多，规则复杂 ，难 以用 板宽、板厚 、卷重、卷径等 ，不同库位按照可 以容纳冷 已有算法求解 ． 卷的卷径大小有不同的规格 ，同一库位的冷卷规格 作者通过对该 问题的具体分析 ，为多种约束规 可 以不同，但必须满足热处理工艺的约束条件 ．冷卷 则设置统一的匹配权值，再进一步简化 问题为约束