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: | Gonalves Jos Fernando, Resende Mauricio G C |
Keywords: | heuristics: genetic algorithms, heuristics: local search |
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.