Abstract: A hybrid ant colony algorithm is proposed to solve the dual resource constrained job shop scheduling problem with heterogeneous workers. Based on technological constraints and tabu search ideas, a candidate aggregate of result is built for every ant to contract the search space and improve the search efficiency. Some heuristic policies for resource allocation are imposed to actualize the best collocating of the machines and the worker forces during the ant routing process. Meanwhile, the simulated annealing algorithm is taken as a local search mechanism to improve the global convergence ability of the algorithm. After the theoretical analysis of the global convergence via Markov chain, according to the experiments and statistical analysis, the optimal combination of parameters and the optimal resource allocation policy are chosen. The hybrid ant colony algorithm has strong search ability and good robustness for this problem based on the result of comparing experiment on random benchmarks.

Key words: Dual resource constrained, Hybrid ant colony algorithm, Markov chain