论文部分内容阅读
任务调度优化是多处理器环境(如并行和分布式系统)取得良好性能所面临的最重要挑战之一。目前大多数任务调度算法基于列表调度法,该方法的基本思路是,以列表的形式准备一系列待调度的节点,赋予这些节点不同优先级,然后不断去除列表中优先级最高的节点,并将其分配给具有最早开始时间(Earliest start time,EST)的处理器。由此可见,该算法的完成时间主要由两大因素决定:(1)任务分配顺序的选择(次序子问题);(2)选定顺序的任务如何分配给处理器(分配子问题)。已有文献提出了许多解决次序子问题的好办法,但分配子问题少有人涉及。本文研究结果显示:传统的按照最早开始时间分配任务的方法并非最优;基于蚁群优化算法,得到一种新的方法,可以获得高效得多的调度方案。
Task scheduling optimization is one of the most important challenges for good performance in multiprocessor environments such as parallel and distributed systems. At present, most task scheduling algorithms are based on the list scheduling method. The basic idea of this method is to prepare a series of nodes to be scheduled in the form of a list, assign these nodes different priorities, and then continuously remove the nodes with the highest priority in the list and It is assigned to the processor with the Earliest Start Time (EST). Thus, the completion time of the algorithm is mainly determined by two factors: (1) the choice of task allocation order (sub-sub-problems); (2) how the task of the selected order is assigned to the processor (sub-problem of allocation). The literature has proposed many good ways to solve the sub-sub-problems, but few sub-problems are involved. The research results show that the traditional method of assigning tasks according to the earliest start time is not optimal. Based on the ant colony optimization algorithm, a new method is obtained, which can obtain a much more efficient scheduling solution.