带最小批量约束的计划问题及其拉格朗日松弛算法  

A Lagrange relaxation algorithm for capacitated lot-size problem(CLSP)with minimum lot-size constraint

作　　者：潘常春[1] 杨根科[1] 孙凯[1] 陆恒云[1] 

机构地区：[1]上海交通大学自动化系,上海200240

出　　处：《控制理论与应用》2009年第2期133-138,共6页Control Theory & Applications

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

摘　　要：针对一类带最小批量约束的计划问题,提出了基于拉格朗日松弛策略求解算法.通过拉格明日松弛策略,将原问题转为一系列带最小批量约束的动态经济批量W-W(Wagner-Whitin)子问题.提出了解决子问题且其时间复杂度O(T^3)的最优前向递推算法.对于拉格朗日对偶问题,用次梯度算法求解,获得原问题的下界.若对偶问题的解是不可行的,通过固定装设变量,求解一个剩余的线性规划问题来进行可行化处理.最后,数据仿真验证了算法的有效性.A Lagrange relaxation heuristic-based procedure is presented to solve the capacitated lot-size problem（CLSP） with minimum lot-size constraint. The problem is first decomposed into a series of sub-problems W-W（Wagner-Whitin） with dynamic economic minimum lot-size constraint. To deal with the sub-problems, an optimal forward iterative algorithm with runtime complexity of O（T^3） is proposed. The Lagrange dual problem is then handled by the sub-gradient optimization algorithm to obtain a tight lower bound. If the solution to the Lagrange dual problem is infeasible, the setup variables are fixed and the remaining problem is reformulated as a linear programming problem which can be solved efficiently by any off-the-shelf solver. Finally, the computational experiments demonstrate the algorithm＇s efficiency.

关 键 词：计划问题 最小批量约束 拉格朗日松弛 次梯度算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]