Problem Solved: Implementing OR-Tools - Scheduling (Part 2 of 3)

2. Scheduling

In part one, we looked at solving a vehicle routing problem using OR-Tools. In the second of this three-part series, we'll use OR-Tools again to consider how to best optimise cooking times for our pizzas.

The rules we’ve assigned for this second step are as follows:

• No chef can work on two pizzas at the same time.
• A chef is focusing on one stage of each pizza (prep, shaping, cooking, etc.) at any given time.
• Only one pizza can fit into the oven
• The stage after shaping must start no earlier than 60 minutes after it’s finished. This is a very customised constraint, like a post-stage delay of sorts.
• The objective of scheduling problems is to minimize something referred to as the ‘Horizon’, which is defined at the time at which the last job has finished. This time is relative to the start of the first job. Therefore, the smaller the horizon, the quicker we’ve been able to cook all the pizzas.

With the above rules set, we can visualise a solution to this problem with some sort of Gantt chart, with time increasing to the right.

We have 3 types of pizza that are split into segments: margherita, pepperoni and Hawaiian. Crucially, the margherita does not undergo a slicing stage. So here’s an example of an optimal output where the horizon (the final stage of the last pizza to be made) is as small as possible. Even if we had three chefs that horizon probably wouldn’t be any smaller as we’re constrained by the earliest time we can put the third pizza in the oven.

2.1. Unit Tests

[Fact]
public void Waits_one_hour_after_shaping()
{
    var model = new MakePizzaModel(1, new List {PizzaType.Margherita});
    var solver = new MakePizzaSolver(model);
     
    var solution = solver.Solve();
 
    var cookedPizza = solution.Pizzas[0];
    var shapingStage = cookedPizza.Stages.Single(s => s.Stage == CookingStage.Shaping);
    var preparingStage = cookedPizza.Stages.Single(s => s.Stage == CookingStage.Preparing);
    const int oneHour = 60;
    var expectedPreparingStart = shapingStage.Finish + oneHour;
    preparingStage.Start.Should().Be(expectedPreparingStart);
}

As mentioned in the rules, we wait one hour after shaping. Each pizza solver takes in a number of chefs and a list of pizzas it wants to make. Then the pizza solver takes in the model.

var model = new MakePizzaModel(1, new List<PizzaType> {PizzaType.Margherita});

This equates to one chef making one margherita pizza. So, we cook the pizza and obtain a solution via var solution = solver.Solve(). The MakePizza solver output contains a list of pizzas that have been scheduled. ScheduledPizza has a type, corresponds to our three flavours of pizza.

It also has a number of stages and each stage is a CookingStage which, in turn, is either Shaping , Slicing, Preparing or Cooking. For each type of pizza, return the amount of time that it takes.

public long Finish -> Pizzas.Max(p.SchedulePizza -> Finish)

There is also an extension which uses switch expressions to get the stages. For every type of pizza, the extension returns the stages that are required to make the pizza (see below).

public static Dictionary<CookingStage, long> GetStages(this PizzaType type)
{
    return type switch
    {
        PizzaType.Margherita => new Dictionary<CookingStage, long>
        {
            {CookingStage.Shaping, 30},
            {CookingStage.Preparing, 10},
            {CookingStage.Cooking, 15}
        },
        PizzaType.Hawaiian => new Dictionary<CookingStage, long>
        {
            {CookingStage.Shaping, 30},
            {CookingStage.Slicing, 10},
            {CookingStage.Preparing, 15},
            {CookingStage.Cooking, 17}
        },
        PizzaType.Pepperoni => new Dictionary<CookingStage, long>
        {
            {CookingStage.Shaping, 30},
            {CookingStage.Slicing, 8},
            {CookingStage.Preparing, 20},
            {CookingStage.Cooking, 20}
        },
        _ => throw new ArgumentOutOfRangeException(nameof(type), type, null)
    };
}

The finish of the Solver Output is also a useful getter which gets the max finish of its pizzas, which is the finish of the last stage i.e., the horizon.

