Full Text:   <1880>

CLC number: TP301

On-line Access: 2017-04-12

Received: 2015-11-10

Revision Accepted: 2016-02-16

Crosschecked: 2017-03-28

Cited: 1

Clicked: 4647

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
Open peer comments

Frontiers of Information Technology & Electronic Engineering  2017 Vol.18 No.4 P.498-510

http://doi.org/10.1631/FITEE.1500394


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


Author(s):  Hamid Reza Boveiri

Affiliation(s):  Sama Technical and Vocational Training College, Islamic Azad University, Shoushtar Branch, Shoushtar, Iran

Corresponding email(s):   boveiri@shoushtar-samacollege.ir

Key Words:  Ant colony optimization, List scheduling, Multiprocessor task graph scheduling, Parallel and distributed systems


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.

@article{title="An incremental ant colony optimization based approach to task assignment to processors for multiprocessor scheduling",
author="Hamid Reza Boveiri",
journal="Frontiers of Information Technology & Electronic Engineering",
volume="18",
number="4",
pages="498-510",
year="2017",
publisher="Zhejiang University Press & Springer",
doi="10.1631/FITEE.1500394"
}

%0 Journal Article
%T An incremental ant colony optimization based approach to task assignment to processors for multiprocessor scheduling
%A Hamid Reza Boveiri
%J Frontiers of Information Technology & Electronic Engineering
%V 18
%N 4
%P 498-510
%@ 2095-9184
%D 2017
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.1500394

TY - JOUR
T1 - An incremental ant colony optimization based approach to task assignment to processors for multiprocessor scheduling
A1 - Hamid Reza Boveiri
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 18
IS - 4
SP - 498
EP - 510
%@ 2095-9184
Y1 - 2017
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.1500394


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.

This is a good, scientifically sound paper on using ACO for scheduling tasks on multiple processors. The author presents a theoretically solid approach, describes it well and uses other previously published datasets for comparison. It provides a small useful improvement over other methods.

基于渐进式蚁群优化的多处理器任务分配

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

关键词:蚁群优化;列表调度;多处理器任务图调度;并行与分布式系统

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[1]Adam, T.L., Chandy, K.M., Dickson, J., 1974. A comparison of list scheduling for parallel processing systems. Commun. ACM, 17(12):685-700.

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

[3]Al-Mouhamed, M.A., 1990. Lower bound on the number of processors and time for scheduling precedence graphs with communication costs. IEEE Trans. Softw. Eng., 16(12):1390-1401.

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

[5]Boveiri, H.R., 2010. ACO-MTS: a new approach for multiprocessor task scheduling based on ant colony optimization. Proc. IEEE Int. Conf. on Intelligent and Advanced Systems, p.1-5.

[6]Boveiri, H.R., 2014. Assigning tasks to the processors for task-graph scheduling in parallel systems using learning and cellular learning automata. Proc. 1st National Conf. on Computer Engineering and Information Technology, p.1-8 (in Farsi).

[7]Boveiri, H.R., 2015. Multiprocessor task graph scheduling using a novel graph-like learning automata. Int. J. Grid Distr. Comput., 8(1):41-54.

[8]Chrétienne, P., Coffman, E.G., Lenstra, J.K., et al., 1995. Scheduling Theory and Its Application. John Wiley & Sons, New York.

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

[10]Dorigo, M., di Caro, G., Gambardella, L., 1999. Ant algorithm for discrete optimization. Artif. Life, 5(2):137-172.

[11]Hwang, J.J., Chow, Y.C., Anger, F.D., et al., 1989. Scheduling precedence graphs in systems with interprocessor communication times. SIAM J. Comput., 18(2):244-257.

[12]Hwang, R., Gen, M., Katayama, H., 2008. A comparison of multiprocessor task scheduling algorithms with communication costs. Comput. Oper. Res., 35(3):976-993.

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

[14]Kwok, Y., Ahmad, I., 1998. Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Comput. Surv., 31(4):406-471.

[15]McCreary, C., Gill, H., 1989. Automatic determination of grain size for efficient parallel processing. Commun. ACM, 32(9):1073-1078.

[16]Meybodi, M.R., Beigy, H., Taherkhani, M., 2004. Cellular learning automata and its applications. J. Sci. Technol. Sharif Univ., 25:54-77 (in Farsi).

[17]Narendra, K.S., Thathachar, M.A.L., 1974. Learning automata: a survey. IEEE Trans. Syst. Man Cybern., SMC-4(4): 323-334.

[18]Sih, G.C., Lee, E.A., 1993. A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures. IEEE Trans. Parall. Distr. Syst., 4(2):175-187.

[19]Wolfram, S., 1983. Cellular automata. Los Alamos Sci., 9:2-27.

[20]Wu, M.Y., Gajski, D.D., 1990. Hypertool: a programming aid for message-passing systems. IEEE Trans. Parall. Distr. Syst., 1(3):330-343.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - 2022 Journal of Zhejiang University-SCIENCE