Optimal Meeting Scheduling

Author(s): Optimization team

Originally published on Towards AI.

Scheduling meetings without overlaps can be a complex task, especially when dealing with multiple participants with busy schedules and big number of meetings.

The meeting schedulling can be done using various optimization tools such as Pyomo, GAMS, Google OR-Tools, AIMMS or AMPL . To effectively utilize these tools, it is essential to construct a well-defined mathematical model that accurately represents the underlying scheduling problem. This article uses Google OR-Tools package.

Let's get our hands dirty and tackle the problem:

To illustrate the problem description, let’s consider a scenario where an organization employs 20 staff members, each of whom may belong to various teams. Within this organization, there are six distinct teams:

1. Sales
2. Finance
3. Legal
4. Customer Support
5. R&D
6. Quality Assurance

The subsequent graph provides a visual representation of the staff members’ affiliations with these teams:

{1: [1, 2, 4, 5, 9, 10, 11, 14, 15, 18],
 2: [1, 2, 3, 5, 6, 9, 10, 11, 15, 17, 18],
 3: [5, 13, 14, 18, 19],
 4: [1, 5, 6, 9, 12, 13, 14, 17, 18, 20],
 5: [3, 6, 7, 8, 10, 16, 17, 20],
 6: [2, 6, 8, 9, 10, 13, 15]}

There are five-time slots (1,2,3,4,5) which these teams should be assigned to them.

Clearly, when a staff member (p) is concurrently part of both team i and team j, scheduling meetings for these two teams during the same time slot presents a dilemma, as staff member p cannot attend both. The concept is to create a model aimed at minimizing such scheduling conflicts.

Optimization model

Python Code

For this problem, the OR-Tools package can be used as follows:

Import the required packages:

from ortools.sat.python import cp_model
import numpy as np 
import matplotlib.pyplot as plt
import random

Before creating and calling the model we need to prepare the data:

Timeslots = [1,2,3,4, 5]
Individuals = [i+1 for i in range(20)]
Teams = [team+1 for team in range(6)]

individual_member = {}
for p in Individuals:
 n = random.randint(1,4)
 individual_member[p] = random.sample(Teams, n)
team_members = {team:[] for team in Teams}
for p , team_list in individual_member.items():
 for team in team_list:
 team_members[team].append(p)
team_members

The CP model

def SearchForAllSolutionsSampleSat():
 model = cp_model.CpModel() 
 x = {(team,t):model.NewBoolVar(f"x_{team}_{t}") for team in Teams for t in Timeslots}
 over_pt = {(p,t):model.NewIntVar(0,len(Teams)-1, f"over_{p}_{t}") for p in Individuals for t in Timeslots}
 
 for team in Teams:
 model.AddExactlyOne([x[team,t] for t in Timeslots])

 for t in Timeslots:
 for p in Individuals:
 expressions = [x[team,t] for team in Teams if p in team_members[team] ]
 model.Add(sum(expressions)-1<= over_pt[p,t]) 

 of_expr = sum([over_pt[p,t] for p in Individuals for t in Timeslots])
 model.Minimize(of_expr)
 solver = cp_model.CpSolver()
 solution_printer = VarArraySolutionPrinter([x,over_pt])
 solver.parameters.enumerate_all_solutions = False
 # Solve.
 status = solver.Solve(model, solution_printer)
 print(f"Status = {solver.StatusName(status)}") 
 print('Overassigned' , [i[0] for i in over_pt if solver.Value(over_pt[i]) ])

SearchForAllSolutionsSampleSat()

Visualizing the Results

Team scheduling will be as follows:

plt.figure(figsize=(6,6))
 team_assignment = {} 
 for (team,t),v in x.items():
 if solver.Value(v)>0:
 team_assignment[team,t] =1 
 print(f"Team {team} ------> time {t}")
 
 plt.scatter(t,team,s=300,c= 'g', zorder=3)
 plt.scatter(0,team,s=300,c= 'k', zorder=3)
 plt.text(-0.2*len(Timeslots),team,s=f"team{team}",c= 'k', zorder=3,fontsize=14, fontweight='bold')

 for t in Timeslots:
 plt.text(t,team+0.3,s=f"t{t}",c= 'k', zorder=3,fontsize=14, fontweight='bold')
 plt.axis('off')
 plt.savefig(f" Teams schedule.png")
 plt.show()

To check the number of meetings for each staff at each time slot, the following visualization can be handy:

 plt.figure(figsize=(11,7))
 print(f"Team member {1} {2} {3} ") 
 for p in Individuals:
 time_assign = []
 for t in Timeslots:
 a = [team for team in Teams if p in team_members[team] and (team,t) in team_assignment]
 if len(a)>0:
 time_assign.append(len(a))
 plt.text(p-0.02,t+0.2,s=L2S(a),fontsize=8, fontweight='bold', rotation = 90)
 plt.scatter(p,t,s=200)
 else:
 time_assign.append(0)
 print(f"{p} {time_assign[0]} {time_assign[1]} {time_assign[2]} ") 
 plt.grid()
 plt.xticks(Individuals ,fontsize=14, fontweight='bold')
 plt.yticks(Teams ,fontsize=14, fontweight='bold')
 plt.ylim(0.5,len(Timeslots)*1.2)
 plt.ylabel(' Time slots ',fontsize=14, fontweight='bold')
 plt.xlabel(' Individuals ',fontsize=14, fontweight='bold')
 plt.savefig(f"all staffs.png")
 plt.show()

It can be observed that all staffs are optimally scheduled without any over assignment.

Conclusion

Optimization, particularly through Linear Mixed-Integer Programming (MILP), proves invaluable for meeting scheduling due to several key reasons:

1. Efficiency Enhancement: MILP models allow for the efficient allocation of limited resources, such as meeting rooms and participants’ time, leading to reduced waste and improved resource utilization.
2. Conflict Resolution: Optimization can identify and resolve conflicts in meeting schedules by considering constraints, ensuring that participants are not double-booked and minimizing scheduling overlaps.
3. Cost Reduction: By minimizing the overall cost associated with meeting scheduling, organizations can save resources and reduce overhead expenses, making operations more cost-effective.
4. Customization: MILP models can be tailored to address specific business requirements, accommodating various constraints and objectives to meet an organization’s unique needs.
5. Time Savings: Implementing optimization techniques streamlines the scheduling process, saving time for administrative staff and participants, and ultimately enhancing overall productivity and effectiveness in an organization.

Want to connect?

• U+1F4D6 Follow me on Medium
• Access the code on Github
• U+1F48C Subscribe to get an email whenever I publish
• U+1F913 Connect with me on LinkedIn

Join thousands of data leaders on the AI newsletter. Join over 80,000 subscribers and keep up to date with the latest developments in AI. From research to projects and ideas. If you are building an AI startup, an AI-related product, or a service, we invite you to consider becoming a sponsor.

Published via Towards AI