求解大规模生产批量问题的启发式算法

中国管理科学 ›› 2010, Vol. 18 ›› Issue (2): 81-88.

求解大规模生产批量问题的启发式算法

蓝伯雄, 姜楠, 郑燕

清华大学经济管理学院, 北京 100084

收稿日期:2009-05-15 修回日期:2010-03-03 出版日期:2010-04-30 发布日期:2010-04-30
作者简介:蓝伯雄(1950- ),男(汉族),黑龙江齐齐哈尔人,清华大学经济管理学院教授,研究方向:大系统优化理论、复杂制造系统优化模型.
基金资助:
国家自然科学基金资助项目(70471007)

A Heuristic Lot-Sizing Algorithm for Large Scale Lot-Sizing Problem

LAN Bo-xiong, JIANG Nan, ZHENG Yan

School of Economics and Management, Tsinghua University, Beijing 100084, China

Received:2009-05-15 Revised:2010-03-03 Online:2010-04-30 Published:2010-04-30

摘要/Abstract

摘要： 企业资源优化模型是多物料、多层、受多种能力约束、有启动时间和启动成本的生产批量问题,该问题是NP完全问题,求解十分困难。为此我们提出了一个新的启发式方法,通过交互求解线性规划松弛问题并应用改进的Silver-Meal方法处理批量来近似求解生产批量问题,并第一次将影子价格引入Silver-Meal方法的批量决策,数值实验表明新算法在不同规模问题上的有较好的表现。

关键词: 企业资源优化, 批量算法, 影子价格, 启发式算法

Abstract: Enterprise resource optimization model is a multi-item,multi-level,multi-capacitated lot-sizing problem with setup time and setup cost,which is NP complete and hard to be solved A new heuristic algorithm is proposed to solve a LP relaxation and a modified Silver-Meal lot-sizing model interactively. The shadow price is first introduced to the lot-sizing decisions of Silver-Meal method Numerical test shows that the new heuristic method has a good performance in solving the test problems with different scales.

Key words: enterprise resource optimization, lot-sizing algorithm, shadow price, heuristic method

中图分类号:

C934

蓝伯雄, 姜楠, 郑燕. 求解大规模生产批量问题的启发式算法[J]. 中国管理科学, 2010, 18(2): 81-88.

LAN Bo-xiong, JIANG Nan, ZHENG Yan. A Heuristic Lot-Sizing Algorithm for Large Scale Lot-Sizing Problem[J]. Chinese Journal of Management Science, 2010, 18(2): 81-88.

[1]	吴江, 王旻轲, 谭涛, 张培文. 非平稳需求下考虑碳配额的供应链选址-库存模型与算法研究[J]. 中国管理科学, 2020, 28(3): 162-173.
[2]	高岩. 智能电网实时电价社会福利最大化模型的研究[J]. 中国管理科学, 2020, 28(10): 201-209.
[3]	郭放, 杨珺, 杨超. 考虑差异化服务时间的多车型电动汽车路径优化与充电策略研究[J]. 中国管理科学, 2019, 27(8): 118-128.
[4]	张杨, 但斌, 高华丽. 带工期指派的产品服务系统订单随机调度问题研究[J]. 中国管理科学, 2019, 27(2): 93-106.
[5]	杨珺, 冯鹏祥, 孙昊, 杨超. 电动汽车物流配送系统的换电站选址与路径优化问题研究[J]. 中国管理科学, 2015, 23(9): 87-96.
[6]	熊中楷, 方衍, 张聪誉. 以旧换新收购方式下的逆向物流网络优化设计[J]. 中国管理科学, 2011, 19(6): 65-72.
[7]	蓝伯雄, 王亚明, 王威. 企业资源优化与企业价值链分析[J]. 中国管理科学, 2011, 19(1): 69-76.
[8]	袁宁. 非流动性市场中的跨期最优消费和投资策略[J]. 中国管理科学, 2009, 17(4): 39-45.
[9]	肖依永, 常文兵, 张人千. 能力与资源双重约束下的启发式组合生产计划研究[J]. 中国管理科学, 2008, 20(6): 33-40.
[10]	乔忠, 李凌颖. 商品交易市场网络节点选址的双层规划模型——以安徽省砀山县为例[J]. 中国管理科学, 2008, 16(1): 125-130.
[11]	鲁奎, 杨昌辉, 戴道明. 一种能力外包且费用时变批量问题的启发式算法[J]. 中国管理科学, 2008, 16(1): 80-85.
[12]	何波, 杨超, 张华. 废弃物回收的多层逆向物流网络优化设计问题研究[J]. 中国管理科学, 2007, 15(3): 61-67.
[13]	李延晖, 马士华. 基于时间约束的单源/p个中转点配送系统的MINLP模型[J]. 中国管理科学, 2004, (3): 86-90.
[14]	贺铁林. 网络图中多约束条件下的路径选择问题[J]. 中国管理科学, 2003, (4): 41-46.
[15]	黄伟文, 钱雁南, 许保光. “行/列约束法”在外贸进出口货柜运输业务上的应用[J]. 中国管理科学, 2002, (1): 89-93.