Description🔗

cooking-buddy is a Python script that parses a JSON file describing your dinner plan, converting your ideas about what you want to cook and how you might cook it into a set of constraints that can then be optimized for shortest makespan. It relies on Google's OR-Tools library and underlying CP-SAT solver to specify and solve the constraint problem — it is a modification of the example program Google provides for solving RCPSP problems, simplifying the algorithm and accepting a more user-friendly input format.

Method🔗

cooking-buddy interprets the general problem of planning out your cooking as a multi-modal RCPSP-Max constraint problem. This means that, if you can define the tasks you need to do, the dependency graph between them, and the list of resources those tasks use, then cooking-buddy can attempt to determine the optimal schedule of what to do when, using which resources.

RCPSP-Max🔗

A Resource-Constrained Project Scheduling Problem is a kind of scheduling problem where tasks need to be completed using renewable resources, with the goal of using the least amount of time possible to get everything done. The additional -Max qualification means that the constraints placed on the successors also have their own maximum delay. I've taken a loose interpretation of this and applied it to the presented usecase to mean that every successor constraint can be delayed up-to a certain amount, but no more than that (before the required successor must be scheduled).

Multi-modal🔗

Additionally, each task can have multiple modes, or "recipes", specified. This way, you can provide alternative methods for completing the same task in case one is blocked due to resource constraints. As an example, you might imagine that one task you might need to perform would be to melt some butter. Normally you might do this on the stove-top in a pot, but you can also specify that it could be done in the microwave instead; that way, if the stove-top is occupied when you need the melted butter, cooking-buddy can instead suggest plans that use the microwave without having to wait for the stove-top to become available. Which mode is picked does not, however, have a general effect on the schedule beyond the resource decisions: cooking-buddy adopts a simplified model of the usual RCPSP-Max paradigm, where a specified delay is universal across all modes and is time- and resource-independent.

Tasks & Resources🔗

cooking-buddy takes a slightly simplified approach in modelling tasks and resources. Tasks happen simultaneously given sufficient resources, and there is no minimum distance between tasks (which is unfortunate for those of us who cannot instantly teleport around the kitchen, so they should plan accordingly by padding out task timings). Resources are considered to be renewable and have no maintenance or cooldown periods (all resources may be used as many times as necessary, are only considered unavailable when in use, and do not necessitate extra time between uses).

{
  "tasks": {
    "asparagus": {
      "wash": {
        "recipes": [
          {
            "duration": 5,
            "demands": [
              [1, "sink"],
              [1, "worker"]
            ]
          }
        ],
        "successors": [
          ["asparagus.prep", -1]
        ]
      },
      "prep": {
        "recipes": [
          {
            "duration": 5,
            "demands": [
              [1, "counter_top"],
              [1, "worker"]
            ]
          }
        ],
        "successors": [
          ["asparagus.bake", -1]
        ]
      },
      "bake": {
        "recipes": [
          {
            "duration": 15,
            "demands": [
              [1, "oven"]
            ]
          }
        ]
      }
    },
    "green_beans": {
      "wash": {
        "recipes": [
          {
            "duration": 5,
            "demands": [
              [1, "sink"],
              [1, "worker"]
            ]
          }
        ],
        "successors": [
          ["green_beans.boil", -1]
        ]
      },
      "boil": {
        "recipes": [
          {
            "duration": 5,
            "demands": [
              [1, "burner"]
            ]
          }
        ],
        "successors": [
          ["green_beans.shock",  0]
        ]
      },
      "shock": {
        "recipes": [
          {
            "duration": 10,
            "demands": []
          }
        ]
      }
    },
    // ...
  },
  "resources": [
    ["burner", 5],
    ["counter_top", 3],
    ["food_processor", 1],
    ["oven", 2],
    ["sink", 1],
    ["worker", 2]
  ],
  "params": {
    "dinner": "17:00"
  }
}

Points of interest🔗

It's neat. I'm not sure that there's anything of particular interest in this specific implementation (nothing about this is new or foundational per se), I just think the notion that you can quickly and easily optimize the task of cooking a big dinner without too much effort or any big Gantt charts is neat.

Things I learned🔗

Forward planning smells like constraint satisfaction 🧑‍🍳🔗

Usually when I think of how to solve planning problems I think of [forward] search in state graphs; but, search techniques like backtracking and branch-and-bound are also traditionally the ways you solve constraint-satisfaction problems! This project really reinforced the similarity between the two paradigms for me in a pragmatic way, beyond just the textbook notion that they might both be solved via search. And, with the obvious benefit that reformulating the planning problem as a constraint problem lets me make use of existing open source constraint solving toolkits, which are heavily optimized and can solve these problems way faster in practice than I might with my own handwritten branch-and-bound solution (in this particular case I used Google's CP-SAT since it's been regularly winning gold on the MiniZinc challenge for the last few years, and because it's open source and has decent bindings for popular languages).

Where to next🔗

Remove relaxations🔗

My kitchen is not a restaurant; I cannot fire my mother.

Aside from the assumptions and problem relaxations mentioned above, one of the main issues with a model like this is that it is offline and assumes both perfect planning and execution. Clearly, even professional kitchens with highly-trained brigades de cuisine make mistakes and experience slowdowns from time to time, let alone my own hectic kitchen on Thanksgiving. A system that can accept realtime feedback and update the plan accordingly would be a better model; however, it would likely require a step back towards search algorithms (like D* or another online technique) and further research into the existing literature to determine prior art and alternative approaches. Further optimizations may also include recombining similar/identical/overlapping tasks (e.g. if you need to wash and peel some tomatoes for a salad and also for a stew, and it's okay for the tomatoes to sit out for a while after being prepped, then combining both prep steps into one logical step could yield a more efficient solution) and other attempts to simplify the dependency graph and.

Product?🔗

I have to wonder if leaning into the user-friendly nature of this project might present the opportunity for a marketable product? Is this functionality something that, once improved upon, could be placed behind a UI/API and offered as a planning product to industries that involve the class of projects being solved for here? Continuing with the example of professional kitchens, handling variable order volume and online updating of the execution plan would seem like useful features, if they can be made available with minimal overhead (inputting updates cannot take longer than simply shouting orders to line cooks and dealing with the consequences, otherwise knowing the "optimal" result wouldn't be very useful). Something to explore in the future when I have more time.