A biased random-key genetic algorithm for job-shop scheduling
José F. Gonçalves (jfgoncalfep.up.pt)
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 (1956), is applied to improve the solution. The new heuristic is tested on a set of 165 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.
Keywords: Job-shop; Scheduling; Genetic algorithm; Biased random-key genetic algorithm; Heuristics; Random keys, Graphical method.
Category 1: Applications -- OR and Management Sciences (Scheduling )
Category 2: Combinatorial Optimization
Category 3: Combinatorial Optimization (Meta Heuristics )
Citation: AT&T Labs Research Technical Report, Florham Park, NJ 07932, April 2011.
Entry Submitted: 04/18/2011
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|