Problem Breakdown
Kitchen Orders
Try This Problem Yourself
Practice in the AI-enabled editor with real-time feedback
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 quietly 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.
The setup
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.
| Recipe | Steps |
|---|---|
| Burger | PREP 30 → GRILL 90 |
| Salad | PREP 30 → CHOP 60 |
| Pasta | PREP 30 → CHOP 60 → GRILL 90 |
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.
| Chef | PREP | CHOP | GRILL |
|---|---|---|---|
| Alice | 1.5 | 1.5 | 0.5 |
| Bob | 1.5 | 0.5 | 1.5 |
| Carol | 0.5 | 1.5 | 1.5 |
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.
Solution 1, the greedy pass
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.
The earliest-finishing choice almost always picks that specialist when they're free, since each station has one chef who's three times faster than the others. The makespan is what we're minimizing. It's the maximum end time across every step, and it climbs whenever a step is forced to wait.
Read the timeline one station at a time. The three preps run back to back on Carol from 0 to 45, because the prep station holds one chef at a time and serializing three 15-second preps is the best anyone can do. Burger's grill takes Alice from 15 to 60. Salad's chop runs on Bob from 30 to 60, and Pasta's chop follows on Bob from 60 to 90. Now look at the grill. It's free at 60, but Pasta's grill can't start until Pasta's chop finishes at 90, so the grill sits idle from 60 to 90 and Pasta finally grills from 90 to 135. The makespan is 135.
public Schedule schedule(Order order) {
List<Chef> chefs = getChefs();
Map<ChefId, Integer> chefFree = new HashMap<>();
for (Chef chef : chefs) {
chefFree.put(chef.id, 0);
}
Map<Station, Integer> stationFree = new EnumMap<>(Station.class);
for (Station station : Station.values()) {
stationFree.put(station, 0);
}
List<ScheduleEntry> entries = new ArrayList<>();
for (Dish dish : order.dishes) {
int previousEnd = 0;
List<RecipeStep> steps = dish.recipe.orderedSteps;
for (int stepIndex = 0; stepIndex < steps.size(); stepIndex++) {
Station station = steps.get(stepIndex).station;
int base = steps.get(stepIndex).baseSeconds;
Chef bestChef = null;
int bestStart = 0;
int bestEnd = Integer.MAX_VALUE;
for (Chef chef : chefs) {
int start = Math.max(previousEnd, Math.max(chefFree.get(chef.id), stationFree.get(station)));
int end = start + chef.timeForStep(station, base);
if (end < bestEnd) {
bestEnd = end;
bestStart = start;
bestChef = chef;
}
}
entries.add(new ScheduleEntry(dish, stepIndex, station, bestChef, bestStart, bestEnd));
chefFree.put(bestChef.id, bestEnd);
stationFree.put(station, bestEnd);
previousEnd = bestEnd;
}
}
return new Schedule(entries);
}
This is a greedy schedule, and it's a perfectly valid one. Every constraint holds. It just isn't fast.
Complexity
O(total steps × chefs). Each step is placed exactly once, and placing it tries every chef to find the earliest finish. There's no backtracking and no search, so the work is linear in the number of steps.
Where it breaks
The three-dish order finishes at 135 against a target of 105. The four-dish and five-dish orders come in at 165 and 195 against 120 and 135. The grill idling from 60 to 90 is the whole story. Pasta needs the grill last, and the greedy pass queued Pasta's chop behind Salad's chop, so Pasta arrives at the grill 30 seconds later than it had to.
The fix isn't a better chef
Notice what is not wrong. The greedy pass already used the specialists. Swapping chefs around won't recover those 30 seconds. The waste came from order. We prepped and chopped Salad before Pasta, and that one decision pushed Pasta's grill to the back.
Solution 2, dispatch the best ready step
So stop marching through the dishes in input order. At any moment, each unfinished dish has exactly one step that's ready to run, which is its next step in recipe order. Gather those ready steps across all the dishes and, each round, schedule the one that can finish earliest. Assign it the chef that finishes it soonest, commit it, and advance that dish to its next step.
public Schedule schedule(Order order) {
List<Chef> chefs = getChefs();
List<Dish> dishes = order.dishes;
int[] nextStep = new int[dishes.size()];
int[] dishReady = new int[dishes.size()];
Map<ChefId, Integer> chefFree = new HashMap<>();
for (Chef chef : chefs) {
chefFree.put(chef.id, 0);
}
Map<Station, Integer> stationFree = new EnumMap<>(Station.class);
for (Station station : Station.values()) {
stationFree.put(station, 0);
}
List<ScheduleEntry> entries = new ArrayList<>();
int total = 0;
for (Dish dish : dishes) {
total += dish.recipe.orderedSteps.size();
}
for (int placed = 0; placed < total; placed++) {
int[] bestKey = null;
int bestIndex = -1, bestStepIndex = 0, bestStart = 0, bestEnd = 0;
Station bestStation = null;
Chef bestChef = null;
Dish bestDish = null;
for (int index = 0; index < dishes.size(); index++) {
int stepIndex = nextStep[index];
List<RecipeStep> steps = dishes.get(index).recipe.orderedSteps;
if (stepIndex == steps.size()) {
continue;
}
Station station = steps.get(stepIndex).station;
int base = steps.get(stepIndex).baseSeconds;
int chosenEnd = Integer.MAX_VALUE, chosenStart = 0;
Chef chosenChef = null;
for (Chef chef : chefs) {
int start = Math.max(dishReady[index], Math.max(chefFree.get(chef.id), stationFree.get(station)));
int end = start + chef.timeForStep(station, base);
if (end < chosenEnd) {
chosenEnd = end;
chosenStart = start;
chosenChef = chef;
}
}
int[] key = {chosenEnd, chosenStart, index};
if (bestKey == null || lessThan(key, bestKey)) {
bestKey = key;
bestIndex = index;
bestDish = dishes.get(index);
bestStepIndex = stepIndex;
bestStation = station;
bestChef = chosenChef;
bestStart = chosenStart;
bestEnd = chosenEnd;
}
}
entries.add(new ScheduleEntry(bestDish, bestStepIndex, bestStation, bestChef, bestStart, bestEnd));
chefFree.put(bestChef.id, bestEnd);
stationFree.put(bestStation, bestEnd);
dishReady[bestIndex] = bestEnd;
nextStep[bestIndex] += 1;
}
return new Schedule(entries);
}
private static boolean lessThan(int[] a, int[] b) {
for (int i = 0; i < a.length; i++) {
if (a[i] < b[i]) {
return true;
}
if (a[i] > b[i]) {
return false;
}
}
return false;
}
This is smarter than walking the dishes in order, because it can interleave them. When several dishes are waiting, it picks the step that frees its resources soonest instead of blindly finishing dish one before touching dish two.
Complexity
O(total steps × dishes × chefs). Each placed step scans every dish to find the ready steps, and scans every chef for each candidate. Still polynomial, still a single forward pass with no backtracking.
Where it breaks
On the busy benchmark orders, dispatch genuinely helps. The six-dish order drops from 225 to 210, and the nine-dish order drops from 285 to 255. But on the three small targets it ties the dish-order pass at 135, 165, and 195, and it still misses every target across the board. The reason is structural. A single greedy pass commits to each pick the instant it makes it. When the earliest-finishing step now is the one that strands the grill later, dispatch takes it anyway, because it has no way to look ahead and no way to take the choice back.
Pattern: Backtracking
When greedy stops being good enough, you fall back to searching the orderings, trying a choice, recursing, and undoing it when a branch can't beat your best. That's backtracking with a bound to prune dead ends early.
Solution 3, search the orderings
If no single pass is good enough, then the ordering itself is the thing to search. This is branch-and-bound. At each point in the search, the next ready step of every unfinished dish is a candidate. We try one, recurse into the smaller problem that's left, then undo it and try the next, exploring the tree of possible orderings. A plain search of that tree would be far too slow, so the "bound" half is what makes it work.
A lower bound is an optimistic estimate of the best makespan any completion of the current partial schedule could reach, built so that it never overestimates. If even that optimistic number is already at least as large as the best full schedule we've found, then nothing in this branch can beat what we already have, and we drop the entire subtree without exploring it. The solution-space tree shrinks dramatically once the bound starts cutting.
Three pieces make the bound tight enough to prune well. The first is the latest time any chef or station is already busy, since the schedule can't finish before its busiest resource is done. The second looks at each station on its own. Take when that station next frees up and add all the work still headed for it, timed at its fastest chef, because those steps share one station and have to run one after another. The third looks at each dish on its own. Take the dish's ready time and add the rest of its steps at their fastest chefs, since a dish's steps can't overlap each other. The bound is the largest of these three, and because each piece only ever undercounts the real remaining time, the bound is safe to prune against.
Two more observations trim the tree further. With these chefs, the non-specialists are never worth using, because a non-specialist takes three times as long on a step and ties up a chef who could be doing nothing better elsewhere. That means each step's chef is effectively forced to the specialist, and the only real choice left is ordering. And many orders repeat a recipe, so two dishes that share a recipe and sit at the same step with the same ready time are interchangeable. Trying both leads to identical subtrees, so we explore only one.
public Schedule schedule(Order order) {
return new Planner(getChefs(), order).run();
}
private static final class Planner {
final List<Chef> chefs;
final List<Dish> dishes;
final Station[] stations = Station.values();
final int num;
final int total;
final int[] lens;
final RecipeStep[][] steps;
final String[] signature;
final int[][] fastestDur;
final int[][] tail;
final Chef[] fastestChef;
final Map<ChefId, Integer> chefIndex = new HashMap<>();
int bestMakespan = Integer.MAX_VALUE;
List<ScheduleEntry> bestEntries = null;
final Map<String, Integer> memo = new HashMap<>();
Planner(List<Chef> chefs, Order order) {
this.chefs = chefs;
this.dishes = order.dishes;
this.num = dishes.size();
for (int i = 0; i < chefs.size(); i++) {
chefIndex.put(chefs.get(i).id, i);
}
fastestChef = new Chef[stations.length];
for (int st = 0; st < stations.length; st++) {
Chef fastest = chefs.get(0);
for (Chef chef : chefs) {
if (chef.timeForStep(stations[st], 60) < fastest.timeForStep(stations[st], 60)) {
fastest = chef;
}
}
fastestChef[st] = fastest;
}
lens = new int[num];
steps = new RecipeStep[num][];
signature = new String[num];
fastestDur = new int[num][];
tail = new int[num][];
int sum = 0;
for (int d = 0; d < num; d++) {
List<RecipeStep> recipeSteps = dishes.get(d).recipe.orderedSteps;
lens[d] = recipeSteps.size();
sum += lens[d];
steps[d] = recipeSteps.toArray(new RecipeStep[0]);
StringBuilder sb = new StringBuilder();
fastestDur[d] = new int[lens[d]];
for (int si = 0; si < lens[d]; si++) {
RecipeStep step = steps[d][si];
sb.append(step.station.ordinal()).append(",").append(step.baseSeconds).append(";");
fastestDur[d][si] = fastestChef[step.station.ordinal()].timeForStep(step.station, step.baseSeconds);
}
signature[d] = sb.toString();
tail[d] = new int[lens[d] + 1];
for (int si = lens[d] - 1; si >= 0; si--) {
tail[d][si] = tail[d][si + 1] + fastestDur[d][si];
}
}
total = sum;
}
Schedule run() {
search(new int[num], new int[num], new int[chefs.size()], new int[stations.length], new ArrayList<>());
return new Schedule(bestEntries);
}
int lowerBound(int[] nextStep, int[] dishReady, int[] chefFree, int[] stationFree) {
int bound = 0;
for (int v : chefFree) bound = Math.max(bound, v);
for (int v : stationFree) bound = Math.max(bound, v);
int[] remaining = new int[stations.length];
for (int d = 0; d < num; d++) {
for (int si = nextStep[d]; si < lens[d]; si++) {
remaining[steps[d][si].station.ordinal()] += fastestDur[d][si];
}
}
for (int st = 0; st < stations.length; st++) {
bound = Math.max(bound, stationFree[st] + remaining[st]);
}
for (int d = 0; d < num; d++) {
if (nextStep[d] < lens[d]) {
bound = Math.max(bound, dishReady[d] + tail[d][nextStep[d]]);
}
}
return bound;
}
String canonical(int[] nextStep, int[] dishReady) {
String[] parts = new String[num];
for (int d = 0; d < num; d++) {
parts[d] = signature[d] + "|" + nextStep[d] + "|" + dishReady[d];
}
Arrays.sort(parts);
return String.join(";", parts);
}
void search(int[] nextStep, int[] dishReady, int[] chefFree, int[] stationFree, List<ScheduleEntry> entries) {
if (entries.size() == total) {
int makespan = 0;
for (int v : chefFree) makespan = Math.max(makespan, v);
for (int v : stationFree) makespan = Math.max(makespan, v);
if (makespan < bestMakespan) {
bestMakespan = makespan;
bestEntries = new ArrayList<>(entries);
}
return;
}
int bound = lowerBound(nextStep, dishReady, chefFree, stationFree);
if (bound >= bestMakespan) {
return;
}
String key = canonical(nextStep, dishReady) + "#" + Arrays.toString(chefFree) + "#" + Arrays.toString(stationFree);
Integer prev = memo.get(key);
if (prev != null && prev <= bound) {
return;
}
memo.put(key, bound);
List<int[]> candidates = new ArrayList<>();
Set<String> seen = new HashSet<>();
for (int d = 0; d < num; d++) {
int si = nextStep[d];
if (si == lens[d]) {
continue;
}
String mark = signature[d] + "|" + si + "|" + dishReady[d];
if (seen.contains(mark)) {
continue;
}
seen.add(mark);
RecipeStep step = steps[d][si];
Chef chef = fastestChef[step.station.ordinal()];
int ci = chefIndex.get(chef.id);
int pi = step.station.ordinal();
int start = Math.max(dishReady[d], Math.max(chefFree[ci], stationFree[pi]));
int end = start + chef.timeForStep(step.station, step.baseSeconds);
candidates.add(new int[]{end, d, ci, pi, start, si});
}
candidates.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
for (int[] c : candidates) {
int end = c[0], d = c[1], ci = c[2], pi = c[3], start = c[4], si = c[5];
int[] ns = nextStep.clone(); ns[d] += 1;
int[] dr = dishReady.clone(); dr[d] = end;
int[] cf = chefFree.clone(); cf[ci] = end;
int[] sf = stationFree.clone(); sf[pi] = end;
RecipeStep step = steps[d][si];
entries.add(new ScheduleEntry(dishes.get(d), si, step.station, fastestChef[pi], start, end));
search(ns, dr, cf, sf, entries);
entries.remove(entries.size() - 1);
}
}
}
Here's the same three-dish order the greedy pass botched, now scheduled by the search.
The difference is one swap. Pasta gets prepped second and chopped first, so its chop runs from 30 to 60 on Bob. That puts Pasta at the grill at 60, exactly when Burger's grill frees the station, and the two grills run back to back from 15 to 60 and 60 to 105 with no idle gap. The makespan is 105, and the search reaches the same kind of optimum on every other case too.
Complexity
Exponential in the worst case, since branch-and-bound is still exploring a tree of orderings. What keeps it fast in practice is the combination of a tight lower bound, the memo that skips resource states already seen with an equal-or-better bound, the forced specialist that collapses the chef choice, and the symmetry cut that ignores interchangeable dishes. On the largest benchmark order it settles the optimum in about a second.
Where it wins
It hits 105, 120, and 135 on the three guided cases and clears every benchmark order inside its time budget. The nine-dish order lands at exactly 240, the target, in about a second against a 2.5-second limit.
Branch-and-bound returns the true optimum for the chefs and orders in this problem, but the general version is hard. Scheduling steps with precedence constraints across machines whose speeds vary is a flexible job-shop problem, which is NP-hard, so there's no known algorithm that stays fast as the orders grow without bound. This search stays quick here because the instances are small, the bound prunes aggressively, the specialist rule removes the chef dimension, and repeated recipes collapse by symmetry. The lower bound and the memo are the load-bearing pieces. Drop either one and the nine-dish order goes from about a second to well past its time budget, while the specialist rule and the symmetry cut trim a bit more on top.
Benchmarks
Makespan from each solution on each order, with the search timed on the default chefs.
| Order | Target | Greedy | Dispatch | Search | Search time |
|---|---|---|---|---|---|
| three_dish | 105 | 135 | 135 | 105 | 0.2ms |
| four_dish | 120 | 165 | 165 | 120 | 0.5ms |
| five_dish | 135 | 195 | 195 | 135 | 0.8ms |
| balanced_six | 195 | 225 | 210 | 195 | 44ms |
| prep_bottleneck_seven | 195 | 255 | 240 | 195 | 210ms |
| mixed_eight | 210 | 255 | 225 | 210 | 153ms |
| deep_nine | 240 | 285 | 255 | 240 | 928ms |
Greedy and dispatch miss every target. Dispatch beats greedy on the four larger orders and ties it on the three small ones, which is the tell that a better one-pass rule was never going to be enough.
Takeaways
The three schedulers share almost all of their machinery. They compute start times the same way, they respect the same constraints, and they all reach for the fast chef. What separates them is when they commit to the order steps run in.
Greedy commits at the worst possible moment, which is up front, by fixing the dish order before it knows anything about how the resources will line up. Dispatch commits a little later, one ready step at a time, which is enough to interleave dishes but not enough to undo a pick that looks good now and bad in hindsight. The search commits to nothing it can't take back. It explores orderings, keeps the best complete schedule it has seen, and uses a lower bound to throw away the orderings that can't possibly beat it.
The move worth remembering is to split "make it valid" from "make it good". Get a legal schedule first, then notice when a greedy rule is structurally stuck, and reach for a bounded search that leans on the problem's own structure to stay fast. A tight lower bound, a memo over repeated states, dominated choices, and interchangeable work are what turn an exponential tree into a search that finishes in a second.