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

Hamid Reza BOVEIRI

doi:10.1631/FITEE.1500394

Your Location：

Home >

Browse articles >

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

Regular Papers | Updated：2022-05-19

- An incremental ant colony optimization based approach to task assignment to processors for multiprocessor scheduling
- 基于渐进式蚁群优化的多处理器任务分配
- Frontiers of Information Technology & Electronic Engineering Vol. 18, Issue 4, Pages: 498-510(2017)
- Affiliations：
  
  Sama Technical and Vocational Training College, Islamic Azad University, Shoushtar Branch, Shoushtar, Iran
- Author bio：
  
  E-mail:boveiri@shoushtar-samacollege.ir
- Funds：
- DOI：10.1631/FITEE.1500394
  CLC： TP301
- Received：10 November 2015，
  
  Accepted：16 February 2017，
  
  Published：2017-04
- Accepted：
Scan QR Code
Hamid Reza BOVEIRI. An incremental ant colony optimization based approach to task assignment to processors for multiprocessor scheduling[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(4): 498-510.
DOI：

Hamid Reza BOVEIRI. An incremental ant colony optimization based approach to task assignment to processors for multiprocessor scheduling[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(4): 498-510. DOI： 10.1631/FITEE.1500394.

摘要

任务调度优化是多处理器环境（如并行和分布式系统）取得良好性能所面临的最重要挑战之一。目前大多数任务调度算法基于列表调度法，该方法的基本思路是，以列表的形式准备一系列待调度的节点，赋予这些节点不同优先级，然后不断去除列表中优先级最高的节点，并将其分配给具有最早开始时间（Earliest start ime

EST）的处理器。由此可见，该算法的完成时间主要由两大因素决定：（1）任务分配顺序的选择（次序子问题）；（2）选定顺序的任务如何分配给处理器（分配子问题）。已有文献提出了许多解决次序子问题的好办法，但分配子问题少有人涉及。本文研究结果显示：传统的按照最早开始时间分配任务的方法并非最优；基于蚁群优化算法，得到一种新的方法，可以获得高效得多的调度方案。

Abstract

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.

关键词

Keywords

references

TL Adam , , , KM Chandy , , , J Dickson . . A comparison of list scheduling for parallel processing systems . . Commun. ACM , , 1974 . . 17 ( ( 12 ): ): 685 - - 700 . . DOI: 10.1145/361604.361619 http://doi.org/10.1145/361604.361619 . .

A Al-Maasarani . . Priority-Based Scheduling and Evaluation of Precedence Graphs with Communication Times , , 1993 . . : Saudi Arabia : King Fahd University of Petroleum and Minerals , , MS Thesis . .

MA Al-Mouhamed . . Lower bound on the number of processors and time for scheduling precedence graphs with communication costs . . IEEE Trans. Softw. Eng. , , 1990 . . 16 ( ( 12 ): ): 1390 - - 1401 . . DOI: 10.1109/32.62447 http://doi.org/10.1109/32.62447 . .

J Baxter , , , JH Patel . . The LAST algorithm: a heuristic-based static task allocation algorithm . . 1989 . . Proc. Int. Conf. on Parallel Processing . . 217 - - 222 . . . .

HR Boveiri . . ACO-MTS: a new approach for multiprocessor task scheduling based on ant colony optimization . . 2010 . . Proc. IEEE Int. Conf. on Intelligent and Advanced Systems . . 1 - - 5 . . DOI: 10.1109/ICIAS.2010.5716203 http://doi.org/10.1109/ICIAS.2010.5716203 . .

HR Boveiri . . Assigning tasks to the processors for task-graph scheduling in parallel systems using learning and cellular learning automata . . 2014 . . Proc. 1st National Conf. on Computer Engineering and Information Technology . . 1 - - 8 . . . .

HR Boveiri . . Multiprocessor task graph scheduling using a novel graph-like learning automata . . Int. J. Grid Distr. Comput. , , 2015 . . 8 ( ( 1 ): ): 41 - - 54 . . DOI: 10.14257/ijgdc.2015.8.1.05 http://doi.org/10.14257/ijgdc.2015.8.1.05 . .

P Chrétienne , , , EG Coffman , , , JK Lenstra , , , 等 . . Scheduling Theory and Its Application , , 1995 . . John Wiley & Sons , , New York . .

M Dorigo , , , V Maniezzo , , , A Colorni . . Positive Feedback as a Search Strategy . . 1991 . . Technical Report No. 91-016, Politecnico di Milano, Milan, Italy . . . .

M Dorigo , , , G di Caro , , , L Gambardella . . Ant algorithm for discrete optimization . . Artif. Life , , 1999 . . 5 ( ( 2 ): ): 137 - - 172 . . DOI: 10.1162/106454699568728 http://doi.org/10.1162/106454699568728 . .

JJ Hwang , , , YC Chow , , , FD Anger , , , 等 . . Scheduling precedence graphs in systems with interprocessor communication times . . SIAM J. Comput. , , 1989 . . 18 ( ( 2 ): ): 244 - - 257 . . DOI: 10.1137/0218016 http://doi.org/10.1137/0218016 . .

R Hwang , , , M Gen , , , H Katayama . . A comparison of multiprocessor task scheduling algorithms with communication costs . . Comput. Oper. Res. , , 2008 . . 35 ( ( 3 ): ): 976 - - 993 . . DOI: 10.1016/j.cor.2006.05.013 http://doi.org/10.1016/j.cor.2006.05.013 . .

B Kruatrachue , , , TG Lewis . . Duplication Scheduling Heuristics (DSH): a New Precedence Task Scheduler for Parallel Processor Systems , , 1987 . . Technical Report No. OR 97331, Oregon State University, Corvallis . . . .

Y Kwok , , , I Ahmad . . Static scheduling algorithms for allocating directed task graphs to multiprocessors . . ACM Comput. Surv. , , 1998 . . 31 ( ( 4 ): ): 406 - - 471 . . DOI: 10.1145/344588.344618 http://doi.org/10.1145/344588.344618 . .

C McCreary , , , H Gill . . Automatic determination of grain size for efficient parallel processing . . Commun. ACM , , 1989 . . 32 ( ( 9 ): ): 1073 - - 1078 . . DOI: 10.1145/66451.66454 http://doi.org/10.1145/66451.66454 . .

MR Meybodi , , , H Beigy , , , M Taherkhani . . Cellular learning automata and its applications . . J. Sci. Technol. Sharif Univ. , , 2004 . . 25 54 - - 77 . . . .

KS Narendra , , , M.A.L. Thathachar . . Learning automata: a survey . . IEEE Trans. Syst. Man Cybern. , , 1974 . . SMC-4 ( ( 4 ): ): 323 - - 334 . . DOI: 10.1109/TSMC.1974.5408453 http://doi.org/10.1109/TSMC.1974.5408453 . .

GC Sih , , , EA Lee . . A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures . . IEEE Trans. Parall. Distr. Syst. , , 1993 . . 4 ( ( 2 ): ): 175 - - 187 . . DOI: 10.1109/71.207593 http://doi.org/10.1109/71.207593 . .

S Wolfram . . Cellular automata . . Los Alamos Sci. , , 1983 . . 9 2 - - 27 . . . .

MY Wu , , , DD Gajski . . Hypertool: a programming aid for message-passing systems . . IEEE Trans. Parall. Distr. Syst. , , 1990 . . 1 ( ( 3 ): ): 330 - - 343 . . DOI: 10.1109/71.80160 http://doi.org/10.1109/71.80160 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