International Journal of Advanced Computing and Communication Systems

A Multi objective Memetic Algorithm For Flexible Job Shop Problem

Bhuvana J and Sowntheriya G, Department of CSE SSN College of Engineering, Chennai, TamilNadu, India.

International Journal of Advanced Computing and Communication Systems

ISSN (Online) : 2347 - 9299

ISSN (Print) : 2347 - 9280

Received On :

Revised On :

Accepted On :

Published On :

Volume 04, Issue 01

Page No :001-007

Abstract

The job shop problem with parallel machine is akind of flexible job shop problem, in which the number of machines is greater than one. The Flexible Job-shop Scheduling Problem(FJSP) is a most commonly used scheduling model. The FJSP is derived from the classical job-shop scheduling problem and it allows an operation to be processed by any machine from a given set. Two challenges in this problem are, assigning each operation to a machine and to order the operations on the machines with minimization of the makespan, critical workload, and total machine workload as the objectives. We propose a Memetic Algorithm, that combines the local search procedure with NSGAII (Non-Dominated Sorting Genetic Algorithm II) for solving multiobjective flexible job shop problem. A Local Search (LS) procedure is implemented whose rate of search will be dynamically changed according to the population across generations. This procedure dynamically decides the number of individuals that undergo local search. The proposed algorithm is compared with the state-of-the-art which solves MO-FJSP on well-known benchmark instances. In order to evaluate the performance of the proposed MA, the Inverted Generational Distance (IGD) and the set coverage metrics have been used as indicators. The results show that the proposed memetic algorithm with dynamic local search rate outperforms the algorithm with fixed local search rate.

Keywords

Multiobjective, Flexible Job Shop Problem (FJSP), GeneticAlgorithm (GA), Nondominated Sorting Genetic Algorithm II(NSGA-II), local search (LS), Memetic Algorithm (MA).

Cite this Article

Bhuvana J and Sowntheriya G, “A Multi objective Memetic Algorithm For Flexible Job Shop Problem, ”International Journal of Advanced Computing and Communication Systems, pp. 001-007, March, 2017.

Copyright

© 2017 Bhuvana J and Sowntheriya G. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.