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

详细信息    查看全文

• 作者：Guoquan Liu ; Yifeng Zeng ; Dong Li ; Yingke Chen
• 关键词：Multi ; objective optimization ; Tabu search ; Distributed computing systems
• 刊名：Soft Computing - A Fusion of Foundations, Methodologies and Applications
• 出版年：2015
• 出版时间：June 2015
• 年：2015
• 卷：19
• 期：6
• 页码：1727-1737
• 全文大小：540 KB
• 参考文献：Ahmad I (1995) Task assignment using a problem-space genetic algorithm. Concurr Pract Exp 7:411鈥?28View Article
  Ben-Tal A (1980) Characterization of pareto and lexicographic optimal solutions. Multiple Criteria Dec Mak Theory Appl 177:1鈥?1View Article MathSciNet
  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鈥?71View Article
  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鈥?0
  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鈥?734View Article
  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鈥?09View Article MATH
  Darbha S, Agrawal DP (1998) Optimal scheduling algorithm for distributed-memory machines. IEEE Trans Parallel Distrib Syst 9(1):87鈥?5View Article
  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鈥?23View Article
  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鈥?6View Article
  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鈥?83View Article MATH MathSciNet
  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, BostonView Article MATH
  Hou ES, Ansari N, Ren H (1994) A genetic algorithm for multiprocessor scheduling. IEEE Trans Parallel Distrib Syst 5(2):113鈥?20View Article
  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鈥?24View Article
  KulturelKonak S, Smith AE, Norman BA (2006) Multi-objective tabu search using a multinomial probability mass function. Eur J Operat Res 169:918鈥?31View Article MathSciNet
  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鈥?7
  Kwok YK, Ahmad I (1999) Benchmarking and comparison of the task graph scheduling algorithms. J Parallel Distrib Comput 59(3):381鈥?22View Article MATH
  Oh J, Wu C (2004) Genetic-algorithm-based real-time task scheduling with multiple goals. J Syst and Softw 71(3):245鈥?58View Article
  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鈥?66
  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鈥?
  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鈥?11
  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鈥?79
  Shatz SM, Wang JP (1989) Models and algorithms for reliability-oriented task-allocation in redundant distributed-computer systems. IEEE Trans Reliab 38(1):16鈥?7View Article
  Shatz SM, Wang JP, Goto M (1992) Task allocation for maximizing reliability of distributed computer systems. IEEE Trans Comput 41(9):1156鈥?168View Article
  Srinivas N, Deb K (1994) Muiltiobjective optimization using nondominated sorting in genetic algorithms. Evol Comput 2(3):221鈥?48View Article
  Srinivasan S, Jha NK (1999) Safety and reliability driven task allocation in distributed systems. IEEE Trans Parallel Distrib Syst 10(3):238鈥?51View Article
  Tan KC, Lee TH, Khor EF (2002) Evolutionary algorithms for multi-objective optimization: performance assessments and comparisons. Artif Intell Rev 17(4):251鈥?90View Article MATH
  Tan KC, Khor EF, Lee TH, Yang Y (2003) A tabu-based exploratory evolutionary algorithm for multiobjective optimization. Artif Intell Rev 19(3):231鈥?60View Article
  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鈥?52View Article MATH
  Tang X, Li K, Liao G, Li R (2010b) List scheduling with duplication for heterogeneous computing systems. J Parallel Distrib Comput 70(4):323鈥?29View Article MATH
  Topcuoglu H, Hariri S (2002) Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans Parallel Distrib Syst 13(3):260鈥?74View Article
  Woodside CM, Monforton GG (1993) Fast allocation of processes in distributed and parallel systems. IEEE Trans Parallel Distrib Syst 4(2):164鈥?74View Article
  Wu M, Gajski DD (1990) Hypertool: a programming aid for message-passing systems. IEEE Trans Parallel Distrib Syst 1(3):330鈥?43View Article
  Zhao H, Sakellariou R (2006) Scheduling multiple DAGs onto heterogeneous systems. In: International symposium on parallel and distributed processing (IPDPS), pp 14鈥?7
  
• 作者单位：Guoquan Liu (1)
  Yifeng Zeng (2) (3)
  Dong Li (4)
  Yingke Chen (5)
  
  1. International Business School Suzhou, Xi鈥檃n Jiaotong-Liverpool University, Suzhou, China
  2. Department of Automation, Xiamen University, Xiamen, China
  3. School of Computing, Teesside University, Middlesbrough, UK
  4. The York Management School, University of York, York, United Kingdom
  5. College of Computer Science, Sichuan University, Chengdu, China
  
• 刊物类别：Engineering
• 刊物主题：Numerical and Computational Methods in Engineering
  Theory of Computation
  Computing Methodologies
  Mathematical Logic and Foundations
  Control Engineering
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1433-7479

文摘

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.