Computer Engineering and Applications ›› 2012, Vol. 48 ›› Issue (8): 221-225.

• 工程与应用 • Previous Articles     Next Articles

Column generation based method for dynamic inventory slab allocation problem

WANG Chao   

  1. Department of Software Engineering, Liaoning Information Vocational Technical College, Liaoyang, Liaoning 111000, China
  • Received:1900-01-01 Revised:1900-01-01 Online:2012-03-11 Published:2012-03-11

基于列生成算法求解动态库存板坯分配问题

王 超   

  1. 辽宁信息职业技术学院 软件工程系,辽宁 辽阳 111000

Abstract: A dynamic inventory slab allocation problem encountered in the steel industry is studied. This problem is formulated as a 0-1 integer program, the objective of the problem is to minimize the total cost in terms of allocation and inventory holding. According to the problem characteristic, the problem is decomposed into a master problem with a set-partition constraint and a price-subproblem with a knapsack constraint by Danzig-Wolfe method. A branch-and-price algorithm is developed for solving the problem. Computational results show that the developed branch-and-price algorithm is capable of generating the optimum solution to the production practical problem.

Key words: slab allocation, column generation, branch-and-price

摘要: 针对钢铁企业中遇到的动态库存板坯分配问题进行了研究。建立了一个0-1整数规划数学模型,该模型的目标是最小化板坯与合同规格差异费用以及板坯在库停留所产生的库存成本费用之和。根据问题特点,使用Danzig-Wolfe策略将这个模型分解为一个带有集划分约束的主问题和一个具有背包特征约束的价格子问题,开发了分支价格算法进行求解。计算结果表明所开发的分支价格算法能够最优求解生产实际问题。

关键词: 板坯分配, 列生成, 分支价格