public class CPM extends Object
CPMclass provides a client that solves the parallel precedence-constrained job scheduling problem via the critical path method. It reduces the problem to the longest-paths problem in edge-weighted DAGs. It builds an edge-weighted digraph (which must be a DAG) from the job-scheduling problem specification, finds the longest-paths tree, and computes the longest-paths lengths (which are precisely the start times for each job).
This implementation uses
AcyclicLP to find a longest
path in a DAG.
The program takes Θ(V + E) time in
the worst case, where V is the number of jobs and
E is the number of precedence constraints.
For additional documentation, see Section 4.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
|Modifier and Type||Method and Description|
Reads the precedence constraints from standard input and prints a feasible schedule to standard output.
public static void main(String args)
args- the command-line arguments