新的Lagrangian松弛法求解CLSP问题  

NEW LAGRANGIAN RELAXATION ALGORITHMS TO SOLVE CLSP

作　　者：唐立新[1] 杨自厚[1] 王梦光[1] 

机构地区：[1]东北大学系统工程研究所

出　　处：《系统工程学报》1999年第1期9-14,共6页Journal of Systems Engineering

基　　金：国家自然科学基金;国家863/CIMS资助

摘　　要：ＣＬＳＰ（ｃａｐａｃｉｔａｔｅｄｓｉｎｇｌｅ－ｌｅｖｅｌｌｏｔ－ｓｉｚｉｎｇｐｒｏｂｌｅｍ）是在受能力约束限制下，确定Ｎ种不同的项目在给定的计划范围Ｔ内的每一个时间段批量，使得在整个计划范围内（ｐｌａｎｎｉｎｇｈｏｒｉｚｏｎ）项目总的调整费用和库存保管费用以及生产费用之和最小．本文基于Ｌａｇｒａｎｇｉａｎ松弛法和新的启发式算法相结合求解ＣＬＳＰ问题，通过测试１０个问题，仿真实验表明，平均对偶误差可达到２％以内．The single level capacitated dynamic lot sizing problem is to determine production lot sizes of N itme over periods that minimizes the sum of setup costs and inventory holding costs over the planning horizon,while satisfying capacity constraints.In this paper,we have developed a Lagrangian relaxation based new heuristic algorithms to generate near optimal solutions to CLSP.Computational results of 10 tested problems show that the average duality gaps are within 2%.

关 键 词：批量计划 LAGRANGIAN CLSP问题 CIMS 

分 类 号：TH166[机械工程—机械制造及自动化]