GA with Priority Rules for Solving Job-Shop Scheduling Problems

Download files
Access & Terms of Use
open access
Abstract
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.
Persistent link to this record
DOI
Additional Link
Author(s)
Hasan, S. M. Kamrul
Sarker, Ruhul
Cornforth, David
Supervisor(s)
Creator(s)
Editor(s)
Translator(s)
Curator(s)
Designer(s)
Arranger(s)
Composer(s)
Recordist(s)
Conference Proceedings Editor(s)
Other Contributor(s)
Corporate/Industry Contributor(s)
Publication Year
2008
Resource Type
Conference Paper
Degree Type
UNSW Faculty
Files
download Camera-ready Version.pdf 191.08 KB Adobe Portable Document Format
Related dataset(s)