An NC algorithm for finding a minimum weighted completion time schedule on series parallel graphs

被引：1

作者：

Sunder, S ^{[1
]}

He, X ^{[1
]}

机构：

[1] SUNY BUFFALO, DEPT COMP SCI, BUFFALO, NY 14260 USA

来源：

ALGORITHMICA | 1996年 / 16卷 / 03期

关键词：

scheduling; series parallel graphs; NC algorithms; parallel algorithm;

D O I：

10.1007/BF01955675

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We present a parallel algorithm for solving the minimum weighted completion time scheduling problem for transitive series parallel graphs. The algorithm takes O (log(2) n) time with O (n(3)) processors on a CREW PRAM, where n is the number of vertices of the input graph. This is the first NC algorithm for solving the problem.

引用

页码：243 / 262

页数：20

共 18 条

[11] SINGLE-MACHINE JOB SEQUENCING WITH TREELIKE PRECEDENCE ORDERING AND LINEAR DELAY PENALTIES [J].