public class MakePizzaSolverOutput
{
    public long Finish => Pizzas.Max(p => p.Finish);
 
    public List Pizzas { get; set; } = new ();
}

Returning to our unit tests, we get the single pizza from the solution that is scheduled to be cooked. We also get the stages relevant to this test- shaping and preparing (note that, because it’s a margherita pizza, we know that the stage after shaping is preparing, because we don’t need to slice it).

In this example we’re dealing with minutes and, therefore, oneHour = 60. Our expected preparing start is the finish of the shaping stage plus one hour. This, in turn, allows us to say that the start of the preparing stage should be the expectedPreparingStart, so one hour after the shaping stage.

[Fact]
public void All_pizzas_are_made() 
{
    var random = new System.Random();
    var pizzas = Enumerable.Range(0, 5).Select(_ => random.Enum()).ToList();
    var model = new MakePizzaModel(1, pizzas);
    var solver = new MakePizzaSolver(model);
     
    var solution = solver.Solve();
 
    var expectedCount = pizzas.Count;
    solution.Pizzas.Should().HaveCount(expectedCount);
}

Using Audacia.Random, we can get a randomly selected PizzaType, as we aren’t necessarily concerned with what type of pizzas are being made; just that they are all being made. The expectedCount is the count of pizzas, which is five. We have five random pizza types and one chef. Again, we aren’t concerned with how long it takes or other sort of rules and, therefore, the output of the model contains all different types of pizza.

[Fact]
public void Minimizes_the_time_taken_to_cook_all_pizzas()
{
    var model = new MakePizzaModel(2, new List {PizzaType.Margherita, PizzaType.Pepperoni});
    var solver = new MakePizzaSolver(model);
     
    var solution = solver.Solve();
 
    const long expectedFinish = 138;
    solution.Finish.Should().Be(expectedFinish);
}

The model should minimise the time taken to cook all pizzas - Minimizes_the_time_taken_to_cook_all_pizzas() - and will provide an expectedFinish time for when the pizzas are ready. 2 chefs are being passed in and 2 pizzas are being cooked. Much like our routing test (Model_minimizes_distance_travelled), we have used a small enough example to be able to manually verify that this is the quickest time the pizzas can all be made in. We can therefore assert that all pizzas are cooked in 138 minutes’ time – our expectedFinish.

[Fact]
public void Pizzas_stages_are_done_in_correct_order()
{
    var model = new MakePizzaModel(1, new List {PizzaType.Margherita});
    var solver = new MakePizzaSolver(model);
     
    var solution = solver.Solve();
 
    var expectedStageOrder = new List {CookingStage.Shaping, CookingStage.Preparing, CookingStage.Cooking};
    var scheduledStages = solution.Pizzas[0].Stages.Select(s => s.Stage);
    scheduledStages.Should().ContainInOrder(expectedStageOrder);
}

This unit test could specify by pizza type (margherita, pepperoni, Hawaiian), but for the purpose of this test, we are testing margherita specifically, so we just have CookingStage.Shaping, CookingStage.Preparing and CookingStage.Cooking to check for.

The scheduledStages should ContainInOrder the expectedStageOrder. What this means is that pizzas should be prepared in the order that is set out.

We further specify that Only_one_pizza_fits_in_the_oven(). So, if we input two margherita pizzas, we will receive an output for each pizza which will also outline the individual stages which each pizza goes through. We also define a Boolean - twoPizzasCookingAtTheSameTime - which represents the times overlapping and assert that this is false.

[Fact]
public void Only_one_pizza_fits_in_the_oven()
{
    var model = new MakePizzaModel(2, new List {PizzaType.Margherita, PizzaType.Margherita});
    var solver = new MakePizzaSolver(model);
     
    var solution = solver.Solve();
 
    var firstCookingStage = solution.Pizzas[0].Stages.Single(s => s.Stage == CookingStage.Cooking);
    var secondCookingStage = solution.Pizzas[1].Stages.Single(s => s.Stage == CookingStage.Cooking);
    var twoPizzasCookingAtTheSameTime = firstCookingStage.Start < secondCookingStage.Finish &&
                                        secondCookingStage.Start > firstCookingStage.Finish;
 
    twoPizzasCookingAtTheSameTime.Should().BeFalse();
}

