考虑延期交货、转包和非减库存能力约束的单产品批量模型

研究了一个非减库存能力约束下的允许延期交货和转包的单产品动态批量问题.引入子计划概念,通过先求解所有可能的子计划,再基于动态规划搜索子计划的最优组合,得到问题的最优解.给出了所有子计划的通用数学描述,并通过松弛正生产量约束将子计划的计算分成两个子问题;依据子问题和子计划最优解的性质,设计了求解子问题和重新集结松弛约束的多项式算法;在此基础上提出了一个复杂性为O(T4)的求解整个规划问题的多项式动态规划算法,这里T是规划时段上的周期数.最后通过数值试验测试了该算法的性能.

Single Item Lot Sizing Models with Backlogging and Outsourcing and Non-decreasing Inventory Capacity

This paper addresses a dynamic single-item lot sizing problem with backlogging and outsourcing and non-decreasing inwentory capacity.By the means of the concept of sub-plan,the problem can be solved by first computing all possible sub-plans and then searching the best combination or concatenation of sub-plans using dynamic programming.All the sub-plans are described by a group of general mathematic formulae.The computation of the sub-plan can be decomposed into two sub-problems by relaxing the constraint that production level at production period of a sub-plan must be more than zero.Based on the properties of an optimal solution,two polynomial algorithms are devised to solve sub-problems and reintegrate the relaxed constraint.Finally,a dynamic programming algorithm with complexity O(T4) is developed to solve the global problem,where T is number of periods in planning horizon.The performance of the proposed algorithm is evaluated by numeric experiment.