Title: Hybrid Genetic Algorithm (GA) for job shop scheduling problems and its sensitivity analysis
Authors: Shahid Maqsood; Sahar Noor; M. Khurshid Khan; Alastair Wood
Addresses: School of Engineering, Design and Technology, University of Bradford, Bradford, UK. ' Department of Industrial Engineering, KPK University of Engineering and Technology, Peshawar, Pakistan. ' School of Engineering, Design and Technology, University of Bradford, Bradford, UK. ' School of Engineering, Design and Technology, University of Bradford, Bradford, UK
Abstract: The Job Shop Scheduling Problem (JSSP) is a hard combinatorial optimisation problem. This paper presents a heuristic-based Genetic Algorithm (GA) or Hybrid Genetic Algorithm (HGA) with the aim of overcoming the GA deficiency of fine tuning of solution around the optimum, and to achieve optimal or near optimal solutions for benchmark JSSP. The paper also presents a detail GA parameter analysis (also called sensitivity analysis) for a wide range of benchmark problems from JSSP. The findings from the sensitivity analysis or best possible parameter combination are then used in the proposed HGA for optimal or near optimal solutions. The experimental results of the HGA for several benchmark problems are encouraging and show that HGA has achieved optimal solutions for more than 90% of the benchmark problems considered in this paper. The presented results will provide a reference for selection of GA parameters for heuristic-based GAs for JSSP.
Keywords: HGA; hybrid genetic algorithms; sensitivity analysis; parameters; optimisation; JSSP; job shop scheduling problem; HybH; hybrid heuristics.
International Journal of Intelligent Systems Technologies and Applications, 2012 Vol.11 No.1/2, pp.49 - 62
Received: 21 Sep 2011
Accepted: 30 Nov 2011
Published online: 23 Apr 2012 *