Journal's Facebook pageUDC 005.8:518.876.3, DOI:10.2298/CSIS0906080
A Hybrid Variable Neighborhood Search Algorithm for Solving Multi-Objective Flexible Job Shop Problems
- College of Computer Science,Liaocheng University
Liaocheng, 252059, People�s Republic of China
{lijunqing, qkpan, xsx}@lcu.edu.cn
Abstract
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.
Key words
Flexible Job Shop Scheduling Problem; Multi-objective; Genetic Algorithm; Variable Neighborhood Search
Digital Object Identifier (DOI)
https://doi.org/10.2298/CSIS090608017L
Publication information
Volume 7, Issue 4 (December 2010)
Year of Publication: 2010
ISSN: 2406-1018 (Online)
Publisher: ComSIS Consortium
Full text
Available in PDF
Portable Document Format
How to cite
Li, J., Pan, Q., Xie, S.: A Hybrid Variable Neighborhood Search Algorithm for Solving Multi-Objective Flexible Job Shop Problems. Computer Science and Information Systems, Vol. 7, No. 4, 907-930. (2010), https://doi.org/10.2298/CSIS090608017L
