求解大规模生产批量问题的启发式算法-中国管理科学.pdf

第 18 卷 　第 2 期 中国管理科学 Vol . 18 , No . 2 　　　　　　　　　　　 　　　　　　　　　　　 20 10 年 　　4 月 Chinese J ournal of Management Science Ap r . , 　20 10 文章编号 :1003 - 207 (20 10) 02 - 0081 - 08 求解大规模生产批量问题的启发式算法 蓝伯雄 ,姜 　楠 ,郑 　燕 (清华大学经济管理学院 ,北京 　100084) 摘 　要 :企业资源优化模型是多物料 、多层 、受多种能力约束 、有启动时间和启动成本的生产批量 问题 ,该问题是 N P 完全问题 ,求解十分困难 。为此我们提出了一个新的启发式方法 ,通过交互求解线性规划松弛问题并应用改进 的 SilverMeal 方法处理批量来近似求解生产批量问题 ,并第一次将影子价格引入 SilverMeal 方法的批量决策 ,数 值实验表明新算法在不同规模问题上的有较好的表现 。 关键词 :企业资源优化 ;批量算法 ;影子价格 ;启发式算法 中图分类号 :C934 　　　文献标识码 :A 备时间的受能力约束的批量问题是 N P 完全问题 。 1 　研究背景 [4 ] ( ) Kato k 等 1998 针对有一般装配结构的制造企 ( 传统的 ERP 软件都应用物料需求计划 Mat e 业 ,构造了多物料 、多层 、多能力约束和生产准备成 rial Requirement s Planning ,M RP) 方法来处理物流 本的批量模型 ,但类似的研究文献并不多见 。显然 , 计划问题 ,M R P 旨在向企业提供正确的生产计划数 多物料 、多层 、多能力约束的复杂批量 问题更难求 据 ,使企业在合适的时间用合适的物料生产出客户 解 ,无法使用精确算法求解大规模问题 ,文献报道的 需要的产品。M RP 方法包括四个计算模块 :主生产 主要求解方法是数学规划方法和启发式方法 。 计划 、物料需求计划 、能力需求计划和批量决策 。由 数学规划方法大部分都基于松弛法 , 即先放松 于 M RP 的无限能力假设以及批量处理时对 BOM 问题的批量约束 ,得到松弛问题的解 ,再通过某些批 关系的忽略 ,得出的生产计划往往既不可行也不经 量算法修正原计算结果中的批量 ,并根据批量调整 济 。面对快速的市场变化和激烈的市场竞争 ,M R P 后的变化重新求解松弛问题 ,直到问题收敛到一个 逻辑已经不能满足企业的需要 。因此 ,提供一个能 近优 解 。很 多文 献 使 用 的是 拉 格 朗 日松 弛 方 够优化企业资源配置且考虑批量决策的生产计划方 法[4 - 6 ] 。此 外 , Salo mon ( 199 1 ) [7 ] 、Mae s 等