改进蚁群算法求解同型机任务调度问题

Improved ant colony algorithm to solve identical parallel machine task scheduling problem

针对并行与分布式系统中的同型机调度问题,提出了一种改进蚁群算法。结合问题具体特点,给出了蚂蚁分配方案的生成策略,设计了一种新颖的基于任务适合度的信息素表示方法,以实现信息素的有效累积;改进了状态转移规则,通过对阈值的自适应调整使算法能根据搜索进度确定查找区域;在对信息素全局更新前,对每轮迭代获得的最好解进行变邻域搜索,避免算法陷入局部最优,提高收敛速度。仿真结果表明,改进算法有较强的寻优能力和稳定的求解质量。

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-adaptabili- ty 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 neighbor- hood 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.