Research On The Multi-item Dynamic Lot-Sizing Problem With Outsourcing And Capacitated Resource

With the intense market competition, the enterprises need to coorperate with their suppliers more closely and provide better products and service for the customers with the lowest costs. Outsourcing has been a common stragety, which can both reduce the costs and improve the service level. In the research of dynamic lot-sizing problem, the articles which consider production capacity are more than that consider inventory capacity, and studies about dynamic lot-sizing problem with outsourcing are usually limited to single-item, less in multi-item. The articles in the research of multi-item dynamic lot-sizing problem which consider product capacity, inventory capacity and outsourcing at the same time haven’t been found. For an enterprise, these factors existed meanwhile which should been considered. Therefore this article researched the multi-item dynamic lot-sizing problem with restricted resource and outsourcing.This paper overviewed the research status of multi-item dynamic lot-sizing problem, and summarized the application of Lagrangean relaxation on multi-item dynamic lot-sizing problem. A brief summarization was given about basic theory of dynamic lot-sizing problem, outsourcing, Lagrangean relaxation algorithm, dynamic programming algorithm and heuristic algorithm.A multi-item dynamic lot-sizing model which considered production time constraint, limited storage capacity and outsourcing is built, where the production cost funciton is linear with fixed cost, outsourcing cost and holding cost are also linear and backlogging is not allowed. The production time of one product include setup time and processing time. In each period, the total prodution time for all products is limited. For a product, outsourcing quantity must be less than or equal to the demand of the current period.An algorithm based Lagrangean relaxation is developed to solve this problem. The constraints of production time capacity are relaxed into the objective funciton, and the problem can be decomposed into N subproblems with limited storage capacity. A dynamic programming algorithm is developed to solve these subproblem. A heuristic algorithm is proposed to construct feasible solutions, which include 4 phases called forward pass, single step backward pass, outsourcing pass and single period optimization. The first three phases are used to construct the feasible solutions and the last phase is used to improve the solution.In the simulation experiment, the effectiveness of the Lagrangean relaxation algorithm is verified by comparing the calculation result with commercial software LINGO under the same example. Then an integral demo example is given, the primal solution computed by dynamic programming algorithm and the feasible solution provided by Lagrangean relaxation heuristic algorithm are also showed. Six experiments are proposed to test the performance of different feasible solution construction strageties. Twelve instances with different product number and period number are used to test the total performance of the Lagrangean relaxation algorithm. In all experiments, the relative duality gap are within 2%.