The world’s leading publication for data science, AI, and ML professionals.

Data-Driven Approach for Schedule Optimizations

How to use Google OR-Tools for scheduling problems and visualize the output with Plotly

Photo by Pablo Merchán Montes on Unsplash
Photo by Pablo Merchán Montes on Unsplash

Starting from a restaurant…

Imagine you are the manager of a restaurant. Today happens to be a busy day, and you are now short of manpower to complete the orders from customers. The vegetables need to be washed, the chicken needs to be cut, meanwhile, the dishes need to be done… After the food is cooked, someone also needs to serve the food and collect money from customers. Seeing the to-do list getting longer and longer, now you are feeling a bit anxious: who should you assign to work on what tasks, so that you can complete all the orders within minimum time?

The scenario I have just described is actually a scheduling problem by nature. Or on the higher level, it is a subset of OR (Operation Research) topics. Operation Research is a discipline that deals with the application of advanced analytical methods to help make better decisions. There are plenty of open-source libraries available that users can utilize to solve scheduling problems. Among them, Google OR-Tools is one of the most popular open-source libraries to solve issues including vehicle routing, scheduling, integer programming, linear programming, and constrain programming problems. For more details, you may refer to their official website over here.

Although there are plenty of examples given in the link to demonstrate how to make use of this library for the Optimization problem, the initial learning curve might be a bit deep if you are completely new to it. Today I am going to show you an example of making schedules for staff in a restaurant, which hopefully makes it easier for you to grasp the concepts. Let’s dive in!

Problem Set Up

Now let’s add more details to the restaurant Scheduling problem, to better simulate an actual restaurant environment. For easier tracking, let’s say there are a total of three staffs in our restaurant to help out on the tasks. To complete the orders from customers, there are generally three types of tasks to work on:

  1. Preparing ingredients. This step may involve washing the vegetables, cutting up the chicken, etc.
  2. Cooking meals. Depending on different types of food, the cooking time might be longer or shorter.
  3. Serving customers. This step may involve tasks such as serving the dishes, collecting payments, etc.

Again, in reality, the whole process can be breakdown further, here we just take these 3 steps for the sake of simplicity. Another thing to note here is, the staffs actually need to complete these 3 steps in order – I.e. one can only cook meals after the preparation works are done. Serving food to customers is not possible unless the meal is cooked. In the context of the scheduling problems, these are called "precedence constraints". We will revisit this concept again in the coding section later. After setting the 3 main processing steps, the next step is to identify which staff to be in charge of which processing step, and how much time is required from him/her to complete that. In reality, the task arrangement could be quite flexible here, as some staff may be able to handle both ingredient preparation and cooking, while others may only focusing on serving the clients. In our example, we will pre-arrange the tasks assigned to each individual staff for simplicity purposes. More details on this in the coding part.

Scheduling with Google OR-Tools

With these settings in place, we are ready to move on to the actual coding. As mentioned earlier, I would use Google OR-Tools as the supporting library to optimize the schedule for our restaurant. To install Google OR-Tools for python, you can simply type the following in command line:

python -m pip install --upgrade --user ortools

It is worthy to mention that if you are using C++, C#, or Java, Google OR-Tools also has the available wrapper for you. There are several solvers available in Google OR-Tools targeting different use cases. For scheduling, we are going to use the CP-SAT solver:

from ortools.sat.python import cp_model

At the beginning of the program, we need to first define the order information, consisting of the staff assigned and the required time for completing that step. Here the order data is defined as a list of tuples, where each tuple pair represents the assigned staff and required processing time. A sample illustration could be found in the image below.

Image by Author
Image by Author

The "horizon" variable defines the upper bound of the possible value assigned in the final schedule. By taking the sum of all the time needed for each task, it returned the total time required as the worst-case scenario if everything is finished sequentially one by one. You will see how this "horizon" parameter comes into the picture in the following sections.

horizon = sum(task[1] for job in jobs_data for task in job)

In the next section of code, we use nested for loops to go through each individual processing step for all 3 orders, and then create the start, end, and interval variables correspondingly. Note here the start_var is defined as model.NewIntVar(0, horizon, ‘start’+suffix) – here the horizon defines the upper bond of how large the start_var can go. By creating all these variables, it will be easier to define the relevant constraints of the problem later on.

for job_id, job in enumerate(jobs_data):
    for task_id, task in enumerate(job):
        staff = task[0]
        duration = task[1]
        suffix = '_%i_%i' % (job_id, task_id)
        start_var = model.NewIntVar(0, horizon, 'start' + suffix)
        end_var = model.NewIntVar(0, horizon, 'end' + suffix)
        interval_var = model.NewIntervalVar(start_var, duration, end_var, 'interval' + suffix)
        all_tasks[job_id, task_id] = task_type(start=start_var,
                                               end=end_var,
                                               interval=interval_var)
        staff_to_intervals[staff].append(interval_var)