2.2. Make Pizza Solver - Explained

Firstly, we CreateIntervalVars, then iterate through the count of pizza - request.Types.Count; pizzaIndex++ - which allows us to get the type of pizza that we want to cook (var pizza = request.Types[pizzaIndex]).

private void CreateIntervalVars(PizzaCpModel model)
{
    for (var pizzaIndex = 0; pizzaIndex < _request.Types.Count; pizzaIndex++)
    {
        var pizza = _request.Types[pizzaIndex];
        foreach (var (cookingStage, duration) in pizza.GetStages())
        {
            // code omitted for brevity
        }
    }
}

All stages must be completed on a something we define as a ‘machine’. which is defined as something that can complete a stage. As we have discussed, only the ovens can cook the pizzas, whilst the chefs take care of the other stages. So, if it’s the CookingStage.Cooking , then it needs to be the oven ‘machine’ that is completing this stage. If it’s any of the other stages, it can be prepared by any of the chefs (one of two in the example cited) – these make up the remaining ‘machines’.

Understanding the purpose of the machine also helps to explain the difference between a NewIntervalVar and a NewOptionalIntervalVar ; NewIntervalVar is when you know what machine that stage has to be done on. In this case we know that because it is cooking, it has to be done on the oven machine, therefore we use NewIntervalVar for cooking stages. For the other stages, we use NewOptionalIntervalVar, as we the model has a choice of more than once machine (or chef) to assign this stage to.

For the purpose of this model, we say that the OvenId is always machine 0 and the first chef will be machine 1, the second chef will be machine 2 and so forth.

For each pizza, we create variables called startVar and endVar. We have a horizon which is the longest possible time that this process could take. When declaring the variables, we’re requesting that Google OR-Tools set the variable somewhere between 0 and the horizon.

var stageName = $"pizza_{pizzaIndex}_{cookingStage}";
// Create variables for when this stage starts and finishes
var startVar = model.NewIntVar(0, _horizon, $"{stageName}_start");
var endVar = model.NewIntVar(0, _horizon, $"{stageName}_end");

Then, as we said with the cooking stage, we then create the NewIntervalVar, which we keep track of later. We can only do this if we know which 'machine' we'll be completing the stage on.

if (cookingStage == CookingStage.Cooking)
{
    // If this stage is cooking, there is only one 'machine' option, so we can have a mandatory interval var
    var stageVar =
        model.NewIntervalVar(startVar, duration, endVar, $"{stageName}_interval");
    model.PizzaStageIntervals[pizzaIndex].Add(stageVar);
    model.MachineIntervals[OvenId].Add(stageVar);
}

For other stages, we need to iterate through the available chefs, and create optional constraints.

// If we're not cooking, we have a choice of chefs who can perform this task.
var chefActivation = model.NewBoolVar($"{stageName}_chef_{chefIndex}");
IntVar chefStartVar = model.NewIntVar(0, _horizon, $"{stageName}_start");
IntVar chefEndVar = model.NewIntVar(0, _horizon, $"{stageName}_end");

// Create an optional interval. This sets the chefActivation to true if the chef is chosen.
var stageVar =
    model.NewOptionalIntervalVar(startVar, duration, endVar, chefActivation,
        $"{stageName}_interval");
model.PizzaStageIntervals[pizzaIndex].Add(stageVar);
model.MachineIntervals[chefIndex].Add(stageVar);
 
// Bind this chef's start and end variables to the actual start and end, if we choose this chef
model.Add(chefStartVar == startVar).OnlyEnforceIf(chefActivation);
model.Add(chefEndVar == endVar).OnlyEnforceIf(chefActivation);
chefActivations.Add(chefActivation);

