关键词: 混合流水车间调度, 改进遗传算法, 变邻域搜索, NEH启发式算法

Abstract: 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.

Key words: hybrid flow shop scheduling, improved genetic algorithm, variable neighborhood search, NEH heuristic