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

Column generation based method for dynamic inventory slab allocation problem

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

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 re- suits show that the developed branch-and-price algorithm is capable of generating the optimum solution to the production practical problem.