Optimization Online


A biased random-key genetic algorithm for job-shop scheduling

José F. Gonçalves (jfgoncal***at***fep.up.pt)
Mauricio G.C. Resende (mgcr***at***research.att.com)

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.

Download: [PDF]

Entry Submitted: 04/18/2011
Entry Accepted: 04/19/2011
Entry Last Modified: 02/25/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society