Study On Multi-level Capacitated Lot-sizing And Scheduling Problem

With the combination with production planning in actual production process, thisthesis studies the multi-level capacitated lot-sizing and scheduling problem. Afterreviewing a large number of related literatures, we found out that most of the productstructures in previous literatures were assumed to remain unchanged. However, some ofthe products in actual production process may have changeable product structures orhave multiple choices on product structure.As a result, this thesis studies lot-sizing and scheduling problem with changeableproduct structures and replaceable product structures. For the lot-sizing and schedulingproblem with changeable product structures, this thesis formulates a mixed integerprogramming model, and designs a relax-and-fix based stochastic search approach tosolve the model; for the lot-sizing and scheduling problem with replaceable productstructures, this thesis formulates a nonlinear programming model, and combines thegenetic algorithm with the stochastic search approach to solve the model. Both of themodels have the objective to minimize the sum of setup cost, inventory holding cost andbacklog cost, and subject to the inventory balance constraints and the machine capacityconstraints.During the research, we made some testing example to test the models and thealgorithms designed. The testing results show that the relax-and-fix based stochasticsearch approach can solve the large-size lot-sizing and scheduling problem withchangeable product structures efficiently with high quality solutions; The testing resultsalso show that the genetic algorithm makes significant improvement to solving thenonlinear programming model constructed to solve the lot-sizing and schedulingproblem with replaceable product structures.