允许缺货和转包的受限批量模型的多项式算法

Polynomial Algorithm for Capacitated Lot Sizing Models with Shortage and Outsourcing

有效组织带转包的采购计划对企业提高竞争力和参与全球产业分工有重要意义。研究了一个新的非减库存能力约束下的允许缺货和转包的企业采购计划模型,提出了一个基于动态规划的多项式算法。引入子计划概念,将问题归结为有效计算子计划;依据最优解的性质设计了求解子计划的多项式算法;再通过动态规划算法以多项式时间枚举所有可能子计划组合,得到问题的最优解。数值试验显示了该算法的有效性及高效性。

An optimal purchase planning with outsourcing is very important for enterprises to enhance their ability to compete, and to participate in the international division of labor. A new single item dynamic lot-sizing problem with backlogging and outsourcing and non-decreasing inventory capacity was addressed, and a polynomial dynamic programming algorithm was developed. By introducing the concept of subplan, the problem could boil down to the efficient computing of subplan. Based on the properties of an optimal solution, the polynomial algorithms were devised to solve the subplan. An optimal solution for the global problem was obtained by searching the best combination or concatenation of subplans with dynamic programming. Numeric results show that the proposed algorithm is effective and efficient.