Here we are saying which chef we want to complete the action. Crucially, we are saying that we don’t care which chef is selected, as long as each stage is cooked by one of these chefs - to do this we define an optional interval. Because it’s optional, it contains a boolean that is set to true or false, representing whether Google OR-Tools has decided to use this interval. Each optional interval therefore represents a chef potentially completing a stage.

// Ensure a chef is chosen for this pizza
model.Add(new SumArray(chefActivations) == 1);

We say that, if we have used this chef, bind the chef’s start to the start variable (chefStartVar = startVar) and the chef’s end variable to the end variable (chefEndVar = endVar).

model.Add(new SumArray(chefActivation = 1);: This makes sure that the sum of the Booleans is 1 which, in turn, means that exactly one of those chefs has been picked. model.Add, specifically, refers to a new rule being added to the model.

2.3. Constraints

private void AddStagePrecedence(PizzaCpModel model)
{
    for (int j = 0; j < model.PizzaStageStarts.Count; ++j)
    {
        for (int t = 0; t < model.PizzaStageStarts[j].Count - 1; ++t)
        {
            var postStageBuffer = 0;
            if (_request.Types[j].GetStages().ElementAt(t).Key == CookingStage.Shaping)
            {
                postStageBuffer = DoughRisingDuration;
            }
 
            model.Add(model.PizzaStageEnds[j][t] + postStageBuffer <= model.PizzaStageStarts[j][t + 1]);
        }
    }
}

On top of the unit tests, where each stage is done in order, we are also saying that the end of one stage is less than or equal to the next stage - [t + 1]). If we were to comment out the code assigning the postStageBuffer to the DoughRisingDuration, the test which waits for an hour after the shaping stage would start failing, so what we’re saying here is the end of this stage plus the buffer needs to be less than or equal to the beginning of the model.PizzaStageStarts.

This makes sure that, first, we wait for an hour before beginning a new stage, but for the other stages too it makes sure that there aren’t blocks on top of each other in our Gantt chart.

We are saying that, in summary, the next stage cannot start until the previous stage has finished. This is what allows a chef not to work on multiple things at once and an oven not to work on multiple things at once.

We also need to prevent chefs from working on multiple things at once, which is achieved by the below code, namely, with model.AddNoOverlap(model.MachineIntervals[machineId]);. This means that of all the intervals can be overlapped for a specific machine i.e., cannot be undertaken at the same time. This also makes sure that it’s all single file, per chef or oven.

private void DeclareObjective(PizzaCpModel model)
{
    // Creates array of end_times of jobs.
    IntVar[] allEnds = new IntVar[_pizzaCount];
    for (var pizzaIndex = 0; pizzaIndex < _pizzaCount; pizzaIndex++)
    {
        allEnds[pizzaIndex] = model.PizzaStageEnds[pizzaIndex].Last();
    }
 
    // Objective: minimize the makespan (maximum end times of all tasks)
    // of the problem.
    IntVar makespan = model.NewIntVar(0, _horizon, "makespan");
    model.AddMaxEquality(makespan, allEnds);
    model.Minimize(makespan);
}

We’ve kept track of all the PizzaStageEnds - the end times of all the pizzas. Here we assign a max variable - illustrated through IntVar makespan = model.NewIntVar(0, _horizon, "makespan"); - as well as a max equality (AddMaxEquality) from the makespan to all the end variables and then we call model.Minimize(makespan). This is the objective of our model; when we click solve, it’s going to pick the one that satisfies that objective the best.

// Create the solver.
CpSolver solver = new();
// Solve the problem.
var status = solver.Solve(model);
 
if (status == CpSolverStatus.Optimal)
{
    return GetSolution(model, solver);
}
 
throw OptimisationException.NoSolution();

After running solver.Solve, we’ll either be able to get the solution and our model or if it’s not we throw an exception throw OptimisationException.NoSolution();

Read the third and final part of this OR-Tools series, where we'll look at assigning our pizzas to our Audacia guests; we'll be optimising this action by ensuring that they get the most slices of their favourite flavour pizza.

Audacia is a software development company based in the UK, headquartered in Leeds. View more technical insights from our teams of consultants, business analysts, developers and testers on our technology insights blog.