Ant colony optimization for precedence-constrained heterogeneous multiprocessor assignment problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Ant colony optimization for precedence-constrained heterogeneous multiprocessor assignment problem

Full text

Pdf (561 KB)

Source

ACM/SIGEVO Summit on Genetic and Evolutionary Computation archive
Proceedings of the first ACM/SIGEVO Summit on Genetic and Evolutionary Computation table of contents

Shanghai, China

SESSION: Full papers table of contents

Pages: 89-96

Year of Publication: 2009

ISBN:978-1-60558-326-6

Authors

Rong Deng	Tongji University, ShangHai, China
Changjun Jiang	Tongji University, ShangHai, China
Fei Yin	Tongji University, ShangHai, China

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 83, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1543834.1543848 What is a DOI?

ABSTRACT

An ant colony optimization approach, named MPAACO, for the Precedence-Constrained Heterogeneous Multiprocessor Assignment Problem (PCHMAP) is presented. The main characteristics of MPAACO are novel pheromone matrix and solution construction scheme. Separating processor selection steps from task selection steps, ant colony has full flexibility to construct new solution. Three-dimensional pheromone matrix can record each solution construction step precisely. When combined with heuristic information, they endow MPAACO the ability to find high quality schedules of PCHMAP quickly. We tested the algorithm on a set of benchmark problems from the [18]. The result shows that for 77% of all benchmark for Precedence-Constrained Homogeneous Multiprocessor Assignment Problem, a special case of PCHMAP, the algorithm can get the optimal in just one try. For PCHMAP problems, MPAACO outperforms other algorithms significantly.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Rashmi Bajaj , Dharma P. Agrawal, Improving Scheduling of Tasks in a Heterogeneous Environment, IEEE Transactions on Parallel and Distributed Systems, v.15 n.2, p.107-118, February 2004 [doi>10.1109/TPDS.2004.1264795]
	2	Tracy D. Braun , Howard Jay Siegel , Noah Beck , Lasislau L. Bölöni , Muthucumara Maheswaran , Albert I. Reuther , James P. Robertson , Mitchell D. Theys , Bin Yao , Debra Hensgen , Richard F. Freund, A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems, Journal of Parallel and Distributed Computing, v.61 n.6, p.810-837, June 2001 [doi>10.1006/jpdc.2000.1714]
	3	Bertrand Cirou, Triplet: A Clustering Scheduling Algorithm for Heterogeneous Systems, Proceedings of the 2001 International Conference on Parallel Processing Workshops, p.231, September 03-07, 2001
	4	Ricardo C. Corrêa , Afonso Ferreira , Pascal Rebreyend, Scheduling Multiprocessor Tasks with Genetic Algorithms, IEEE Transactions on Parallel and Distributed Systems, v.10 n.8, p.825-837, August 1999 [doi>10.1109/71.790600]
	5	Daniel, M., Martin, M., and Hartmut, S. 2002.Ant Colony Optimization for Resource-Constrained Project Scheduling. IEEE Transactions on Evolutionary Computation, Vol. 6, No. 4, August, 2002.
	6	Muhammad K. Dhodhi , Imtiaz Ahmad , Anwar Yatama , Ishfaq Ahmad, An integrated technique for task matching and scheduling onto distributed heterogeneous computing systems, Journal of Parallel and Distributed Computing, v.62 n.9, p.1338-1361, September 2002 [doi>10.1006/jpdc.2002.1850]
	7	Fang, P. D. and Selim, G. A. 2006. Scheduling Algorithms for Grid Computing: State of the Art and Open Problems. Technical Report No.2006--504.
	8	E. S. H. Hou , N. Ansari , H. Ren, A Genetic Algorithm for Multiprocessor Scheduling, IEEE Transactions on Parallel and Distributed Systems, v.5 n.2, p.113-120, February 1994 [doi>10.1109/71.265940]
	9	Iverson, M., Ozguner, F. and Follen, G. 1995. Parallelizing existing applications in a distributed heterogeneous environment. Heterogeneous Computing Workshop 1995.
	10	Yu-Kwong Kwok , Ishfaq Ahmad, Static scheduling algorithms for allocating directed task graphs to multiprocessors, ACM Computing Surveys (CSUR), v.31 n.4, p.406-471, Dec. 1999 [doi>10.1145/344588.344618]
	11	Marco, D., Mauro, B. and Thomas, S. 2006. Ant Colony Optimization: Artificial Ants as a Computational Intelligence Technique. IEEE Computational intelligence magazine, 2006(11):28--39
	12	Andrei Rădulescu , Arjan J. C. van Gemund, On the complexity of list scheduling algorithms for distributed-memory systems, Proceedings of the 13th international conference on Supercomputing, p.68-75, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305162]
	13	Sakellariou, R., Zhao, H. 2004. A Hybrid Heuristic for DAG Scheduling on Heterogeneous Systems. 18th International Parallel and Distributed Processing Symposium (April 26--30, 2004), 111--123.
	14	Shih-Tang Lo , Ruey-Maw Chen , Yueh-Min Huang , Chung-Lun Wu, Multiprocessor system scheduling with precedence and resource constraints using an enhanced ant colony system, Expert Systems with Applications: An International Journal, v.34 n.3, p.2071-2081, April, 2008 [doi>10.1016/j.eswa.2007.02.022]
	15	Shroff, P., Watson, D.W., Flann, N. S., Freund, R. F. 1996.Genetic simulated annealing for scheduling data dependent tasks in heterogeneous environments. Proceedings of the Heterogeneous Computing Workshop, 1996, 98--104.
	16	G. C. Sih , E. A. Lee, A Compile-Time Scheduling Heuristic for Interconnection-Constrained Heterogeneous Processor Architectures, IEEE Transactions on Parallel and Distributed Systems, v.4 n.2, p.175-187, February 1993 [doi>10.1109/71.207593]
	17	Haluk Topcuouglu , Salim Hariri , Min-you Wu, Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing, IEEE Transactions on Parallel and Distributed Systems, v.13 n.3, p.260-274, March 2002 [doi>10.1109/71.993206]
	18	Udo, H. and Wolfram, S. 2004. A Comprehensive Test Bench For the Evaluation of Scheduling Heuristics. Proc. of the 16th International Conference on Parallel and Distributed Computing and Systems (PDCS'04), ACTA Press, Cambridge, USA , 2004
	19	Annie S. Wu , Han Yu , Shiyuan Jin , Kuo-Chi Lin , Guy Schiavone, An Incremental Genetic Algorithm Approach to Multiprocessor Scheduling, IEEE Transactions on Parallel and Distributed Systems, v.15 n.9, p.824-834, September 2004 [doi>10.1109/TPDS.2004.38]
	20	Xiao, H. K., Jun, S. and Wen, B. X . 2008. Permutation--based particle swarm algorithm for tasks scheduling in heterogeneous systems with communication delays. International Journal of Computational Intelligence Research, Vol 4, Issue 1.
	21	Xiao, H. K. and Wen, B. X. 2006. Ant Colony Algorithm for Scheduling Parallel Program Based on DAG Graph Heuristics. Proceedings of the 6th World Congress on Intelligent Control and Automation, June 21 -- 23, 2006.
	22	Zhao, H., Sakellariou, R. 2003. Experimental investigations into the rank function of the heterogeneous earliest finish time scheduling algorithm. (Euro-Par2003). Springer-Verlag, LNCS 2790.