Title :
An NC algorithm for finding minimum weighted completion time schedule on series parallel graphs
Author :
Sunder, S. ; He, Xin
Author_Institution :
Dept. of Comput. Sci., State Univ. of New York, Buffalo, NY, USA
Abstract :
The authors present a parallel algorithm for solving the minimum weighted completion time scheduling problem for transitive series parallel graphs. The algorithm takes O(log2 n ) time with O(n3) processors on a CREW (concurrent-read exclusive-write) PRAM (parallel random-access machine), where n is the number of vertices of the input graph. It is noted that this is the first NC algorithm for solving the problem
Keywords :
computational complexity; parallel algorithms; random-access storage; scheduling; CREW; NC algorithm; PRAM; concurrent-read exclusive-write; minimum weighted completion time schedule; parallel algorithm; series parallel graphs; Algorithm design and analysis; Computer science; Design optimization; Helium; Optimal scheduling; Parallel algorithms; Phase change random access memory; Processor scheduling; Scheduling algorithm; Virtual manufacturing;
Conference_Titel :
Parallel and Distributed Processing, 1992. Proceedings of the Fourth IEEE Symposium on
Conference_Location :
Arlington, TX
Print_ISBN :
0-8186-3200-3
DOI :
10.1109/SPDP.1992.242754
