Two Genetic Algorithm For Job Shop Problems

JSP (Job shop problem) is typically NP-hard, which means that it is impossible to find the global optimum in polynomial complexity. JSP is one of the key problems in the production management. Good algorithms for this problem can promote productivity of enterprises. So this thesis can provide good results for both theory and practice. In recent years, meta-heuristics and heuristics are two kinds of algorithm for JSP. However, they are different in CPU-time and performance. Meta-heuristics can always obtain better solutions than heuristics but they need much more CPU-times. As well, robustness of heuristics is good but optimum can seldom be obtained. CPU-time is not critical as the development of computer techniques. So the quality of solutions is pursued by most researchers at present by integrating some heuristic with a meta-heuristic. In this thesis, a Virus Evolutionary Genetic Algorithm (VEGA) and a Hybrid Genetic Algorithm (HGA) are respectively proposed for JSP. Pre-maturity and slow-convergence are two issues existing in Genetic Algorithm (GA) for JSP. For the above two issues, JVGA (Job shop oriented Virus evolutionary Genetic Algorithm) is developed for JSP with the objective of makespan minimization. JVGA searches the solution space in both depth and width. A new virus density scheme is introduced to improve the diversity of the population and to evaluate some part of genes in the chromosomes in quantity. This scheme can overcome the intrinsic premature of GA. Besides, a decimal encoding method based on processing routes is presented which can avoid deadlock and switch solutions to chromosomes and vice versa easily. Experimental results of 17 typical benchmarks show that JVGA can efficiently solve JSP. The convergent speed is greatly affected by the quality of the initial solution of GA. So Modified Shifting Bottleneck (MSB) algorithm for JSP is adopted to generate a seed for the initial population of GA, the remaining seeds are randomly produced. By combining MSB with GA, HGA (hybrid genetic algorithm) is described with elitist strategy. Performance of HGA is good due to the good performance of MSB.