二供应商经济批量问题的多项式时间算法

doi:10.12341/jssms09011

系统科学与数学 ›› 2010, Vol. 30 ›› Issue (7): 936-946.DOI: 10.12341/jssms09011

二供应商经济批量问题的多项式时间算法

徐健腾(1), 柏庆国(2), 张庆普(3)

(1)曲阜师范大学运筹与管理学院, 276826; 哈尔滨工业大学管理学院, 150001;(2)曲阜师范大学运筹与管理学院, 276826;(3)哈尔滨工业大学管理学院,150001

收稿日期:2008-03-31 修回日期:2010-03-09 出版日期:2010-07-25 发布日期:2010-07-25

PDF ( 461 ) 引用被引次数 ( 1 )

徐健腾;柏庆国;张庆普. 二供应商经济批量问题的多项式时间算法[J]. 系统科学与数学, 2010, 30(7): 936-946.

XU Jianteng;BAI Qingguo;ZHANG Qingpu. A Polynomial Time Algorithm for Two-Supplier Economic Lot-Size Problem[J]. Journal of Systems Science and Mathematical Sciences, 2010, 30(7): 936-946.

A Polynomial Time Algorithm for Two-Supplier Economic Lot-Size Problem

XU Jianteng(1), BAI Qingguo(2), ZHANG Qingpu(3)

(1)School of Operations Research and Management, Qufu Normal University, 276826; School of Management, Harbin Institute of Technology, 150001;(2)School of Operations Research and Management, Qufu Normal University, 276826;(3)School of Management, Harbin Institute of Technology, 150001

Received:2008-03-31 Revised:2010-03-09 Online:2010-07-25 Published:2010-07-25

为了从采购费用结构不同的供应商中找到最佳补货策略,考虑一个零售商从两个供应商补货的二供应商经济批量问题.零售商在两个供应商处的采购费用结构分别为复合安装费用和全单位数量折扣费用结构.通过对问题结构性质的分析论证,将问题的可行解转化为一个有向网络,降低问题求解的计算复杂性.综合动态规划和Dijkstra最短路算法证明了该问题是多项式时间可解的.

关键词： 批量, 复合安装费用, 全单位数量折扣, 计算复杂性, 动态规划.

In order to find the optimal replenishment policy from the suppliers with different structures, this paper considers the two-supplier economic lot-size problem in which the retailer replenishes products from two suppliers. The two suppliers are characterized by multiple set-ups and all-unit quantity discount cost structures.
Some structure properties are proposed to reduce the computational complexity.
Then the feasible solutions of the problem are converted into a directed network.
It is proved that this two-supplier economic lot-size problem can be solved in polynomial time by integrated dynamic programming and Dijkstra's shortest-path algorithm.

Key words: Lot-size, multiple set-ups cost, all-unit quantity discount, computational complexity, dynamic programming.

MR(2010)主题分类:

90B05

分享此文:

[1]	王磊，任建峰，柏庆国. 具有多个制造商和分批配送的同类机排序问题[J]. 系统科学与数学, 2019, 39(9): 1428-1434.
[2]	王磊，张玉忠，邢伟. 加工时间离散可控的分批配送排序问题[J]. 系统科学与数学, 2016, 36(10): 1652-1658.
[3]	王磊，张玉忠，柏庆国. 单机带有可拒绝的供应链排序问题[J]. 系统科学与数学, 2014, 34(9): 1044-1050.
[4]	王磊，张玉忠，王成飞. 机器具有学习效应的供应链排序问题[J]. 系统科学与数学, 2013, 33(7): 799-806.
[5]	张玲，李仲飞. 收益序列相关的动态资产-负债管理[J]. 系统科学与数学, 2012, 32(3): 297-309.
[6]	王科峰, 叶春明, 唐国春. 节点具有双重需求的车辆路径问题及其性质[J]. 系统科学与数学, 2011, 31(10): 1185-1196.
[7]	王磊;王国庆;易余胤. 交货期可以指派的供应链排序问题[J]. 系统科学与数学, 2010, 30(12): 1622-1630.
[8]	李仲飞从建发. 最优多期比例再保险策略的必要条件[J]. 系统科学与数学, 2008, 28(11): 1354-1362.

阅读次数

全文

摘要