Paper Info
Title
Polynomial Algorithms for MPSP Using Parametric Linear Programming
Abstract
The multiprocessor scheduling problem(MPSP), p\prec,p(j) = 1\C-max, is known to be NP-complete. The problem is polynomially solvable, however, if the precedence relations are of the intree(outtree) type, P\intree(outtree), p(j) = 1\C-max, or if the number of processors is two, P2\prec, p(j) = 1\Cmax. In this paper, we introduce a parametric linear program which gives a lower bound for the makespan of MPSP and retrieves the makespans of the two polynomially solvable problems.
Year
DOI
Venue
2004
10.1007/978-3-540-25967-1_4
LECTURE NOTES IN COMPUTER SCIENCE
Keywords
Field
DocType
linear program,multiprocessor scheduling,lower bound
Discrete mathematics,Combinatorics,Multiprocessor scheduling,Job shop scheduling,Parametric programming,Upper and lower bounds,Directed acyclic graph,Parametric statistics,Parametric linear programming,Linear programming,Mathematics
Conference
Volume
ISSN
Citations 
3075
0302-9743
0
PageRank 
References 
Authors
0.34
7
1
Name
Order
Citations
PageRank
Babak Mougouie1686.01