ant colony optimization for precedence-constrained heterogeneous multiprocessor assignment problem
An ant colony optimization approach, named MPAACO, for the Precedence-Constrained Heterogeneous Multiprocessor Assignment Problem (PCHMAP) is presented. The main characteristics of MPAACO are novel pheromone matrix and solution construction scheme. Separating processor selection steps from task selection steps, ant colony has full flexibility to construct new solution. Three-dimensional pheromone matrix can record each solution construction step precisely. When combined with heuristic information, they endow MPAACO the ability to find high quality schedules of PCHMAP quickly. We tested the algorithm on a set of benchmark problems from the [18]. The result shows that for 77\% of all benchmark for Precedence-Constrained Homogeneous Multiprocessor Assignment Problem, a special case of PCHMAP, the algorithm can get the optimal in just one try. For PCHMAP problems, MPAACO outperforms other algorithms significantly.
ant colony optimization ant colony system dag scheduling heterogeneous environment precedence-constrained problems.