Implement Deterministic Workflow Scheduling

Databricks Workflows executes tasks whose dependencies form a directed acyclic graph. Implement a scheduler that produces a deterministic execution order and computes the earliest completion time for every task when unlimited parallel execution is available.

A task can start only after all of its prerequisites finish. When multiple tasks are ready, choose the lexicographically smallest task ID. If the dependency graph contains a cycle, no valid schedule exists.

Formal Specification

Implement schedule_workflow(tasks, dependencies).

• tasks is a dictionary mapping a unique string task ID to a nonnegative integer duration.
• dependencies is a list of two-element lists [prerequisite, dependent].
• Each dependency means prerequisite must finish before dependent starts.
• Return None if the graph contains a cycle.
• Otherwise, return a dictionary with:
  • order: the deterministic topological order of task IDs.
  • finish_times: a dictionary mapping each task ID to its earliest finish time.
  • makespan: the earliest time at which all tasks finish.

Tasks with no prerequisites start at time zero. The scheduler must not mutate its inputs.