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

中国管理科学 ›› 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]. 中国管理科学, 2024, 32(6): 68-78.
[2]	代业明, 齐尧, 高红伟, 李陆. 基于PMSC管理及奖惩机制的智能电网实时定价研究[J]. 中国管理科学, 2022, 30(7): 88-98.
[3]	许保光, , 常嘉欣, , 高敏刚. 考虑人车混采的道路信息采集的路径规划研究[J]. 中国管理科学, 2022, 30(4): 218-227.
[4]	郭放, 黄志红, 黄卫来, 杨超. 考虑自取服务和门到门服务的电动汽车物流网络优化策略研究[J]. 中国管理科学, 2022, 30(2): 264-275.
[5]	王秀利, 徐悦, 胡修武. 中小呼叫中心月度排班优化模型与算法[J]. 中国管理科学, 2021, 29(4): 169-178.
[6]	吴江, 王旻轲, 谭涛, 张培文. 非平稳需求下考虑碳配额的供应链选址-库存模型与算法研究[J]. 中国管理科学, 2020, 28(3): 162-173.
[7]	高岩. 智能电网实时电价社会福利最大化模型的研究[J]. 中国管理科学, 2020, 28(10): 201-209.
[8]	郭放, 杨珺, 杨超. 考虑差异化服务时间的多车型电动汽车路径优化与充电策略研究[J]. 中国管理科学, 2019, 27(8): 118-128.
[9]	张杨, 但斌, 高华丽. 带工期指派的产品服务系统订单随机调度问题研究[J]. 中国管理科学, 2019, 27(2): 93-106.
[10]	杨珺, 冯鹏祥, 孙昊, 杨超. 电动汽车物流配送系统的换电站选址与路径优化问题研究[J]. 中国管理科学, 2015, 23(9): 87-96.
[11]	熊中楷, 方衍, 张聪誉. 以旧换新收购方式下的逆向物流网络优化设计[J]. 中国管理科学, 2011, 19(6): 65-72.
[12]	蓝伯雄, 王亚明, 王威. 企业资源优化与企业价值链分析[J]. 中国管理科学, 2011, 19(1): 69-76.
[13]	袁宁. 非流动性市场中的跨期最优消费和投资策略[J]. 中国管理科学, 2009, 17(4): 39-45.
[14]	肖依永, 常文兵, 张人千. 能力与资源双重约束下的启发式组合生产计划研究[J]. 中国管理科学, 2008, 20(6): 33-40.
[15]	鲁奎, 杨昌辉, 戴道明. 一种能力外包且费用时变批量问题的启发式算法[J]. 中国管理科学, 2008, 16(1): 80-85.