Kitchen Orders

A kitchen has to cook an order made of several dishes. Each dish follows a recipe, which is a fixed sequence of station steps, and you assign every step to one of three chefs. The goal is to finish the whole order as fast as possible. It reads like a chef-assignment puzzle, and that framing is a trap. The hard part is deciding the order the steps run in, and that's where a natural greedy solution leaves a third of the time on the floor.

We'll build three schedulers. The first produces a valid plan by walking the dishes in order, and it works until the makespan targets show up. The second stops marching through dishes one at a time and instead grabs the best ready step each round, which helps on busy orders but still falls short. The third treats the ordering as a search, prunes hard, and lands on the optimum while staying inside every time budget.

An order holds a list of dishes. Each dish has a recipe, and a recipe is an ordered list of station steps with a base time in seconds. There are three stations.

There are three chefs, and each one runs some stations faster than others. A chef's actual time on a step is the step's base time multiplied by that chef's factor for the station.

Every station has exactly one specialist who runs it at half time, and the other two run it at one-and-a-half times. So the fast times are PREP 15 (Carol), CHOP 30 (Bob), and GRILL 45 (Alice), and the slow times are three times as long. Three rules keep a schedule honest. The steps inside a dish run in recipe order, a chef does one step at a time, and a station holds one chef at a time. The makespan is the moment the last step finishes, and that's the number we minimize.

The order [Burger, Salad, Pasta] is small enough to reason about by hand. Its optimum is 105 seconds. Hold onto that number, because the first two solutions miss it.

The natural first attempt walks the dishes in the order they arrive. For each step of each dish, you hand the step to whichever chef can finish it earliest, and you start it at the earliest moment that's actually legal. That earliest legal start is the latest of three times. The dish's previous step has to be done, the chef has to be free, and the station has to be free.