A Hybrid Variable Neighborhood Search Algorithm for Solving Multi-Objective Flexible Job Shop Problems

Computer Science and Information Systems

Jun-qing Li¹ 

[1] College of Computer Science,Liaocheng University

关键词: Flexible Job Shop Scheduling Problem;    Multi-objective;    Genetic Algorithm;    Variable Neighborhood Search;   

DOI  :  10.2298/CSIS090608017L

学科分类：社会科学、人文和艺术（综合）

来源: Computer Science and Information Systems

【 摘 要 】

In this paper, we propose a novel hybrid variable neighborhood search algorithm combining with the genetic algorithm (VNS+GA) for solving the multi-objective flexible job shop scheduling problems (FJSPs) to minimize the makespan, the total workload of all machines, and the workload of the busiest machine. Firstly, a mix of two machine assignment rules and two operation sequencing rules are developed to create high quality initial solutions. Secondly, two adaptive mutation rules are used in the hybrid algorithm to produce effective perturbations in machine assignment component. Thirdly, a speed-up local search method based on public critical blocks theory is proposed to produce perturbation in operation sequencing component. Simulation results based on the well-known benchmarks and statistical performance comparisons are provided. It is concluded that the proposed VNS+GA algorithm is superior to the three existing algorithms, i.e., AL+CGA algorithm, PSO+SA algorithm and PSO+TS algorithm, in terms of searching quality and efficiency.

【 授权许可】

CC BY-NC-ND