A POLYNOMIAL TIME ALGORITHM FOR TWO-SUPPLIER ECONOMIC LOT-SIZE PROBLEM
二供应商经济批量问题的多项式时间算法

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.