nach oben

Soft Computing

Erschienen in:

01.06.2015 | Methodologies and Application

Schedule length and reliability-oriented multi-objective scheduling for distributed computing

verfasst von: Guoquan Liu, Yifeng Zeng, Dong Li, Yingke Chen

Erschienen in: Soft Computing | Ausgabe 6/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Maximizing system reliability and minimizing schedule length are the two major objectives in scheduling a distributed computing system. These two objectives have been considered separately by most researchers, although more realistically they should be considered simultaneously. This paper addresses the problem by taking a multi-objective approach in scheduling. A Tabu search algorithm is proposed and two lateral interference schemes are used to distribute the Pareto optimal solutions along the Pareto front uniformly. Randomly generated directed acyclic graphs and a real application task graph are used to study the performance of the proposed algorithms. Experimental results show that for this problem lateral interference has no influence on the non-dominated solution number, but does benefit the uniform distribution of non-dominated solutions, irrespective of the computation method used to determine distances between the solutions.

Vorheriger Artikel Adaptive Web QoS controller based on online system identification using quantum-behaved particle swarm optimization

Nächster Artikel Uncertain random multilevel programming with application to production control problem

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

Ahmad I (1995) Task assignment using a problem-space genetic algorithm. Concurr Pract Exp 7:411–428CrossRef

Ben-Tal A (1980) Characterization of pareto and lexicographic optimal solutions. Multiple Criteria Dec Mak Theory Appl 177:1–11CrossRefMathSciNet

Bozdag D, Ozguner F, Catalyurek UV (2009) Compaction of schedules and a two-stage approach for duplication-based DAG scheduling. IEEE Trans Parallel Distrib Syst 20(6):857–871CrossRef

Buffet O, Cucu L, Idoumghar L, Schott R (2010) Tabu search type algorithms for the multiprocessor scheduling problem. In: 10th IASTED international conference on artificial intelligence and applications

Chitra P, Venkatesh P (2010) Multiobjective evolutionary computation algorithms for solving task scheduling problem on heterogeneous systems. Int J Knowl Based Intell Eng Syst 14(1):21–30

Chitra P, Rajaram R, Venkatesh P (2011) Application and comparison of hybrid evolutionary multiobjective optimization algorithms for solving task scheduling problem on heterogeneous systems. Appl Soft Comput 11(2):2725–2734CrossRef

Coello CAC, Lamont GB, Van Veldhuisen DA (2007) Evolutionary algorithms for solving multi-objective problems. Springer, BerlinMATH

Daoud MI, Kharma N (2008) A high performance algorithm for static task scheduling in heterogeneous distributed computing systems. J Parallel Distrib Comput 68(4):399–409CrossRefMATH

Darbha S, Agrawal DP (1998) Optimal scheduling algorithm for distributed-memory machines. IEEE Trans Parallel Distrib Syst 9(1):87–95CrossRef

Dogan A, Ozguner F (2002) Matching and scheduling algorithms for minimizing execution time and failure probability of applications in heterogeneous computing. IEEE Trans Parallel Distrib Syst 13(3):308–323CrossRef

da Fonseca CMM (1995) Multi-objective genetic algorithms with application to control engineering problems. PhD thesis, University of Sheffield

da Fonseca CMM, Fleming PJ (1995) An overview of evolutionary algorithms in multiobjective optimization. Evolu Comput 3(1):1–16CrossRef

Erschler J, Roubellat F, Vernhes J (1976) Technical notefinding some essential characteristics of the feasible solutions for a scheduling problem. Operat Res 24(4):774–783CrossRefMATHMathSciNet

Fox MS (1987) Constraint-directed search: a case study of job-shop scheduling. Pitman

Garey MR, Johnson DS (1979) Computers and tntractability: a guide to the theory of NP-completeness. W. H Freeman, New YorkMATH

Glover F (1997) Tabu search. Kluwer, BostonCrossRefMATH

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

Iverson M (1999) Dynamic mapping and scheduling algorithms for a multi-user heterogeneous computing environment. PhD thesis, The Ohio State University

Jaffrs-Runser K, Gorce J, Comaniciu C (2008) A multiobjective tabu framework for the optimization and evaluation of wireless systems. Chapter 2. In: Jaziri W (ed) Tabu search. I-Tech Education and Publishing, Austria

Kartik S, Siva Ram Murthy C (1997) Task allocation algorithms for maximizing reliability of distributed computing systems. IEEE Trans Comput 46(6):719–724CrossRef

