A hybrid ant colony algorithm for Job Shop Scheduling Problem

Job Shop Scheduling Problem (JSSP) is one of the NP-hard problems. JSSP has been investigated from a variety of perspectives resulting in several techniques combining heuristic as well as problem specific strategies. A hybrid Ant Colony Algorithm (HACA) is proposed which is derived from the existing methods, in the mean time, dynamic parameter control mechanism is adopted with a dividable parameter 8 which gives a new variable to control the computational rate of ant algorithm. The procedure of using HACA to solve JSSP can be divided into 3 phases, i.e. prophase, metaphase and anaphase- Each phase adopts special pheromone release method and transition probability expression. The results obtained from experimental evaluation oil JSSP shows that HACA strongly enhance the computational and convergent rate of basic Ant System algorithm.