A hybrid evolutionary approach for heterogeneous multiprocessor scheduling | Soft Computing Skip to main content

Advertisement

Springer Nature Link
Log in

A hybrid evolutionary approach for heterogeneous multiprocessor scheduling

  • Focus
  • Published:
Soft Computing Aims and scope Submit manuscript

Abstract

This article investigates the assignment of tasks with interdependencies in a heterogeneous multiprocessor environment; specific to this problem, task execution time varies depending on the nature of the tasks as well as with the processing element assigned. The solution to this heterogeneous multiprocessor scheduling problem involves the optimization of complete task assignments and processing order between the assigned processors to arrive at a minimum makespan, subject to a precedence constraint. To solve an NP-hard combinatorial optimization problem, as is typified by this problem, this paper presents a hybrid evolutionary algorithm that incorporates two local search heuristics, which exploit the intrinsic structure of the solution, as well as through the use of specialized genetic operators to promote exploration of the search space. The effectiveness and contribution of the proposed features are subsequently validated on a set of benchmark problems characterized by different degrees of communication times, task, and processor heterogeneities. Preliminary results from simulations demonstrate the effectiveness of the proposed algorithm in finding useful schedule sets based on the set of new benchmark problems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Ahmad I, Kwok YK (1998) Optimal and near-optimal allocation of precedence-constrained tasks to parallel processors: defying the high complexity using effective search techniques. In: Proceedings of 1998 international conference on parallel processing, pp 423–431

  • Ahmad I, Kwok YK (1998) On exploiting task duplication in parallel program scheduling. IEEE Trans Parallel Distrib Syst 9(9): 872–892

    Article  Google Scholar 

  • Baskiyar S, Dickinson C (2005) Scheduling directed a-cyclic task graphs on a bounded set of heterogeneous processors using task duplication. J Parallel Distrib Comput 65(8): 911–921

    Article  MATH  Google Scholar 

  • Blickle T, Teich J, Thiele L (1996) System level synthesis using evolutionary algorithms, TIK-Report, Nr. 16

  • Braun TD, Siegel HJ, Beck N, Boloni LL, Maheswaran M, Reuther AI, Robertson JP, Theys MD, Yao B, Hensgen D, Freund RF (2001) A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. J Parallel Distrib Comput 61(6): 810–837

    Article  Google Scholar 

  • Burke EK, Cowling P, De Causmaecker P (2001) A memetic approach to the nurse rostering problem. Appl Intell 15(3): 199–214

    Article  MATH  Google Scholar 

  • Coll PE, Ribeiro CC, de Sousa CC (2002) Test instances for scheduling unrelated processors under precedence constraints. http://www-di.inf.pucrio.br/celso/grupo/readme.ps

  • Correa RC, Ferreira A, Rebreyend P (1999) Scheduling multiprocessor tasks with genetic algorithms. IEEE Trans Parallel Distrib Syst 10(8): 825–837

    Article  Google Scholar 

  • Davidovic T, Crainic TG (2003) New benchmarks for static task scheduling on homogenous multiprocessor systems with communication delays, Publication CRT, 2003-04, Centre de Recherche sur les Transports, Universite de Montreal, pp 123–136

  • Davis L (1991) Handbook of genetic algorithms. Van Nostrand Reinhold, London

    Google Scholar 

  • Dhodi MK, Hielscher EH, Storer RH, Bhasker J (1995) Datapath synthesis using a problem space genetic algorithm. IEEE Trans CAD 14(8): 934–944

    Google Scholar 

  • Eiben AE, Smith JE (2003) Introduction to evolutionary computing. Springer, New York

    MATH  Google Scholar 

  • El-Rewini H, Lewis TG, Ali HH (1994) Task scheduling in parallel and distributed systems. Prentice Hall, Englewood Cliffs

    Google Scholar 

  • Franca PM, Mendes A, Moscato P (2001) A memetic algorithm for the total tardiness single machine scheduling problem. Eur J Oper Res 132(1): 224–242

    Article  MATH  MathSciNet  Google Scholar 

  • Garey MR, Johnson DS (1979) Computers and intractability, a guide to the theory of NP-completeness. W.H. Freeman and Co., San Francisco

    MATH  Google Scholar 

  • Hall NG, Posner ME (2001) Generating experimental data for computational testing with machine scheduling applications. Oper Res 49: 854–865

    Article  MathSciNet  Google Scholar 

  • Hou ES, Ansari N, Ren H (1994) A genetic algorithm for multiprocessor scheduling. IEEE Trans Parallel Distrib Syst 5(2): 113–120

    Article  Google Scholar 

  • Ishibuchi H, Yoshida T, Murata T (2003) Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Trans Evol Comput 7(2): 204–223

    Article  Google Scholar 

  • Kasahara H, Narita S (1984) Practical multiprocessor scheduling algorithms for efficient parallel processing. IEEE Trans Comput 33(11): 1023–1029

    Article  Google Scholar 

  • Kruatrachue B, Lewis TG (1987) Duplication scheduling heuristic, a new precedence task scheduler for parallel systems, Technical Report 87-60-3, Oregon State University

  • Kwok Y, Ahmad I (1997) Efficient scheduling of arbitrary task graphs to multiprocessors using a parallel genetic algorithm. J Parallel Distrib Comput 47(1): 58–77

    Article  Google Scholar 

  • Kwok Y, Ahmad I (1999) Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Comput Surv 31(4): 406–471

    Article  Google Scholar 

  • Lewis TG, El-Rewini H (1992) Introduction to parallel computing. Prentice Hall, New York

    MATH  Google Scholar 

  • Lim D, Ong YS, Jin Y, Sendhoff B, Lee BS (2007) Efficient hierarchical parallel genetic algorithm using grid computing. In: Future generation computer systems: the international journal of grid computing: theory, methods and applications, pp 658–670

  • Macey BS, Zomaya AY (1998) A performance evaluation of CP list scheduling heuristics for communication intensive task graphs. In: Proceedings of the joint 12th international parallel processing symposium and ninth symposium on parallel and distributed programming, pp 538–541

  • Merz P, Freisleben B (2000) Fitness landscape analysis and memetic algorithms for the quadratic assignment problem. IEEE Trans Evol Comput 4(4): 337–352

    Article  Google Scholar 

  • Ong YS, Keane AJ (2004) Meta-Lamarckian learning in memetic algorithms. IEEE Trans Evol Comput 8(2): 99–110

    Article  Google Scholar 

  • Ong YS, Lim MH, Zhu N, Wong KW (2006) Classification of adaptive memetic algorithms: a comparative study. IEEE Trans Syst Man Cybern B 36(1): 141–152

    Article  Google Scholar 

  • Papadimitriou C, Yannakakis M (1990) Toward an architecture independent analysis of parallel algorithms. SIAM J Comput 19: 322–328

    Article  MATH  MathSciNet  Google Scholar 

  • Ritchie G, Levine J (2004) A hybrid ant algorithm for scheduling independent jobs in heterogeneous computing environments. In: Proceedings of the 23rd workshop of the UK planning and scheduling special interest group

  • Tang J, Lim MH, Ong YS (2007) Diversity-adaptive parallel memetic algorithm for solving large scale combinatorial optimization problems. Soft Comput 7(9): 873–888

    Article  Google Scholar 

  • Tsuchiya T, Osada T, Kikuno T (1998) Genetic-based multiprocessor scheduling using task duplication. Microprocessors Microsyst 22: 197–207

    Article  Google Scholar 

  • Wu AS, Yu H, Jin S, Lin KC, Schiavone G (2004) An incremental genetic algorithm approach to multiprocessor scheduling. IEEE Trans Parallel Distrib Syst 15(9): 824–834

    Article  Google Scholar 

  • Zhou Z, Ong YS, Lim MH, Lee BS (2007) Memetic algorithm using multi-surrogates for computationally expensive optimization problems. Soft Comput 11(10): 957–972

    Article  Google Scholar 

  • Zhong YW, Yang JG, Qi HN (2004) A hybrid genetic algorithm for task scheduling in heterogeneous computing systems. In: Proceedings of the third international conference on machine learning and cybernetics, pp 2463–2468

  • Zomaya AY, Ward C, Macey B (1999) Genetic scheduling for parallel processor systems: comparative studies and performance issues. IEEE Trans Parallel Distrib Syst 10(8): 795–812

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Spintronics, Media and Interface Division, Data Storage Institute, DSI Building, 5 Engineering Drive 1, Singapore, 117608, Singapore

    C. K. Goh

  2. Department of Electrical and Computer Engineering, National University of Singapore, 4 Engineering Drive 3, Singapore, 117576, Singapore

    E. J. Teoh & K. C. Tan

Authors
  1. C. K. Goh
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. E. J. Teoh
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. K. C. Tan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to C. K. Goh.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Goh, C.K., Teoh, E.J. & Tan, K.C. A hybrid evolutionary approach for heterogeneous multiprocessor scheduling. Soft Comput 13, 833–846 (2009). https://doi.org/10.1007/s00500-008-0356-2

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00500-008-0356-2

Keywords

Search

Navigation