KulturelKonak S, Smith AE, Norman BA (2006) Multi-objective tabu search using a multinomial probability mass function. Eur J Operat Res 169:918–931CrossRefMathSciNet

Kwok YK, Ahmad I (1997) Efficient scheduling of arbitrary task graphs to multiprocessors using a parallel genetic algorithm. IEEE Trans Parallel Distrib Syst 47(1):58–77

Kwok YK, Ahmad I (1999) Benchmarking and comparison of the task graph scheduling algorithms. J Parallel Distrib Comput 59(3):381–422CrossRefMATH

Oh J, Wu C (2004) Genetic-algorithm-based real-time task scheduling with multiple goals. J Syst and Softw 71(3):245–258CrossRef

Page AJ, Keane TM, Naughton TJ (2010) Multi-heuristic dynamic task allocation using genetic algorithms in a heterogeneous distributed system. J Parallel Distrib Comput 70(7):758–766

Qiu M, Deng J, Sha EM (2008) Failure rate minimization with multiple function unit scheduling for heterogeneous wsns. In: IEEE global telecommunications conference (GLOBECOM), pp 1–5

Sardiña IM, Boeres C, Drummond da L (2010) An efficient weighted bi-objective scheduling algorithm for heterogeneous systems. In: Euro-Par parallel processing workshops, pp 102–111

Sedaghat N, Tabatabaee-Yazdi H, Akbarzadeh T, Mohammad R (2010) Pareto front based realistic soft real-time task scheduling with multi-objective genetic algorithm in unstructured heterogeneous distributed system. In: Advances in grid and pervasive computing, pp 268–279

Shatz SM, Wang JP (1989) Models and algorithms for reliability-oriented task-allocation in redundant distributed-computer systems. IEEE Trans Reliab 38(1):16–27CrossRef

Shatz SM, Wang JP, Goto M (1992) Task allocation for maximizing reliability of distributed computer systems. IEEE Trans Comput 41(9):1156–1168CrossRef

Srinivas N, Deb K (1994) Muiltiobjective optimization using nondominated sorting in genetic algorithms. Evol Comput 2(3):221–248CrossRef

Srinivasan S, Jha NK (1999) Safety and reliability driven task allocation in distributed systems. IEEE Trans Parallel Distrib Syst 10(3):238–251CrossRef

Tan KC, Lee TH, Khor EF (2002) Evolutionary algorithms for multi-objective optimization: performance assessments and comparisons. Artif Intell Rev 17(4):251–290CrossRefMATH

Tan KC, Khor EF, Lee TH, Yang Y (2003) A tabu-based exploratory evolutionary algorithm for multiobjective optimization. Artif Intell Rev 19(3):231–260CrossRef

Tang X, Li K, Li R, Veeravalli B (2010a) Reliability-aware scheduling strategy for heterogeneous distributed computing systems. J Parallel Distrib Comput 70(9):941–952CrossRefMATH

Tang X, Li K, Liao G, Li R (2010b) List scheduling with duplication for heterogeneous computing systems. J Parallel Distrib Comput 70(4):323–329CrossRefMATH

Topcuoglu H, Hariri S (2002) Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans Parallel Distrib Syst 13(3):260–274CrossRef

Woodside CM, Monforton GG (1993) Fast allocation of processes in distributed and parallel systems. IEEE Trans Parallel Distrib Syst 4(2):164–174CrossRef

Wu M, Gajski DD (1990) Hypertool: a programming aid for message-passing systems. IEEE Trans Parallel Distrib Syst 1(3):330–343CrossRef

Zhao H, Sakellariou R (2006) Scheduling multiple DAGs onto heterogeneous systems. In: International symposium on parallel and distributed processing (IPDPS), pp 14–27

Titel: Schedule length and reliability-oriented multi-objective scheduling for distributed computing
verfasst von: Guoquan Liu
Yifeng Zeng
Dong Li
Yingke Chen
Publikationsdatum: 01.06.2015
Verlag: Springer Berlin Heidelberg
Erschienen in: Soft Computing / Ausgabe 6/2015
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-014-1360-3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 6/2015

Double-phase locality-sensitive hashing of neighborhood development for multi-relational data

Uncertain random multilevel programming with application to production control problem

Design and stability analysis of adaptive fuzzy feedback controller for nonlinear systems by Takagi–Sugeno model-based adaptation scheme

Adaptive Web QoS controller based on online system identification using quantum-behaved particle swarm optimization

The time complexity analysis of a class of gene expression programming

An integrative top-down and bottom-up qualitative model construction framework for exploration of biochemical systems