An incremental ant colony optimization based approach to task assignment to processors for multiprocessor scheduling

任务调度优化是多处理器环境(如并行和分布式系统)取得良好性能所面临的最重要挑战之一。目前大多数任务调度算法基于列表调度法,该方法的基本思路是,以列表的形式准备一系列待调度的节点,赋予这些节点不同优先级,然后不断去除列表中优先级最高的节点,并将其分配给具有最早开始时间(Earliest start time,EST)的处理器。由此可见,该算法的完成时间主要由两大因素决定:(1)任务分配顺序的选择(次序子问题);(2)选定顺序的任务如何分配给处理器(分配子问题)。已有文献提出了许多解决次序子问题的好办法,但分配子问题少有人涉及。本文研究结果显示:传统的按照最早开始时间分配任务的方法并非最优;基于蚁群优化算法,得到一种新的方法,可以获得高效得多的调度方案。

Optimized task scheduling is one of the most important challenges to achieve high performance in multiprocessor environments such as parallel and distributed systems. Most introduced task-scheduling algorithms are based on the so-called list scheduling technique. The basic idea behind list scheduling is to prepare a sequence of nodes in the form of a list for scheduling by assigning them some priority measurements, and then repeatedly removing the node with the highest priority from the list and allocating it to the processor providing the earliest start time （EST）. Therefore, it can be inferred that the makespans obtained are dominated by two major factors： （1） which order of tasks should be selected （sequence subproblem）; （2） how the selected order should be assigned to the processors （assignment subproblem）. A number of good approaches for overcoming the task sequence dilemma have been proposed in the literature, while the task assignment problem has not been studied much. The results of this study prove that assigning tasks to the processors using the traditional EST method is not optimum; in addition, a novel approach based on the ant colony optimization algorithm is introduced, which can find far better solutions.