Scatter search算法求解无能力约束生产批量计划问题

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