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

徐健腾;柏庆国;张庆普

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

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

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

    徐健腾(1), 柏庆国(2), 张庆普(3)
作者信息 +

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

    XU Jianteng(1), BAI Qingguo(2), ZHANG Qingpu(3)
Author information +
文章历史 +

摘要

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

Abstract

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.

引用本文

导出引用
徐健腾 , 柏庆国 , 张庆普. 二供应商经济批量问题的多项式时间算法. 系统科学与数学, 2010, 30(7): 936-946. https://doi.org/10.12341/jssms09011
XU Jianteng , BAI Qingguo , ZHANG Qingpu. A Polynomial Time Algorithm for Two-Supplier Economic Lot-Size Problem. Journal of Systems Science and Mathematical Sciences, 2010, 30(7): 936-946 https://doi.org/10.12341/jssms09011
中图分类号: 90B05   
PDF(508 KB)

Accesses

Citation

Detail

段落导航
相关文章

/