Solving the Flexible Job Shop Scheduling Problem Based on Memetic Algorithm
Flexible job shop scheduling problem (FJSP) is a well known NP-hard combinatorial optimization problem due to its very large search space and many constraint between jobs and machines. Evolutionary algorithms are the most widely used techniques in solving FJSP. Memetic algorithm is a hybrid evolutionary algorithm that combines the local search strategy and global search strategy. In this paper, an effective memetic algorithm is proposed to solve the FJSP. In the proposed algorithm, variable neighborhood search is adopted as local search algorithm. The neighborhood functions is generated by exchanging and inserting the key operations which belong to the critical path. The optimization objective is to minimize makespan. The experimental results obtained from proposed algorithm show that the proposed algorithm is very efficient and effective for all tested problems.
Flexible job shop scheduling problem memetic algorithm variable neighborhood
Guohui Zhang
Zhengzhou Institute of Aeronautical Industry Management, Zhengzhou, 450015, China
国际会议
武汉
英文
1-5
2012-07-29（万方平台首次上网日期，不代表论文的发表时间）