关键词: 同型机调度, 任务分配, 蚁群算法, 变邻域搜索算法

Abstract: An improved ant colony algorithm is presented to solve the problem of scheduling tasks on identical parallel machines in parallel and distributed systems.According to the characteristics of the identical parallel machine scheduling problem，the method of dynamic generation of the network of ants is developed，and a novel representation of pheromone，which makes use of the task fitness value to accumulate pheromone effectively，is designed.To improve the self-adaptability of the algorithm，the state transfer rule is modified so that the algorithm can adjust the searching space according to the progress of the algorithm convergence.In order to accelerate the converging rate of the algorithm，a variable neighborhood searching is performed on the best solution every iteration before the global pheromone is updated.Simulation results show that the performance of the heuristic algorithm is better on finding optimum or near-optimal solutions and providing stable solutions.

Key words: identical parallel machine scheduling, task assigning, ant colony algorithm, variable neighborhood search algorithm