Efficient nondominated sorting with genetic algorithm for solving multi-objective job shop scheduling problems

Abdalla Ali, Martin Birkett, Philip Hackney, David Bell

Research output: Chapter in Book/Report/Conference proceedingChapter

2 Citations (Scopus)

Abstract

In this paper a combination of Genetic Algorithm (GA) and a modified version of a very recent and computationally efficient approach to non-dominated sort called Efficient Non-dominated Sorting (ENS) has been introduced to solve the Multi-Objective Job Shop Scheduling Problem (MO-JSSP). Genetic algorithm was used to lead the search towards the Pareto optimality whilst an Efficient Non-dominated Sorting using a Sequential Strategy (ENS-SS) has been employed to determine the front to which each solution belongs, but instead of starting with the first front, the proposed algorithm starts the comparison with the last created front so far, and this is termed as a Backward Pass Sequential Strategy (BPSS). Efficient Non-dominated Sorting using the Backward Pass Sequential Strategy (ENS-BPSS) can reduce the number of comparisons needed for N solutions with M objectives when there are fronts and there exists only one solution in each front to O(M(N -1)). Computational results validate the effectiveness of the proposed algorithm.
Original languageEnglish
Title of host publication2016 International Conference Multidisciplinary Engineering Design Optimization (MEDO)
Place of PublicationPiscataway
PublisherIEEE
ISBN (Print)978-1-5090-2113-0
DOIs
Publication statusE-pub ahead of print - 17 Nov 2016

Keywords

  • Efficient Nondominated Sort
  • Job Shop Scheduling
  • Multi Objective optimization
  • Genetic Algorithm

Fingerprint

Dive into the research topics of 'Efficient nondominated sorting with genetic algorithm for solving multi-objective job shop scheduling problems'. Together they form a unique fingerprint.

Cite this