An extended Akers graphical method with a biased random-key genetic algorithm for job-shop scheduling

An extended Akers graphical method with a biased random-key genetic algorithm for job-shop scheduling

0.00 Avg rating0 Votes
Article ID: iaor201524327
Volume: 21
Issue: 2
Start Page Number: 215
End Page Number: 246
Publication Date: Mar 2014
Journal: International Transactions in Operational Research
Authors: ,
Keywords: heuristics: genetic algorithms, heuristics: local search
Abstract:

This paper presents a local search, based on a new neighborhood for the job‐shop scheduling problem, and its application within a biased random‐key genetic algorithm. Schedules are constructed by decoding the chromosome supplied by the genetic algorithm with a procedure that generates active schedules. After an initial schedule is obtained, a local search heuristic, based on an extension of the graphical method of Akers, is applied to improve the solution. The new heuristic is tested on a set of 205 standard instances taken from the job‐shop scheduling literature and compared with results obtained by other approaches. The new algorithm improved the best‐known solution values for 57 instances.

Reviews

Required fields are marked *. Your email address will not be published.