钢铁企业板坯动态分配问题的建模与分散搜索算法求解  

Modeling and scatter search algorithm for dynamic slab allocation problem in iron and steel enterprises

作　　者：吕亚娜[1,2] 唐立新[1,2] 孟盈[1,2] 袁媛[1,2] 

机构地区：[1]东北大学工业工程与物流优化研究所,沈阳110004 [2]东北大学辽宁省制造系统与物流优化重点实验室,沈阳110004

出　　处：《控制与决策》2015年第1期17-24,共8页Control and Decision

基　　金：国家自然科学基金重点项目(71032004);国家自然科学基金创新研究群体科学基金项目(71321001);国家863计划项目(2013AA040704)

摘　　要：板坯动态分配问题是在一定周期内,将炼钢-连铸工序动态产出的余材板坯合理分配给期货合同、潜在合同或自拟合同,使加权费用和最小.对该问题建立0-1整数规划模型,针对问题的NP-难求解性,设计基于多邻域的分散搜索算法对问题近似求解,并加入随机策略防止算法陷入局部最优.分别采用模拟数据和实际数据进行测试,所提出的算法与商业软件CPLEX相比,可在较短时间内获得近优解,在解的质量和计算时间方面均优于人工方法.The dynamic slab allocation problem is to assign the surplus slabs, which are dynamically obtained from steel-making and casting process, to the customer-orders, potential-orders and self-designed-orders in a given period. Therefore, a 0-1 integer programming model is formulated. Due to its NP-hardness, a multiple neighborhoods based scatter search algorithm is proposed to solve the problem approximately. Furthermore, to avoid search process being tapped in local optima, a random perturbation strategy is introduced. Both randomly generated instances and practical instances obtained from a large iron-and-steel enterprise are used to test the performance of the proposed algorithm. Compared with commercial soft named CPLEX, the proposed algorithm can get near-optimal solution in a reasonable CPU time. The experiments on the practical data show that the proposed algorithm outperforms the manual methods on solution quality and computation time.

关 键 词：余材板坯 动态分配 建模 分散搜索 

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]