×
Chen, Hua; Cheng, Albert Mo Kim; Kuo, Ying-Wei

Assigning real-time tasks to heterogeneous processors by applying ant colony optimization. (English) Zbl 1219.68068

J. Parallel Distrib. Comput. 71, No. 1, 132-142 (2011).
Summary: The problem of determining whether a set of periodic tasks can be assigned to a set of heterogeneous processors without deadline violations has been shown, in general, to be NP-hard. This paper presents a new algorithm based on ant colony optimization (ACO) metaheuristic for solving this problem. A local search heuristic that can be used by various metaheuristics to improve the assignment solution is proposed and its time and space complexity is analyzed. In addition to being able to search for a feasible assignment solution, our extended ACO algorithm can optimize the solution by lowering its energy consumption. Experimental results show that both the prototype and the extended version of our ACO algorithm outperform major existing methods; furthermore, the extended version achieves an average of 15.8% energy saving over its prototype.

Cited in 2 Documents

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Keywords:

scheduling; real-time systems; multiprocessors; heterogeneous processors; ant colony optimization; power-aware computing; periodic tasks

Software:

LPbook; GLPK
PDF BibTeX XML Cite
\textit{H. Chen} et al., J. Parallel Distrib. Comput. 71, No. 1, 132--142 (2011; Zbl 1219.68068)
Full Text: DOI

References:

[1] H. Aydin, Q. Yang, Energy-aware partitioning for multiprocessor real-time systems, in: Proc. Intl. Parallel and Distributed Processing Symposium, 2003.
[2] Baruah, S.: Task partitioning upon heterogeneous multiprocessor platforms, , 1-8 (2004)
[3] S. Baruah, Partitioning real-time tasks among heterogeneous multiprocessors, in: ICPP, 2004, pp. 1–8.
[4] Bentley, J. L.: Fast algorithms for geometric traveling salesman problems, ORSA journal on computing 4, 387-411 (1992) · Zbl 0758.90071
[5] Braun, T.: A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems, Journal of parallel and distributed computing 61, 810-837 (2001) · Zbl 0990.68013
[6] Bunde, D. P.: Power-aware scheduling for makespan and flow, Journal of scheduling 12, No. 5 (2009) · Zbl 1176.90196
[7] T.D. Burd, R.W. Brodersen, Energy efficient CMOS microprocessor design, in: Proc. Hawaii Int’l Conf. System Science, January 1995, pp. 288–297.
[8] Carpenter, J.; Funk, S.; Holman, P.; Srinivansan, A.; Anderson, J.; Baruah, S.: A categorization of real-time multiprocessor scheduling problems and algorithms, (2003)
[9] H. Chen, Assigning real-time tasks to heterogeneous processors by applying ant colony optimization, Master Thesis, Dept. of Computer Science, University of Houston, TX, 2005.
[10] H. Chen, A.M.K. Cheng, Applying ant colony optimization to the partitioned scheduling problem for heterogeneous multiprocessors, WIP session, in: IEEE RTAS, 2005.
[11] Cheng, Albert M. K.: Real-time systems: scheduling, analysis, and verification, (2002)
[12] Dantzig, G. B.; Thapa, M. N.: Linear programming, 1: introduction, (1997) · Zbl 0883.90090
[13] Dorigo, M.; Stützle, T.: Ant colony optimization, (2004) · Zbl 1092.90066
[14] Garey, M. R.; Johnson, D. S.: Computers and intractability: A guide to the theory of NP-completeness, (1979) · Zbl 0411.68039
[15] GNU Linear Programming Kit Reference Manual, vol. 4.6, August, 2004.
[17] Jin, H.; Wang, H.; Wang, H.; Dai, G.: An ACO-based approach for task assignment and scheduling of multiprocessor control, Lecture notes in computer science 3959 (2006) · Zbl 1178.68103
[18] D.S. Johnson, L.A. McGeoch, The traveling salesman problem: a case study in local optimization, 1995.
[19] Levine, J.; Ducatelle, F.: Ant colony optimisation and local search for bin packing and cutting stock problems, Journal of the operational research society 55, No. 7, 705-716 (2004) · Zbl 1095.90122
[20] G. Ritchie, Static multi-processor scheduling with ant colony optimization & local search, Master Thesis, School of Informatics, University of Edinburgh, UK, 2003.
[21] Shmoys, D. B.; Tardos, E.: An approximation algorithm for the generalized assignment problem, Mathematical programming 62, 461-474 (1993) · Zbl 0804.90077
[22] Stützle, T.; Hoos, H.: MAX–MIN ant system, Future generation computer systems 16, No. 8, 889-914 (1999) · Zbl 0970.90083
[23] T. Stutzle, H. Hoos, Improvements on the ant-system: introducing the max–min ant system.
[24] Vanderbei, R. J.: Linear programming: foundations and extensions, (2001) · Zbl 1043.90002
[25] M. Yagiura, T. Ibaraki, Recent metaheuristic algorithms for the generalized assignment problem, in: ICKS, 2004, pp. 1–9. · Zbl 1239.90091
[26] D. Zhu, N. AbouGhazaleh, D. Mosse, R. Melhem, Power aware scheduling for and/or graphs in multi-processor real-time systems, in: Proc. International Conference on Parallel Processing, 2002.
[27] Zhu, D.; Melhem, R.; Childers, B. R.: Scheduling with dynamic voltage/speed adjustment using slack reclamation in multiprocessor real-time systems, IEEE transactions on parallel and distributed systems 14, No. 7 (2003)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.