基于文化基因算法的集成工艺规划与调度研究

Memetic algorithm for integrated process planning and scheduling

建立了与工艺规划集成的调度问题的数学模型.以最大完工时间为目标,设计一种混合文化基因算法求解该问题.在提出算法中,设计了新型编码和主动解码方案,使用变邻域搜索(VNS)算法进行局部搜索,引入了高效的邻域结构以强化算法的局部搜索能力,并提出了一种个体扰动方法,以避免群体多样性趋于单一,使得提出算法在分散搜索和集中搜索之间达到更合理的平衡.为测试算法的性能,对现有的基准问题进行了测试,有21个实例达到了下界或得到改进,成为当前新的最优解.对比已有的最优结果可见:提出的算法可高效地求解工艺规划与车间调度集成问题且优于其他算法.

A mathematical model of the problem was first established based on the characteristics of the problem.A memetic algorithm was developed to address the problem with makespan criterion.In the algorithm,a novel coding scheme with active scheduling based decoding method was developed.The variable neighborhood search（VNS）algorithm was introduced as the local search method.Effective neighborhood structures were adopted in VNS to enhance the ability for local exploitation.Meanwhile,an individual perturbation method was also introduced to avoid the homogeneity of the population.In such a case,the algorithm can strike a balance between evolution and local exploitation.To test the performance of the memetic algorithm,the algorithm has been tested on Kim＇s benchmark instances and the results of 21 instances either reach corresponding lower bounds or become current best solutions.According to the comparison with existing best results,it shows that the algorithm is able to solve the integrated process planning and scheduling（IPPS）problem effectively and is better than other algorithms.