After defining all the relevant variables, the next step is to define the constraints for our problem. In our example, we have the following 3 main constraints:

  1. One staff can only work on one task at a given time – no multi-tasking is allowed( I am sure you don’t want your staff to serve dishes to clients while he/she is busy cooking). Under the context of scheduling, this is called disjunctive constraints.
  2. As we already mentioned earlier, the sequence of steps needs to be followed to complete the order -> preparation, cooking, and then serving. This is called precedence constrain in the scheduling problem.
  3. Lastly, the overall objective is of course to finish all the orders with the least amount of time.
# Create and add disjunctive constraints.
for staff in all_staffs:
    model.AddNoOverlap(staff_to_intervals[staff])

# Precedences inside a job.
for job_id, job in enumerate(jobs_data):
    for task_id in range(len(job) - 1):
        model.Add(all_tasks[job_id, task_id + 1].start >= all_tasks[job_id, task_id].end)
#Minimize the total time spent
obj_var = model.NewIntVar(0, horizon, 'total_time')
model.AddMaxEquality(obj_var, [all_tasks[job_id, len(job) - 1].end for job_id, job in enumerate(jobs_data)])
model.Minimize(obj_var)

With these things configured, then we just need to let the Google OR-Tools do the optimization work in the backend and see what is the output returned. The status variable will return "Optimal" if an optimal solution is found later

solver = cp_model.CpSolver()
status = solver.Solve(model)

Visualize the output schedule

So now the model is returning "Optimal" after running the solver. Excellent! Now how should we visualize the schedule? Basically, we will need to retrieve the final values of the relevant start and end time variable we defined earlier, and then visualize it with some bar charts. Plotly offers a handy function for us to create Gantt Charts automatically, as long as the input data is formatted in the desired format. I will not go into much detail about the usage of the Plotly library, you can always refer to the tutorials online or my full code later on.

def visualize_schedule(assigned_jobs,all_staffs,plan_date):
    final = []
    for staff in all_staffs:
        #print("This is for staff: ", staff)
        assigned_jobs[staff].sort()
        for assigned_task in assigned_jobs[staff]:
            name = 'Order_%i' % assigned_task.job
            temp = dict(Task=staff,Start=plan_date + pd.DateOffset(minutes = assigned_task.start),
                        Finish= plan_date + pd.DateOffset(minutes = (assigned_task.start + assigned_task.duration)),
                        Resource=name)
            final.append(temp)
    final.sort(key = lambda x: x['Task'])
    return final

The final output visualized with Plotly is shown in the graph below. We can see that the overall time spent is 18 mins for completing all three orders. With this visualization, you can have a very direct view of if the relevant constraints and fulfilled.

Restaurant working schedule visualized with Plotly (Image by Author)
Restaurant working schedule visualized with Plotly (Image by Author)

Adding additional constraints

The problem we just defined is actually a very basic example of scheduling. In the real world, there are lots of other types of constraints that we might need to take into account. Here we could add another constraint for illustration purposes: To ensure better customer satisfaction, the restaurant requests that all the dishes should be served to the customers within 3 minutes after it finishes cooking. In other words, now the time gap between step 2 and step 3 should be within 3 mins. As we can observe in the schedule output earlier on, now order 1 is not meeting this constraint with a large gap between step 2 and step 3. How can we add this constrain to the model? Actually, it could be done quite easily by adding the condition highlighted in bold below, which is quite self-explanatory I hope:

for job_id, job in enumerate(jobs_data):
    for task_id in range(len(job) - 1):
        model.Add(all_tasks[job_id, task_id + 1].start >= all_tasks[job_id, task_id].end)
        # Make sure the time gap of task 2 and task 3 are less then 3 mins
        if task_id == 1:
            model.Add(all_tasks[job_id, task_id + 1].start <= all_tasks[job_id, task_id].end + 3)
        else:
            continue

After adding this constrain and re-run the model, the updated schedule is shown in the diagram below. While the overall completion time remains the same, now all 3 orders are fulfilling the new constraint we placed in (no more than 3 mins wait from cooking completion and serving). While this solution might look straightforward in this example, when the staff counts and the number of orders scale up, the benefits of using this tool will be more obvious.

Updated schedule with additional constraints (Image by Author)
Updated schedule with additional constraints (Image by Author)

Final Thoughts and Future Works

There are plenty of things we can improve on for this use case. For instance, Instead of pre-defining individual tasks to different staffs, we can configure it in a way that the same task could be handled by different people. Based on their proficiency level for different tasks, likely there will be different processing times associated. In this way, the scheduler could give more dynamic outputs.

To further enhance it, we can host this scheduler as a web application, where users can simply input the staff and order information through frond-end UI, and then the final schedule will be shown as the output. Feel free to try this out if that interests you!

Reference

The example showed in this post largely follows the same structure as the one on their official website. For further examples on implementing other constraints with Google OR-Tools, you can refer to their Github page and discussion groups.

Lastly, you may find the full code I used for this post from my Github page here. Thanks for reading!

P.S.

In case you are interested to join the Medium Membership Program, you can use the following link to sign up! Appreciate your help in advance 🙂

https://medium.com/@tianjie1112/membership


Related Articles