Critical Task

PERT-based scheduling tool for modeling task dependencies and identifying critical paths in project timelines. Critical path analysis underpins scheduling in construction, manufacturing, and software delivery — this implementation uses topological sorting over a DAG to compute it efficiently.

Overview

A Java implementation of PERT/CPM scheduling built as a class project in Fall 2024. The tool models task dependencies as a directed acyclic graph and computes critical paths in O(V+E) time using topological sorting with forward and backward passes. For more reading: PERT

Role

Lead developer.

Problem

PERT scheduling by hand is tractable for small networks but becomes error-prone as the number of tasks grows. Manually tracing forward and backward passes through a graph with dozens of dependencies is tedious and mistakes in slack computation cascade — a single wrong earliest-finish value can misidentify the critical path entirely. The motivation was to automate this process and make it reliable regardless of graph size.

Implementation

The graph is represented as an adjacency list with directed edges encoding task dependencies. A DFS-based topological sort with onStack[] cycle tracking validates that the input is a DAG before any scheduling runs — if a cycle is detected, the sort returns null and the computation halts rather than producing incorrect output.

The scheduling itself follows the standard PERT two-pass approach. The forward pass iterates vertices in topological order, computing ES = max(EF of predecessors) and EF = ES + duration for each task. The backward pass initializes every vertex’s LF to the project completion time, then processes in reverse topological order: LF = min(LS of successors), LS = LF - duration. Slack is computed as LF − EF across all vertices using a parallel stream.

Zero-slack tasks constitute the critical path. The numCritical() method counts critical vertices; criticalPath() returns the total project duration as the maximum EF across all vertices. The output for each task includes earliest completion, latest completion, slack, and a critical flag.

Testing

Test cases were built from a combination of course-provided inputs and generated cases using LLMs to produce task networks with known critical paths. This allowed verification that the forward/backward passes and slack computation produced correct results across graphs of varying size and structure.