CLSP问题的分枝定价算法

来源期刊：东北大学学报(自然科学版)2003年第1期

论文作者：高振 唐立新

文章页码：11 - 14

关键词：生产计划;调度;CLSP;启发式;分枝定界;列生成;

摘    要：提出了一种新的算法 分枝定价(Branch and Price)算法解经典CLSP,带有能力约束的单级多项动态批量问题(Thecapacitatedsingle level,multi item,dynamiclot sizingproblem)·CLSP问题有广泛工业背景,而且已被证明为NP Hard问题,它的目标是最小化总的装设(set up)费用和库存费用之和在所考虑的时间范围(horizon)内,并且满足给定约束条件·分枝定价算法是一种广义分枝定界(branch and bound)算法,它允许应用列生成(columngeneration)过程于整个分枝定界树·详细描述了该算法的实现,并用两组benchmark问题测试实例说明了该算法的有效性和优越性·