UDC 005.8:518.876.3, DOI:10.2298/CSIS0906080

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

Jun-qing Li, Quan-ke Pan and Sheng-xian Xie

  1. 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: 1820-0214 (Print) 2406-1018 (Online)
Publisher: ComSIS Consortium

Full text

DownloadAvailable 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)