A job shop oriented virus genetic algorithm

Prematurity and slow convergence are two problems existing in GA (genetic algorithm) for the NP-hard JSP (job shop problems). JVGA (job shop oriented virus 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. JVGA overcomes the problems of prematurity and convergence. Experimental results show that JVGA can efficiently solve JSP and can obtain optimums on some instances. As well, JVGA outperforms GA in performance on average.