变邻域改进遗传算法求解混合流水车间调度问题

Improved genetic algorithm variable neighborhood search for solving hybrid flow shop scheduling problem

针对混合流水车间调度问题的NP难特性,提出一种改进的混合变邻域搜索的遗传算法。建立了数学模型,提出了算法的总体流程,设计了基于操作的编码和解码方法,并采用NEH启发式算法产生初始种群。随机采用基于位置的交叉和线性次序交叉,选用反转逆序的变异算子,交叉变异后合并子代与父代,保留较优个体,对当前最优个体执行变邻域搜索,以增强遗传算法的局部搜索能力。通过初始对比实验,证明了NEH启发式算法能够产生质量更好的初始解,随机采取两种交叉算子能够提高算法的搜索效率,标准算例实验结果表明所提算法能够有效求解混合流水车间调度问题。

Aiming at the NP-hard feature of Hybrid Flow Shop Scheduling Problem（HFSP）,an Improved Genetic Algorithm Variable Neighborhood Search（IGA-VNS）was proposed.The optimization model of HFSP was formulated,and the flowchart of IGA-VNS was presented.The operation based encoding and decoding schemes were designed and NEH heuristic was employed to generate the initial population.The Position-Based Crossover（PBX）and the Liner Order Crossover（LOX）operators were chosen randomly to explore the solution space variously.The inversion operator was employed to mutate the population.After crossover and mutation,the offspring and the parents were compared and the better individuals were kept to generate the offspring.Further,a variable neighborhood search included five local search methods was carried out on the current optimal individual to exploit its neighbor in different ways.The experiment results showed that NEH heuristic generated a better initial population and the randomly chosen crossover operators could improve the search efficiency of algorithm and the proposed algorithm could solve the HFSP effectively and efficiently.