Performance evaluation of a parallel tabu search task scheduling algorithm

作     者：Porto, SCS Kitajima, JPFW Ribeiro, CC 

作者机构：Pontificia Univ Catolica Rio de Janeiro Dept Comp Sci Rio De Janeiro Brazil Univ Fed Fluminense Inst Computacao Niteroi RJ Brazil Univ Fed Minas Gerais Dept Comp Sci Belo Horizonte MG Brazil 

出 版 物：《PARALLEL COMPUTING》 (并行计算)

年 卷 期：2000年第26卷第1期

页      面：73-90页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：parallel algorithms task scheduling greedy algorithm tabu search solution quality 

摘      要：This paper presents the solution quality analysis of a parallel tabu search algorithm for the task scheduling problem on heterogeneous processors under precedence constraints. We evaluate the achieved makespan reduction of different parallel applications, relatively to the results obtained by the best greedy algorithm in the literature, as a function of parameters such as problem size, system heterogeneity, and number of processors. Our results show that the parallel tabu search algorithm leads to much better solutions than the greedy algorithm in many cases where the latter is not capable of profiting from the inherent application parallelism and system heterogeneity, (C) 2000 Elsevier Science B.V. All rights reserved.