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

Scatter Search Algorithm for Unconstrained Multilevel Lot-sizing Problems

作　　者：韩毅[1] 卢勇虎[1] 周根贵[1] 王晓晴[2] 王立岩[2] 牟立峰[2] 

机构地区：[1]浙江工业大学经贸管理学院,杭州310023 [2]东北大学教育部流程工业综合自动化重点实验室,沈阳110004

出　　处：《系统仿真学报》2009年第13期3902-3905,3913,共5页Journal of System Simulation

基　　金：国家自然科学基金(70671095)

摘　　要：多级生产批量计划(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.

关 键 词：SCATTER search算法 亚启发式算法 多级生产批量计划问题 物料需求计划 装配结构 无能力约束 

分 类 号：TP29[自动化与计算机技术—检测技术与自动化装置]