A Hybrid Genetic Algorithm for the Job Shop Scheduling Problem

Gonçalves, José Fernando; Mendes, J. J. M.; Resende, Maurício G. C.

http://hdl.handle.net/10400.22/10058

Use this identifier to reference this record.

Name:	Description:	Size:	Format:
ART_JorgeMendes_CIDEM_2005.pdf		307.74 KB	Adobe PDF	Download

Send Feedback

Authors

Gonçalves, José Fernando

Mendes, J. J. M.

Resende, Maurício G. C.

Abstract(s)

This paper presents a hybrid genetic algorithm for the Job Shop Scheduling problem. The chromosome representation of the problem is based on random keys. The schedules are constructed using a priority rule in which the priorities are defined by the genetic algorithm. Schedules are constructed using a procedure that generates parameterized active schedules. After a schedule is obtained a local search heuristic is applied to improve the solution. The approach is tested on a set of standard instances taken from the literature and compared with other approaches. The computation results validate the effectiveness of the proposed algorithm.