A Genetic Algorithm Applied To Job Shop Scheduling Problem

Job Shop Scheduling problem is a typical NP-Hard Problem, and it is a important issues in CIMS area. It is impossible to find the global optimum in polynomial complexity. Good algorithms for JSP problem can promote porductivity of enterprises. So this thesis can provide good results for both theory and practice. In this thesis, a Simple Genetic Algorithm (SGA) is proposed for JSP. By using the JGAP java software package, the Simple Genetic Algorithm (SGA) can be easily used to apply evolution principles for JSP problem. Besides, a decimal encoding method for chromosome based on processing routes is presented which can avoid deadlock and switch solutions to chromosomes and vice versa easily. Experimental results of some test data show that SGA can efficiently solve the JSP for our company.