CLSP问题的分枝定价算法  

Branch-and-Price Algorithm for CLSP

作　　者：高振[1] 唐立新[1] 

机构地区：[1]东北大学信息科学与工程学院,辽宁沈阳110004

出　　处：《东北大学学报（自然科学版）》2003年第1期11-14,共4页Journal of Northeastern University(Natural Science)

基　　金：国家自然科学基金资助项目(70171030;60274049).

摘　　要：提出了一种新的算法 分枝定价(Branch and Price)算法解经典CLSP,带有能力约束的单级多项动态批量问题(Thecapacitatedsingle level,multi item,dynamiclot sizingproblem)·CLSP问题有广泛工业背景,而且已被证明为NP Hard问题,它的目标是最小化总的装设(set up)费用和库存费用之和在所考虑的时间范围(horizon)内,并且满足给定约束条件·分枝定价算法是一种广义分枝定界(branch and bound)算法,它允许应用列生成(columngeneration)过程于整个分枝定界树·详细描述了该算法的实现,并用两组benchmark问题测试实例说明了该算法的有效性和优越性·A new BranchandPrice approach was presented to solve the classical capacitated singlelevel multiitem dynamic lotsizing problems,also called as CLSP. Its objective is to minimize the sum of setup and inventoryholding costs over the horizon under consideration, such as demands, capacity restrictions, etc. CLSP is frequently encountered in the most industry settings and well known as NPHard problem. The BranchandPrice approach, a generalization of branchandbound with LP relaxation, allows column generation to be applied throughout explored nodes in the branchandbound tree. An implementation of the branchandprice approach was described in detail. Two groups of examples were computed to verify the correctness and advantages of the suggested approach.

关 键 词：分枝定价算法 生产计划 调度 CLSP 分枝定界 列生成 能力约束 单级多项动态批量问题 工业企业 

分 类 号：F406.2[经济管理—产业经济] F224.0