- Title
- GA with priority rules for solving job-shop scheduling problems
- Creator
- Hasan, S. M. Kamrul; Sarker, Ruhul; Cornforth, David
- Relation
- 2008 IEEE Congress on Evolutionary Computation (CEC 2008). Proceedings of the 2008 IEEE Congress on Evolutionary Computation (Hong Kong 1-6 June, 2008) p. 1913-1920
- Publisher Link
- http://dx.doi.org/10.1109/CEC.2008.4631050
- Publisher
- Institute of Electrical and Electronics Engineers (IEEE)
- Resource Type
- conference paper
- Date
- 2008
- Description
- The Job-Shop Scheduling Problem (JSSP) is considered as one of the difficult combinatorial optimization problems and treated as a member of NP-complete problem class. In this paper, we consider JSSPs with an objective of minimizing makespan while satisfying a number of hard constraints. First, we develop a genetic algorithm (GA) based approach for solving JSSPs. We then introduce a number of priority rules such as partial reordering, gap reduction and restricted swapping to improve the performance of the GA. We run the GA incorporating these rules in a number of different ways. We solve 40 benchmark problems and compared their results with that of a number of well-known algorithms. We obtain optimal solutions for 27 problems, and the overall performance of our algorithms is quite encouraging.
- Subject
- combinatorial mathematics; genetic algorithms; job shop scheduling
- Identifier
- http://hdl.handle.net/1959.13/1057729
- Identifier
- uon:16249
- Identifier
- ISBN:9781424418237
- Language
- eng
- Reviewed
- Hits: 821
- Visitors: 1006
- Downloads: 0
Thumbnail | File | Description | Size | Format |
---|