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.