中文摘要：

多级生产批量计划（multilevel lot-sizing，MLLs）问题是物料需求计划（material requirements planning，MRP）系统中的关键问题已被证明是NP难问题。Scattersearch（SS）算法是一种亚启发式算法，其应用范围已涉及优化领域中的许多NP难问题。扩展了SS算法的应用范围，采用结合变异算子的混合SS算法＊hybrid scatter search，HSS）对具有小规模和中规模的装配结构无能力约束MLLS问题进行了求解。仿真实验表明HSS算法能够有效地求解MLLS问题其求解结果明显优于遗传算法的求解结果。

英文摘要：

Multilevel Lot-sizing （MLLS） problem, which has been proved as NP-hard, is a key problem in material requirements planning （MRP） systems. Scatter search （SS） algorithm is one of meta-heuristics. Currently, SS algorithm has been widely used to solve many NP-hard problems in optimization research fields. The application scope of SS algorithm was extended and an SS algorithm integrated with mutation operator （HSS） was adopted to solve the unconstrained MLLS problem with assembly structure. Simulation tests were done on the small-sized and medium-sized problems. Experimental results show that HSS algorithm is an effective tool for solving the unconstrained MLLS problem with assembly structure and that the results of HSS are obviously superior to those of GA.