中国管理科学 ›› 2026, Vol. 34 ›› Issue (11): 199-209.doi: 10.16381/j.cnki.issn1003-207x.2024.1151cstr: 32146.14.j.cnki.issn1003-207x.2024.1151
收稿日期:2024-07-12
修回日期:2025-01-09
出版日期:2026-11-25
发布日期:2026-11-10
通讯作者:
梅启煌
E-mail:qhmei@wtu.edu.cn
基金资助:
Jianbin Li1,2, Gong Feng1, Ping Zhou3, Cheng Yang1, Qihuang Mei4(
)
Received:2024-07-12
Revised:2025-01-09
Online:2026-11-25
Published:2026-11-10
Contact:
Qihuang Mei
E-mail:qhmei@wtu.edu.cn
摘要:
考虑到生产能力的限制、多周期排产和原料替代等因素时,批量生产问题的复杂性会显著增加。批量生产过程中可能存在多种可替代原料,每种原料的替代方案均会影响生产成本。本文研究一类具有原料替代的多周期批量生产问题,针对此问题构建了混合整数规划模型,并设计了混合自适应大邻域搜索算法进行求解,该算法将自适应大邻域搜索算法框架与Gurobi求解器相结合,简化了修复算子的设计过程,同时能快速收敛至较高质量的解。此外,本文采用X烟草工业公司2023年1月-2023年8月的生产数据进行算例分析,并将混合ALNS算法与ALNS算法、Gurobi求解器、贪婪算法进行了对比,实验结果验证了本文算法的可行性和有效性。在小规模算例上,混合ALNS能求解出和Gurobi精度相同的解;在大规模算例上,具有明显的时间优势。同时,混合ALNS求解结果较ALNS的平均改善幅度达到了37.73%。最后,通过数值实验,分析了原料替代策略对生产成本、缺货率的影响以及单位原料替代成本对总成本的影响。实验结果表明,原料替代策略能平均节省约23%的生产总成本,减少约26.4%的缺货率。
中图分类号:
李建斌,冯巩,周平, 等. 考虑原料替代的多周期批量生产策略研究[J]. 中国管理科学, 2026, 34(11): 199-209.
Jianbin Li,Gong Feng,Ping Zhou, et al. Research on Multi-Period Lot-Sizing Problem Considering Raw Material Substitution[J]. Chinese Journal of Management Science, 2026, 34(11): 199-209.
表1
参数符号及含义"
| 参数 | 含义 |
|---|---|
| 集合 | |
| 烟草产品集合, | |
| 烟叶原料集合, | |
| 生产周期集合, | |
| 生产机器集合, | |
| 烟草产品 | |
| 烟草产品 | |
| 烟草产品 | |
| 烟草产品 | |
| 一个足够大的正整数 | |
| 生产机器 | |
| 生产1单位烟草产品 | |
| 生产1单位烟草产品 | |
| 原料 | |
| 原料 | |
| 原料 | |
| 在生产周期 | |
| 生产周期 | |
| 决策变量 | |
| 生产周期 | |
| 在生产周期 | |
| 生产周期 | |
| 在生产周期 |
表4
混合ALNS与Gurobi求解器、贪婪算法、ALNS算法求解结果的对比"
| 算例 | N | T | Gurobi | 贪婪算法 | ALNS | 混合ALNS | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| obj | t/s | obj | t/s | obj | t/s | Gap_AG/% | Gap_AT/% | obj | t/s | Gap_G/% | Gap_T/% | Gap_A/% | |||
| A1 | 2 | 2 | 8023.11 | 0.1 | 10221.78 | 0 | 9047.01 | 6.5 | -12.76 | 11.49 | 8023.11 | 4.73 | 0 | 21.51 | 11.32 |
| A2 | 2 | 8 | 25904.09 | 2.0 | 37343.68 | 0 | 32735.68 | 10.5 | -26.37 | 12.34 | 25904.09 | 5.36 | 0 | 30.63 | 20.87 |
| A3 | 3 | 10 | 45187.81 | 5.0 | 64868.28 | 0.001 | 58742.28 | 14.3 | -30.00 | 9.44 | 45187.81 | 19.07 | 0 | 30.34 | 23.07 |
| A4 | 4 | 12 | 72406.51 | 8.0 | 107658.76 | 0.002 | 97434.75 | 25.6 | -34.57 | 9.50 | 72406.51 | 31.82 | 0 | 32.74 | 25.69 |
| A5 | 5 | 14 | 99676.70 | 20.0 | 153701.28 | 0.002 | 142553.28 | 27.8 | -43.02 | 7.25 | 99676.70 | 32.46 | 0 | 35.15 | 30.08 |
| A6 | 6 | 16 | 119852.47 | 50.0 | 198922.96 | 0.003 | 186145.96 | 30.3 | -55.31 | 6.42 | 119892.48 | 35.38 | -0.03 | 39.73 | 35.59 |
| A7 | 6 | 18 | 134687.29 | 250.0 | 226003.21 | 0.003 | 209806.21 | 122.17 | -55.77 | 7.17 | 136051.29 | 45.83 | -1.00 | 39.80 | 35.15 |
| A8 | 7 | 20 | - | 36000 | 297525.31 | 0.004 | 262508.31 | 130.62 | - | 11.77 | 158213.03 | 46.72 | - | 46.82 | 39.73 |
| A9 | 7 | 22 | - | 36000 | 330394.81 | 0.006 | 273330.81 | 134.13 | - | 17.27 | 167770.66 | 53.41 | - | 49.22 | 38.62 |
| A10 | 8 | 24 | - | 36000 | 419445.59 | 0.006 | 345092.59 | 153.65 | - | 17.73 | 188622.54 | 54.05 | - | 55.03 | 45.34 |
| A11 | 9 | 26 | - | 36000 | 603469.64 | 0.013 | 538536.64 | 291.69 | - | 10.76 | 229053.89 | 57.72 | - | 62.04 | 57.47 |
| A12 | 10 | 28 | - | 36000 | 724157.02 | 0.013 | 628934.02 | 614.36 | - | 13.15 | 273883.39 | 57.74 | - | 62.18 | 56.45 |
| A13 | 11 | 30 | - | 36000 | 835364.14 | 0.013 | 703890.14 | 1027.51 | - | 15.74 | 312184.54 | 281.27 | - | 62.63 | 55.65 |
| A14 | 12 | 32 | - | 36000 | 934261.63 | 0.016 | 807350.63 | 1336.51 | - | 13.58 | 377407.60 | 389.5 | - | 59.60 | 53.25 |
| Avg | - | - | - | - | - | - | - | - | - | 11.69 | - | - | - | 44.82 | 37.73 |
表5
算例B1~B6两种不同生产场景的成本细分"
| 算例 | N | T | 存在原料替代 | ||||||
|---|---|---|---|---|---|---|---|---|---|
| 总成本 | 生产成本 | 生产准备成本 | 持有成本 | 缺货成本 | 替代成本 | ||||
| B1 | 6 | 8 | 72301.0 | 42240.0 | 11931.0 | 12620.0 | 0.0 | 5510.0 | |
| B2 | 8 | 8 | 94952.3 | 53460.0 | 21861.0 | 13060.0 | 0.0 | 6571.3 | |
| B3 | 10 | 8 | 121973.8 | 71280.0 | 23909.0 | 18720.0 | 0.0 | 8064.8 | |
| B4 | 12 | 8 | 155968.4 | 91740.0 | 30609.0 | 25300.0 | 0.0 | 8319.4 | |
| B5 | 14 | 8 | 167116.6 | 102300.0 | 30845.0 | 26940.0 | 0.0 | 7031.6 | |
| B6 | 16 | 8 | 181483.4 | 107580.0 | 34185.0 | 32120.0 | 0.0 | 7598.4 | |
| 算例 | N | T | 不存在原料替代 | ||||||
| 总成本 | 生产成本 | 生产准备成本 | 持有成本 | 缺货成本 | 替代成本 | ||||
| B1 | 6 | 8 | 104331.0 | 28987.0 | 8566.0 | 7130.0 | 59648.0 | - | |
| B2 | 8 | 8 | 142066.0 | 35996.0 | 13038.0 | 10030.0 | 83002.0 | - | |
| B3 | 10 | 8 | 160274.0 | 52539.0 | 16511.0 | 14080.0 | 77144.0 | - | |
| B4 | 12 | 8 | 196104.0 | 67304.0 | 22008.0 | 17790.0 | 89002.0 | - | |
| B5 | 14 | 8 | 211559.0 | 79558.0 | 24745.0 | 19213.0 | 88043.0 | - | |
| B6 | 16 | 8 | 220265.0 | 85568.0 | 29734.0 | 22561.0 | 82402.0 | - | |
| [1] | Sreedevi R, Saranga H. Uncertainty and supply chain risk: The moderating role of supply chain flexibility in risk mitigation[J]. International Journal of Production Economics, 2017, 193: 332-342. |
| [2] | Qin H, Zhuang H, Yu C, et al. A matheuristic approach for the multi-level capacitated lot-sizing problem with substitution and backorder[J]. International Journal of Production Research, 2024, 62(13): 4645-4673. |
| [3] | Balakrishnan A, Geunes J. Requirements planning with substitutions: Exploiting bill-of-materials flexibility in production planning[J]. Manufacturing & Service Operations Management, 2000, 2(2): 166-185. |
| [4] | Han G, Dong M, Liu S. Yield and allocation management in a continuous make-to-stock system with demand upgrade substitution[J]. International Journal of Production Economics, 2014, 156: 124-131. |
| [5] | Sethi A K, Sethi S P. Flexibility in manufacturing: A survey[J]. International Journal of Flexible Manufacturing Systems, 1990, 2(4): 289-328. |
| [6] | Hsu A, Bassok Y. Random yield and random demand in a production system with downward substitution[J]. Operations Research, 1999, 47(2): 277-290. |
| [7] | 范捷, 王国庆. 带分段仓储能力决策的动态批量优化问题研究[J]. 系统工程理论与实践, 2017, 37(10): 2592-2599. |
| Fan J, Wang G Q. Dynamic lot sizing problem with section storage capacity decisions[J]. Systems Engineering —Theory & Practice, 2017, 37(10): 2592-2599. | |
| [8] | 陈豪韵. 面向产品族的有限产能批量与调度模型[J]. 系统工程, 2020, 38(4): 143-150. |
| Chen H Y. The capacitated lot sizing and scheduling problem model oriented product family[J]. Systems Engineering, 2020, 38(4): 143-150. | |
| [9] | 谢祥添. 基于产品合格率不确定与M/M/l下生产批量决策[J]. 系统科学学报, 2021, 29(3): 121-124. |
| Xie X T. Lot sizing problem with uncertain rate of qualified products and M/M/1[J]. Chinese Journal of Systems Science, 2021, 29(3): 121-124. | |
| [10] | Pamuk B, Ağralı S, Taşkın Z C, et al. A lot-sizing problem in deliberated and controlled co-production systems[J]. IISE Transactions, 2022, 54(10): 950-962. |
| [11] | Hwang H C, Kang J. An improved algorithm for the lot-sizing problem with outbound shipment[J]. Omega, 2021, 100: 102205. |
| [12] | Liu M, Tang H, Chu F, et al. Joint optimization of lot-sizing and pricing with backlogging[J]. Computers & Industrial Engineering, 2022, 167: 107979. |
| [13] | Bank M, Mahdavi Mazdeh M, Heydari M, et al. Coordinating lot sizing and integrated production and distribution scheduling with batch delivery and holding cost[J]. Kybernetes, 2022, 51(3): 1151-1179. |
| [14] | Acevedo-Ojeda A, Contreras I, Chen M. Two-level lot-sizing with raw-material perishability and deterioration[J]. Journal of the Operational Research Society, 2020, 71(3): 417-432. |
| [15] | Shin H, Park S, Lee E, et al. A classification of the literature on the planning of substitutable products[J]. European Journal of Operational Research, 2015, 246(3): 686-699. |
| [16] | Freeman N K, Narayanan A, Keskin B B. Optimal use of downward substitution in a manufacturing operation subject to uncertainty[J]. Omega, 2021, 103: 102372. |
| [17] | Sim J, Kim B. Sourcing decision in the presence of a complementary component[J]. Omega, 2021, 101: 102281. |
| [18] | Lang J C, Shen Z J M. Fix-and-optimize heuristics for capacitated lot-sizing with sequence-dependent setups and substitutions[J]. European Journal of Operational Research, 2011, 214(3): 595-605. |
| [19] | 蓝伯雄, 姜楠, 郑燕. 求解大规模生产批量问题的启发式算法[J]. 中国管理科学, 2010, 18(2): 81-88. |
| Lan B X, Jiang N, Zheng Y. A heuristic lot-sizing algorithm for large scale lot-sizing problem[J]. Chinese Journal of Management Science, 2010, 18(2): 81-88. | |
| [20] | Windras Mara S T, Norcahyo R, Jodiawan P, et al. A survey of adaptive large neighborhood search algorithms and applications[J]. Computers & Operations Research, 2022, 146: 105903. |
| [21] | Ji B, Zhang S, Yu S S, et al. Novel model and solution method for flexible job shop scheduling problem with batch processing machines[J]. Computers & Operations Research, 2024, 161: 106442. |
| [22] | Liu J, Sun B, Li G, et al. Multi-objective adaptive large neighbourhood search algorithm for dynamic flexible job shop schedule problem with transportation resource[J]. Engineering Applications of Artificial Intelligence, 2024, 132: 107917. |
| [23] | Abreu L R, Nagano M S. A new hybridization of adaptive large neighborhood search with constraint programming for open shop scheduling with sequence-dependent setup times[J]. Computers & Industrial Engineering, 2022, 168: 108128. |
| [24] | Begnaud J, Benjaafar S, Miller L A. The multi-level lot sizing problem with flexible production sequences[J]. IIE Transactions, 2009, 41(8): 702-715. |
| [25] | Zeppetella L, Gebennini E, Grassi A, et al. Optimal production scheduling with customer-driven demand substitution[J]. International Journal of Production Research, 2017, 55(6): 1692-1706. |
| [26] | Jing F, Mu Y. Dynamic lot-sizing model under perishability, substitution, and limited storage capacity[J]. Computers & Operations Research, 2020, 122: 104978. |
| [27] | Geunes J. Solving large-scale requirements planning problems with component substitution options[J]. Computers & Industrial Engineering, 2003, 44(3): 475-491. |
| [28] | Wei M, Qi M, Wu T, et al. Distance and matching-induced search algorithm for the multi-level lot-sizing problem with substitutable bill of materials[J]. European Journal of Operational Research, 2019, 277(2): 521-541. |
| [29] | 韩毅, 唐加福, 牟立峰, 等. 粒子群算法求解无能力约束生产批量计划问题[J]. 管理科学学报, 2008, 11(5): 33-40. |
| Han Y, Tang J F, Mou L F, et al. Particle swarm optimization algorithm for solving uncapacitated multilevel lot-sizing problems[J]. Journal of Management Sciences in China, 2008, 11(5): 33-40. | |
| [30] | Tunc H, Kilic O A, Tarim S A, et al. An extended mixed-integer programming formulation and dynamic cut generation approach for the stochastic lot-sizing problem[J]. INFORMS Journal on Computing, 2018, 30(3): 492-506. |
| [31] | Thevenin S, Adulyasak Y, Cordeau J F. Stochastic dual dynamic programming for multiechelon lot sizing with component substitution[J]. INFORMS Journal on Computing, 2022, 34(6): 3151-3169. |
| [32] | Thevenin S, Adulyasak Y, Cordeau J F. Material requirements planning under demand uncertainty using stochastic optimization[J]. Production and Operations Management, 2021, 30(2): 475-493. |
| [33] | Muller L F, Spoorendonk S, Pisinger D. A hybrid adaptive large neighborhood search heuristic for lot-sizing with setup times[J]. European Journal of Operational Research, 2012, 218(3): 614-623. |
| [34] | Pisinger D, Ropke S. A general heuristic for vehicle routing problems[J].Computers & Operations Research, 2007, 34(8): 2403-2435. |
| [1] | 项寅, 滕辰妹, 李佩, 谈丹. 换电模式下考虑设施中断的无人机应急救援网络规划[J]. 中国管理科学, 2026, 34(10): 196-208. |
| [2] | 隋鑫, 代文强, 王子绮. 两阶段定向展示广告保量鲁棒投放问题[J]. 中国管理科学, 2026, 34(9): 133-141. |
| [3] | 刘丽萍, 王蕊, 孙时磊, 甘晓凤, 范体军. 节点中断下考虑风险公平的危化品运输网络优化[J]. 中国管理科学, 2026, 34(6): 66-76. |
| [4] | 周煜丰, 吴志彬, 向传凯, 徐玖平. 考虑需求可拆分的雇佣和众包车辆协同运输路径规划模型[J]. 中国管理科学, 2026, 34(2): 133-144. |
| [5] | 赵菊, 袁叶, 曹宗宏, 闵杰. 基于库存控制的全渠道零售商线上下单线下取货退货策略研究[J]. 中国管理科学, 2025, 33(12): 349-359. |
| [6] | 项寅, 滕辰妹, 王雪, 张文静. 基于网络阻断理论的交通安检网络设计与资源调度模型[J]. 中国管理科学, 2025, 33(9): 109-120. |
| [7] | 代文强, 李丹阳. 考虑不确定协变量下的在线广告鲁棒分配策略[J]. 中国管理科学, 2025, 33(8): 230-237. |
| [8] | 金爽, 周晶, 胡骞. 考虑灵活弧中断的网络维护调度问题及其算法研究[J]. 中国管理科学, 2025, 33(8): 250-259. |
| [9] | 王蕊, 徐秀丽. “服务智能化”排队系统的顾客行为及定价研究[J]. 中国管理科学, 2025, 33(8): 260-270. |
| [10] | 李京, 车阿大. 考虑家庭储备的应急设施选址与物资分配的分布鲁棒优化研究[J]. 中国管理科学, 2025, 33(5): 268-279. |
| [11] | 殷允强, 秦慧, 刘小畅, 王杜娟. 考虑医患匹配的双目标速度时变家庭医疗护理调度问题研究[J]. 中国管理科学, 2025, 33(5): 203-213. |
| [12] | 代文强, 章潇月, 陈琳. 道路稳定系数不确定条件下的应急疏散规划[J]. 中国管理科学, 2025, 33(4): 204-212. |
| [13] | 张玲, 李锦棚, 陈圣群. 基于数据驱动的应急血液供应网络配置分布式鲁棒优化方案研究[J]. 中国管理科学, 2025, 33(2): 131-140. |
| [14] | 田甜, 苑慧静, 唐加福, 刘玉学. 外卖配送无人接单问题的平台监管与商家激励策略研究[J]. 中国管理科学, 2025, 33(2): 184-194. |
| [15] | 郑斐峰, 王志鑫, 刘明. 考虑峰谷分时电价和电池损耗成本的纯电动公交车充电调度优化研究[J]. 中国管理科学, 2024, 32(11): 125-135. |
| 阅读次数 | ||||||
|
全文 |
|
|||||
|
摘要 |
|
|||||
|
||