Abstract—Flexible job-shop scheduling problem (FJSP) is very important in many research fields such as production management and combinatorial optimization. The FJSP problems cover two difficulties namely machine assignment problem and operation sequencing problem. In this paper, a hybrid of particle swarm optimization (PSO) algorithm and tabu search (TS) algorithm are presented to solve the FJSP with the criterion to minimize the maximum completion time (makespan). In the novel hybrid algorithm, PSO was used to produce a swarm of high quality candidate solutions, while TS was used to obtain a near optimal solution around the given good solution. The computational results have proved that the proposed hybrid algorithm is efficient and effective for solving FJSP, especially for the problems with large scale.
Index Terms—Flexible job shop scheduling problem; Particle swarm optimization; Tabu search algorithm; makespan
J.-Q. Li is with the College of Computer Science, Liaocheng University, Liaocheng 252059, People’s Republic of China, (email: lijunqing@lcu.edu.cn; lijunqing.cn@gmail.com; p2p_jql@126.com).
Q.-K. Pan is with the College of Computer Science, Liaocheng University, Liaocheng 252059, People’s Republic of China.
S.-X. Xie is with the College of Computer Science, Liaocheng University, Liaocheng 252059, People’s Republic of China.
B-X. Jia is with the College of Computer Science, Liaocheng University, Liaocheng 252059, People’s Republic of China.
Y-T. Wang is with the College of Computer Science, Liaocheng University, Liaocheng 252059, People’s Republic of China.
[PDF]
Cite: Jun-qing Li, Quan-ke Pan, Sheng-xian Xie, Bao-xian Jia and Yu-ting Wang, "A Hybrid Particle Swarm Optimization and Tabu Search Algorithm for Flexible Job-Shop Scheduling Problem,"
International Journal of Computer Theory and Engineering vol. 2, no. 2, pp. 189-194, 2010.
