An ant colony algorithm for job shop scheduling problem

Prematurity and unsteadiness are two problems unsolved in GA (genetic algorithm) for the NP-hard JSSP (job shop scheduling problems). An ant colony algorithm (ACA for short) is proposed for JSSP with the objective of makespan minimization. A probability priority is introduced for the initial distribution of ants. Moreover, quality and robustness of solutions are improved by the nature of feedback and parallel paradigm of ACA and GA are run on many instances with different sizes. Experimental results show that ACA can efficiently solve JSSP and can obtain the optimums on some instances. As well, ACA outperforms GA in performance on average.