Applying Forward/Backward Scheduling to Multi-Colony Ant Algorithm in Solving Scheduling Problem.

This paper presents a new method of ant algorithm to solve the Job-shop Scheduling Problem (JSP) which minimizes the makespan. This algorithm includes two important features, forward/backward scheduling and multi-colony approach. In general, a schedule is constructed by ants working in a forward direction, constructs the solutions in order of the precedence of processing sequences. In this paper, ants working in a backward direction, constructs the solution in the reversing order of processing sequences are introduced. Two types of ants exchange the information via modifying the pheromone trail in the same pheromone matrix. In multi-colony approach colonies of ants work independently but additional information from other colonies is also included. The performance of the proposed algorithm is tested over the benchmark problems. The comprehensive numerical investigation illustrates clearly the advantage of embedding the forward/backward scheduling and multi-colony approach in ant algorithm. [ABSTRACT FROM AUTHOR]