期刊
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
卷 142, 期 2, 页码 242-249出版社
ELSEVIER
DOI: 10.1016/S0377-2217(02)00264-3
关键词
parallel computing; scheduling; malleable tasks; precedence constraints; trees
This work presents an approximation algorithm for scheduling the tasks of a parallel application. These tasks are considered as malleable tasks (MT in short), which means that they can be executed on several processors. This model receives recently a lot of attention, mainly due to their practical use for implementing actual parallel applications. Most of the works developed within this model deal with independent MT for which good approximation algorithms have been designed. This work is devoted to the case where MT are linked by precedence relations. We present a 4(1 + epsilon) approximation algorithm (for any fixed 6) for the specific structure of a tree. This preliminary result should open the way for further investigations concerning arbitrary precedence graphs of MT. (C) 2002 Published by Elsevier Science B.V.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据