Research On An Ant Colony Algorithm For Job Shop Scheduling Problem

The Job-shop scheduling problem is a NP-hard. The fact that it is impossible to find the global optimum in polynomial complexity has been proved. Ant colony algorithm (ACA), which is an optimization searching technique, has been widely noticed during recent years. An ant colony algorithm (ACA for short) is proposed for two Job-shop scheduling problem. 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. 1. Through the analysis and studying of Ant colony algorithm and Job-shop scheduling problem, a disjunctive graph is introduced. The detail description of the proposed ACA algorithm is described. Last, ACA and GA are run on 28 instances with different sizes. Experimental results show that ACA can efficiently solve Job-shop scheduling problem and can obtain the optimums on some instances. As well, ACA outperforms GA in performance on average. 2. Through the analysis and studying of Ant colony algorithm and Flow shop scheduling problem, a construction graph is introduced. Two ant colony algorithms (FACA and PACA) are proposed and analyzed for solving the flow shop scheduling problem with the objective of minimizing the flowtime. The Initialization of parameters and updating of trail intensities and probability is described respectively and a newly local search technique is proposed. Last is the experiment and the comparison shows that the PACA performs better than the FACA in the case of relatively large-sized problems than in the case of relatively small-sized problems. As well, PACA outperforms FACA in performance on average.