loading...
An Approximation Algorithm for Multiprocessor Scheduling of Trees with Communication Delays
Dallas/Richardson, Texas, USA December 07-December 07
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISPAN.2000.9002742000 International Symposium on Paral ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
S. Tayu, M. Katsura, M. Kaneko, "An Approximation Algorithm for Multiprocessor Scheduling of Trees with Communication Delays," Parallel Architectures, Algorithms, and Networks, International Symposium on, pp. 114, 2000 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '00), 2000.
 
 
BibTex
x
 
@article{ 10.1109/ISPAN.2000.900274,
author = {S. Tayu and M. Katsura and M. Kaneko},
title = {An Approximation Algorithm for Multiprocessor Scheduling of Trees with Communication Delays},
journal ={Parallel Architectures, Algorithms, and Networks, International Symposium on},
volume = {0},
year = {2000},
issn = {1087-4089},
pages = {114},
doi = {http://doi.ieeecomputersociety.org/10.1109/ISPAN.2000.900274},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Parallel Architectures, Algorithms, and Networks, International Symposium on
TI - An Approximation Algorithm for Multiprocessor Scheduling of Trees with Communication Delays
SN - 1087-4089
SP
EP
A1 - S. Tayu,
A1 - M. Katsura,
A1 - M. Kaneko,
PY - 2000
KW - null
VL - 0
JA - Parallel Architectures, Algorithms, and Networks, International Symposium on
ER -
 
In this paper, we investigate multiprocessor scheduling of trees considering the communication delay. The objective of our study is to minimize the makespan of the scheduling. We propose an approximation algorithm for computing a scheduling of trees when each task and communication have unit execution times. We show that the approximation difference of the total completion time of our proposal algorithm from the optimum is at most [m \over 2], where m is the number of processing elements. We also show that our algorithm is optimal for m = 2.
Citation:
S. Tayu, M. Katsura, M. Kaneko, "An Approximation Algorithm for Multiprocessor Scheduling of Trees with Communication Delays," ispan, pp.114, 2000 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '00), 2000
Usage of this product signifies your acceptance of the Terms of Use.