引用本文:潘常春,杨根科,孙 凯,陆恒云.带最小批量约束的计划问题及其拉格朗日松弛算法[J].控制理论与应用,2009,26(2):133~138.[点击复制]
PAN Chang-chun,YANG Gen-ke,SUN Kai,LU Heng-yun.A Lagrange relaxation algorithm for capacitated lot-size problem(CLSP) with minimum lot-size constraint[J].Control Theory and Technology,2009,26(2):133~138.[点击复制]
带最小批量约束的计划问题及其拉格朗日松弛算法
A Lagrange relaxation algorithm for capacitated lot-size problem(CLSP) with minimum lot-size constraint
摘要点击 1869  全文点击 2107  投稿时间：2007-09-07  修订日期：2008-07-04
查看全文  查看/发表评论  下载PDF阅读器
DOI编号  
  2009,26(2):133-138
中文关键词  计划问题  最小批量约束  拉格朗日松弛  次梯度算法
英文关键词  CLSP  minimum lot-size  Lagrange relaxation  sub-gradient optimization
基金项目  国家自然科学基金资助项目(60574063).
作者单位E-mail
潘常春 上海交通大学 自动化系, 上海 200240 pan_cc@sjtu.edu.cn 
杨根科 上海交通大学 自动化系, 上海 200240 gkyang@sjtu.edu.cn 
孙 凯 上海交通大学 自动化系, 上海 200240 sunkai@sjtu.edu.cn 
陆恒云 上海交通大学 自动化系, 上海 200240 luhy@sjtu.edu.cn 
中文摘要
      针对一类带最小批量约束的计划问题, 提出了基于拉格朗日松弛策略求解算法. 通过拉格朗日松弛策略, 将原问题转为一系列带最小批量约束的动态经济批量W-W(Wagner-Whitin)子问题. 提出了解决子问题且其时间复杂度O(T3)的最优前向递推算法. 对于拉格朗日对偶问题, 用次梯度算法求解, 获得原问题的下界. 若对偶问题的解是不可行的, 通过固定装设变量, 求解一个剩余的线性规划问题来进行可行化处理. 最后, 数据仿真验证了算法的有效性.
英文摘要
      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(T3) 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.