The Joy of Baking (Optimally)

‘Tis the season of baking all kinds of things: cookies, cakes, breads, brownies, pies, and my favorite Brazilian dessert “pudim de leite moça“, which is depicted below. Click here for the step-by-step recipe.

Many OR bloggers, such as Laura McLay and Anna Nagurney, actually enjoy baking, and they both have written posts on the subject (e.g. here and here). I happen to include myself in this group and, yes, I made the pudim shown above (using  my mom’s recipe).

My goal today is to approach the art of baking from an optimization point of view. Let’s say you have a long list of items to bake. Perhaps you’re hosting a mega party at your house, or you’re helping your local church or favorite charity with their holiday cooking. You have an oven that can only fit so much at a time (think of area, or volume). Each item to be baked occupies some space in the oven and needs to bake for a specific amount of time. In what order should you bake your items so that you finish as soon as possible? (Side note: it may not be obvious at first sight, but this is the same problem faced by a container port that needs to decide the order in which to unload cargo ships.)

In the OR world, this is a job scheduling problem with a cumulative machine. The jobs are the tasks to be performed (items to bake), the machine (or resource) is the oven. We say the oven is cumulative, as opposed to disjunctive, because it can deal with (bake) multiple items at a time. The unknowns in this optimization problem are the start times of each job (when to begin baking each item). The objective is to minimize the makespan, which is defined as the finish time of the last job (the time at which it’s OK to turn off the oven). Finally, this is a non-preemptive problem because, typically, once you start baking something, it stays in the oven until it’s done.

This problem occurs so often in practice that the Constraint Programming (CP) community created a global constraint to represent it. It’s called the cumulative constraint (what a surprise!). Here’s a reference. For example, let’s say that we have a -cubic-foot (cf) oven and we need to bake five items. The baking times (in minutes) are , , , , and . The space requirements in cf are, respectively, , , , , . If the time at which we begin baking item is denoted by the variable , we can write the following in a CP model:

The above constraint makes sure that the start times are such that the capacity of the oven is never exceeded. To minimize the makespan, we have to minimize the maximum among , , , , and .

It’s easy to incorporate some real-life details into this model. For example:

• Not every item will be ready to go into the oven at time zero. After all, you’re making them as you go. To take care of this, add a ready-time (i.e. a lower bound) to the appropriate variable: .
• If a given item does not occupy the entire oven, but you still prefer to bake it alone, just artificially increase its space requirement to be equal to the oven’s capacity .
• If you’re baking both savory and sweet things, you probably don’t want to mix them up in the oven. In that case, simply solve the problem twice.
• If, for some reason, item must be finished before item starts baking (e.g. they need different temperatures), just include the constraint , where is the baking time of item .

We could, of course, have approached this problem from an Integer Programming point of view. In that case, we’d have binary variables that are equal to 1 if you start baking item at time , and equal to zero otherwise. For more details on this formulation, including model files and some pretty tough instances, take a look at the CuSPLIB web page.

In the spirit of holiday baking, I will close with some pictures of past baking jobs ran on my house’s machine (a.k.a. oven). Enjoy! :-)

Key Lime Pie

Carrot Oatmeal Cookies (recipe here)

Sparkling Ginger Chip Cookies (recipe here)

Irish Soda Bread

Six-Seed Soda Bread (recipe here)