A hybrid evolutionary algorithm to solve the job shop scheduling problem

Edwin Tai Chiu Cheng, Bo Peng, Zhipeng Lü

Research output: Journal article publicationJournal articleAcademic researchpeer-review

21 Citations (Scopus)

Abstract

This paper presents a Hybrid Evolutionary Algorithm (HEA) to solve the Job Shop Scheduling Problem (JSP). Incorporating a tabu search procedure into the framework of an evolutionary algorithm, the HEA embraces several distinguishing features such as a longest common sequence based recombination operator and a similarity-and-quality based replacement criterion for population updating. The HEA is able to easily generate the best-known solutions for 90 % of the tested difficult instances widely used in the literature, demonstrating its efficacy in terms of both solution quality and computational efficiency. In particular, the HEA identifies a better upper bound for two of these difficult instances.
Original languageEnglish
Pages (from-to)223-237
Number of pages15
JournalAnnals of Operations Research
Volume242
Issue number2
DOIs
Publication statusPublished - 1 Jul 2016

Keywords

  • Evolutionary algorithm
  • Job shop scheduling
  • Population updating
  • Recombination operator

ASJC Scopus subject areas

  • Decision Sciences(all)
  • Management Science and Operations Research

Cite this