Research On Algorithm For Multi-Level Multi-Item Lot-Sizing Scheduling Problem

Solving multi-level multi-item lot-sizing problem is the core component of business management software. The algorithm dealing with lot-sizing problem plays an important role in enhancing operating efficiency of business management software. Many infeasible solutions occur in solving lot sizing problem, occupy the population and disturb the process of searching for the optimal solution. In another aspect, the efficiency of many algorithms depends on the distribution of initial solutions tightly.This paper presents two formulations for multi-level multi-item lot-sizing problem with lead time and setup carryover constraints. Firstly, it presents binary coding adaptive genetic algorithm to solving multi-level multi-item capacitated lot-sizing problem. At the beginning of computing progress, adaptive genetic algorithm tends to do global search in solution space by controlling crossover possibility, and it tends to do local search by controlling mutate possibility as approaching to the end of computing progress. This paper implements this algorithm and test it's efficiency with a example of multi-level multi-item lot-sizing problem. The efficiency of the algorithm is due to introducing of memory cell in immune algorithm.Secondly, this paper researches multi-level multi-item uncapacitated lot-sizing problem with carryover setup state and lead time. This paper introduces forest coding into partheno genetic algorithm for multi-level multi-item uncapacitated lot-sizing. Forest coding is inspired by similarity of the bill of materials'structure and forest in data structures, and the search operation for a item's predecessor and successor is acted by pointer in gene instead of searching in binary matrix one by one. Because of the character of partheno genetic algorithm, result of algorithm is independent to the distribution of initial solutions . Finally, a production planning prototype system is developed, the algorithms presented in this paper are applied in solving lot-sizing process. The feasibility and application value of the algorithms presented in this paper is displayed fully.