关键词: 运筹学, 经济批量, 多项式时间算法, 计算复杂性

Abstract: The economic lot size problem with quantity discount policy in a supply chain consisted of multi-supplier and multi-retailer is considered. Via constructing optimization models, some special optimal properties are proposed for the cases where order cost is all-unit quantity discount and incremental quantity discount, respectively. With the help of these optimal properties, the searching range of the optimal solutions is reduced under dynamic programming method. The polynomial time algorithms are developed for a special case of the model with all-unit quantity discount cost structure and the model with incremental quantity discount cost structure. Finally, the numerical examples illustrates the efficiency and implementation processes of the algorithms.

Key words: Operation research, economic lot-size, polynomial time algorithm, computational complexity