Problem Statement

Problem Description Real-World Scenario: A high-volume restaurant kitchen has S cooking stations (grill, saute, fryer, ...). Each incoming dish is a recipe: a sequence of prep steps with dependencies (e.g., the protein must be marinated before grilling; the sauce must be reduced before plating). Each step has a station type and a duration. The dishes form a DAG: nodes are prep steps across all dishes; edges encode " step U must finish before step V starts " . Each station can run only one step at a time; when a step is ready (all prerequisites done) and its station is free, it begins immediately. If multiple ready steps compete for the same station, the one with the earliest ready time wins; ties broken by the smaller step-id. The Challenge: Compute the completion time of every step and the overall makespan (time at which the last step finishes). Why This Problem is Multi-Concept: Topological sort establishes processing order over the DAG. Critical-path DP computes earliest-ready times