Scheduling Algorithm

A major component of our application is the part that decides the order of steps in a meal. This is the part that needs to achieve the decrease in scheduled time. In order to accomplish this, the scheduler takes into account two pieces of information about each step. The first is the estimated time each step will take and the second is whether or not each step can be done simultaneously or not.

The algorithm starts with all of the recipes steps unscheduled and tries to schedule the next step whenever the client calls “getNextStep” and the next step hasn’t been scheduled yet. A next step can not be scheduled if all of the recipes have no currently available next steps. A recipe has no currently available next steps if either all of the steps in the recipe have been scheduled or the recipe is still blocked on a simultaneous step. To become unblocked from a simultaneous step, the client must explicitly call “finishSimultaneousStepFromRecipe”. In the case where one or more next steps can be scheduled, the scheduler selects the most optimal one based off of a seemingly odd metric. Given multiple recipes with an available next step, the scheduler will choose the one that has the smallest amount of time from the next simultaneous step to the last step in the recipe.

This metric was chosen because we found that the problem is both NP complete and unpredictable due to the variability in actual step completion times. Other more intuitive metrics, such as choosing the next step from the available recipe with the smallest amount of time until the next simultaneous step, fail in specific and important cases. For example, with this alternative metric the scheduler would fail when one recipe has a really long simultaneous step and the other recipe takes much less time, but has a small simultaneous step earlier in the cooking process. The seemingly odd metric that we actually used tends to both select steps from recipes with larger and earlier simultaneous blocks of time. These properties are very desirable and they addressed the issues we found with other strategies.