public class CPM extends Object
CPM
class 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 running time is proportional to V + E,
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.
public static void main(String[] args)
args
- the command-line arguments