Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Xu, Yuming; Li, Kenli; He, Ligang; Zhang, Longxin; Li, Keqin
Publisher: IEEE
Languages: English
Types: Article
Subjects: QA
An application consisting of a group of tasks can be represented by a node- and edge-weighted directed acyclic graph (DAG), in which the vertices represent the computations and the directed edges represent the data dependencies as well as the communication times between the vertices. DAGs have been shown to be expressive for a large number of and a variety of applications. Task scheduling is one of the most thought-provoking NP-hard problems in general cases, and polynomial time algorithms are known only for a few restricted cases [1]. Hence, it is a challenge on heterogeneous computing systems to develop task scheduling algorithms that assign the tasks of an application to processors in order to minimize makespan without violating precedence constraints. Therefore, many researchers have proposed a variety of approaches to solving the DAG task scheduling problem. These methods are basically classified into two major categories: dynamic scheduling and static scheduling. In dynamic scheduling, the information, such as a task’s relation, execution time, and communication time, are all not previously known. The scheduler has to make decisions in real time. In static scheduling, all information about tasks are known before hand. Static scheduling algorithms by using different techniques to find a near optimal solution are universally classified into two major groups: heuristic scheduling and meta-heuristic scheduling.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [1] M. R. Garey and D. S. Johnson, Computers and intractability: a guide to the theory of NPCompleteness. New York: W. H. Freeman, 1979.
    • [2] F. Ferrandi, P. Lanzi, C. Pilato, D. Sciuto, and A. Tumeo, “Ant colony heuristic for mapping and scheduling tasks and communications on heterogeneous embedded systems,” Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, vol. 29, no. 6, pp. 911-924, june 2010.
    • [3] R. Correa, A. Ferreira, and P. Rebreyend, “Scheduling multiprocessor tasks with genetic algorithms,” Parallel and Distributed Systems, IEEE Transactions on, vol. 10, no. 8, pp. 825-837, Aug 1999.
    • [4] A. Zomaya, C. Ward, and B. Macey, “Genetic scheduling for parallel processor systems: comparative studies and performance issues,” Parallel and Distributed Systems, IEEE Transactions on, vol. 10, no. 8, pp. 795-812, Aug 1999.
    • [5] M. Kashani and M. Jahanshahi, “Using simulated annealing for task scheduling in distributed systems,” in Computational Intelligence, Modelling and Simulation, 2009. CSSim '09. International Conference on, sept. 2009, pp. 265-269.
    • [6] A. Lam and V. Li, “Chemical-reaction-inspired metaheuristic for optimization,” Evolutionary Computation, IEEE Transactions on, vol. 14, no. 3, pp. 381-399, june 2010.
    • [7] J. Xu, A. Lam, and V. Li, “Chemical reaction optimization for task scheduling in grid computing,” Parallel and Distributed Systems, IEEE Transactions on, vol. 22, no. 10, pp. 1624-1631, Oct 2011.
    • [8] Y. Xu, K. Li, L. He, and T. K. Truong, “A DAG scheduling scheme on heterogeneous computing systems using double molecular structurebased chemical reaction optimization,” Journal of Parallel and Distributed Computing, vol. 73, no. 9, pp. 1306-1322, 2013.
    • [9] S. Santander-Jimenez and M. Vega-Rodriguez, “Parallel multiobjective metaheuristics for inferring phylogenies on multicore clusters,” Parallel and Distributed Systems, IEEE Transactions on, vol. PP, no. 99, pp. 1-1, 2014.
    • [10] Y. Bai, S. Xiao, C. Liu, and B. Wang, “A hybrid iwo/pso algorithm for pattern synthesis of conformal phased arrays,” Antennas and Propagation, IEEE Transactions on, vol. 61, no. 4, pp. 2328-2332, April 2013.
    • [11] Y. Tominaga, Y. Okamoto, S. Wakao, and S. Sato, “Binarybased topology optimization of magnetostatic shielding by a hybrid evolutionary algorithm combining genetic algorithm and extended compact genetic algorithm,” Magnetics, IEEE Transactions on, vol. 49, no. 5, pp. 2093- 2096, May 2013.
    • [12] J. Yang, W. Li, X. Shi, L. Xin, and J. Yu, “A hybrid abcde algorithm and its application for timemodulated arrays pattern synthesis,” Antennas and Propagation, IEEE Transactions on, vol. 61, no. 11, pp. 5485-5495, Nov 2013.
    • [13] D. Fodorean, L. Idoumghar, and L. Szabo, “Motorization for an electric scooter by using permanentmagnet machines optimized based on a hybrid metaheuristic algorithm,” Vehicular Technology, IEEE Transactions on, vol. 62, no. 1, pp. 39-49, Jan 2013.
    • [14] M. Li, H. Kang, and P. Zhou, “Hybrid optimization algorithm based on chaos, cloud and particle swarm optimization algorithm,” Systems Engineering and Electronics, Journal of, vol. 24, no. 2, pp. 324-334, April 2013.
    • [15] X. Li and Y. Zhang, “Adaptive hybrid algorithms for the sequencedependent setup time permutation flow shop scheduling problem,” Automation Science and Engineering, IEEE Transactions on, vol. 9, no. 3, pp. 578-595, July 2012.
    • [16] H. Cheng, I. Chung, and W. Chen, “Thermal chip placement in mcms using a novel hybrid optimization algorithm,” Components, Packaging and Manufacturing Technology, IEEE Transactions on, vol. 2, no. 5, pp. 764-774, May 2012.
    • [17] “Hybrid algorithm,” http://en.wikipedia.org/wiki/Hybrid algorithm.htm, accessed: 2014-06-06.
    • [18] H. Topcuoglu, S. Hariri, and M.-Y. Wu, “Performanceeffective and lowcomplexity task scheduling for heterogeneous computing,” Parallel and Distributed Systems, IEEE Transactions on, vol. 13, no. 3, pp. 260-274, mar 2002.
    • [19] A. Kapsalis, V. J. Rayward-Smith, and G. D. Smith, “Solving the graphical steiner tree problem using genetic algorithms,” The Journal of the Operational Research Society, vol. 44, no. 4, pp. 397-406, 1993.
    • [20] D. Levine, “Commentaryłgenetic algorithms: A practitioner's view,” INFORMS Journal on Computing, vol. 9, no. 3, pp. 256-259, 1997.
    • [21] G. E. P. Box and M. E. Muller, “A note on the generation of random normal deviates,” The Annals of Mathematical Statistics, vol. 29, no. 2, pp. 610-611, 06 1958.
    • [22] Wikipedia, “68-95-99.7 rule,” June 2014. [Online]. Available: http://en.wikipedia.org/wiki/68-80-95.7 rule
    • [23] --, “Hamming distance,” March 2014. [Online]. Available: http://en.wikipedia.org/wiki/Hamming distance
    • [24] L. Davis, Genetic Algorithms and Simulated Annealing. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1987.
    • [25] Y. Xu, K. Li, J. Hu, and K. Li, “A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues,” Information Sciences, vol. 270, no. 0, pp. 255-287, 2014.
    • [26] M.-Y. Wu and D. Gajski, “Hypertool: a programming aid for messagepassing systems,” Parallel and Distributed Systems, IEEE Transactions on, vol. 1, no. 3, pp. 330-343, jul 1990.
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article