A Lagrangean Relaxation- genetic algorithm heuristic for multi-product multi-stage and multi-period lot sizing problem with limited resource capacity

Abstract

In this paper, a hybrid method for limited resource allocation and leveling in complex multi-stage, multi-product and multi-period production planning problems with aim of lot-size determination and total cost minimization has been proposed. This problem consists of multiple products with sequential production processes that are produced in different periods to meet the customers demand. By determining decision variables, production capacity of machines and customers demand, an integer linear program is developed to minimize the total set-up, inventory holding and production cost. A three-stage approach has been developed to solve the problem. In the first stage, the primary problem is divided into several sub-problems using a heuristic algorithm based on the limited resource Lagrangean multipliers. In this case, each sub-problem could be solved using more simple methods. In the second stage a new approach is proposed to solve these sub-problems combining the genetic algorithm with a neighborhood search technique. In the third stage resource leveling is performed among sub-problems to obtain a better solution. In this case, lot-size for each product is determined during the planning periods. This paper's objectives have been evaluated and verified through several empirical experiments.