王文涛，穆晓峰，王玲霞

(中南民族大学 计算机科学学院，武汉 430074)



基于蚁群算法的无联系并行机调度问题的仿真研究

王文涛，穆晓峰，王玲霞

(中南民族大学 计算机科学学院，武汉 430074)

摘要针对无联系并行机调度求解问题，引入了蚁群算法的思想.基于转移概率构建的信息素迭代模型，研究了无联系并行机调度问题的求解过程.基于Python的仿真实验结果表明：通过蚁群算法可以得到其近似解；更进一步探求了任务次序对解的影响；通过实验探索了此算法的时间性能.

关键词并行机；任务调度；蚁群算法

Study on Unrelated Parallel Machine Scheduling Problem Based on the Ant Colony Algorithm

WangWentao,MuXiaofeng,WangLingxia

(College of Computer Science, South-Central University for Nationalities,Wuhan 430074,China)

AbstractAiming at unrelated parallel machine scheduling problem, we introduced the idea of ant colony algorithm. Based on pheromone iterative model constructed by transfer probability, we researched the solving process of unrelated parallel machine scheduling problem. The results of the simulation test based on Python illustrate that ant colony algorithm can reach an approximate solution. Furthermore, we explored the influence of different task sequence on solution. At last, we performed some experiment to analyze time performance of the algorithm.

Keywordsparallel machine；task scheduling；ant colony algorithm

在人们生产生活的诸多领域都存在着调度问题，例如工厂如何分配工件在合适的机器上执行；此外，随着互联网的发展，云计算已经成为一大热点，如何对云环境下的资源进行调度，本质上也是此类问题.优良的调度策略能够极大地提高生产效率.

本文对无联系并行机器调度问题(UPMSP)[1]进行研究.问题可以描述如下：有N个任务在时间点0处开始，有M台机器可供这些任务运行，最终的调度目标是使这些任务总的完成时间(makespan)最小，其中M

在M不大的情况下可以在多项式时间内找到最优解；反之，是一个NP-hard问题，采用启发式的算法可以在合理的时间内找到一个近似解[2,3].

一些研究者开发了确定性算法来解决UPMSP问题.在文[4]和[5]中，Liaw和Lancia开发了分支定界法来找出最优解.

另外一些研究者考虑采用启发式的方法来解决此问题.在文[6]中，作者考虑了增加负载均衡这……