Paper Info
Title
An Extended Akers Graphical Method With A Biased Random-Key Genetic Algorithm For Job-Shop Scheduling
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 1956 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.
Year
DOI
Venue
2014
10.1111/itor.12044
INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH
Keywords
Field
DocType
job-shop, scheduling, genetic algorithm, biased random-key genetic algorithm, heuristics, random keys, graphical approach
Heuristic,Mathematical optimization,Job shop scheduling,Computer science,Job shop,Flow shop scheduling,Schedule,Local search (optimization),Population-based incremental learning,Genetic algorithm
Journal
Volume
Issue
ISSN
21
2
0969-6016
Citations 
PageRank 
References 
15
0.77
30
Authors
2
Name
Order
Citations
PageRank
José Fernando Gonçalves173637.31
Mauricio G. C. Resende23729336.98